[UVa] 10034 - Freckles

Method:

Algorithm used: Kruskal's MST
Complexity: n^2
Comments: I used structures to store edge & vertex information
For using qsort() you need to modify the cmp function as mine, or something
else that means the same.

Sample Input:

7

4
6.99999999999 0.99999999999999
6.99999999999 0.99999999999999
6.99999999999 -0.99999999999999
-6.99999999999 0.99999999999999

1
0.0 0.1

3
1.0 1.0
2.0 -2.0
2.0 4.0

4
1.0 1.0
2.0 2.0
2.0 4.0
-3.0 9.0

3
1.0 1.0
2.0 2.0
2.0 4.0

4
1.0 1.0
-2.0 -2.0
2.0 -4.0
3.0 9.0

5
0.0 0.0
0.0 -0.0
0.0 -0.0
-0.0 0.0
0.0 0.0

Sample Output:

16.00

0.00

6.32

10.49

3.41

16.96

0.00

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10100
int rank[MAX], p[MAX];
char blank[MAX];

struct point {
    double x, y;
} V[MAX]={0.0,0.0};

struct edge {
    int u, v;
    double w;
} A[MAX]={0,0,0.0}, E[MAX]={0,0,0.0};

int cmp(const void *a, const void *b) {
    /*return (((struct edge*)a)->w - ((struct edge*)b)->w);*/
    if (((struct edge*)a)->w > ((struct edge*)b)->w) return 1;
    else if (((struct edge*)a)->w < ((struct edge*)b)->w) return -1;
    else return 0;
}

double dis(int u, int v) {
    return sqrt(pow(V[u].x-V[v].x,2.0)+pow(V[u].y-V[v].y,2.0));
}

void make_set(int x) {
    p[x]=x;
    rank[x]=0;
}

int find_set(int x) {
    if (x!=p[x]) {
        p[x]=find_set(p[x]);
    }
    return p[x];
}

void link(int x, int y) {
    if (rank[x]>rank[y]) {
        p[y]=x;
    } else {
        p[x]=y;
        if (rank[x]==rank[y]) {
            rank[y]=rank[y]+1;
        }
    }
}

void uni(int x, int y) {
    link(find_set(x),find_set(y));
}

int kruskal(int num_vertex, int num_edge) {

    int idx_A=0, i;

    for (i=0 ; i<num_vertex ; i++) {
        make_set(i);
    }

    qsort(E,num_edge,sizeof(struct edge),cmp);

    for (i=0, idx_A=0 ; i<num_edge ; i++) {
        if (find_set(E[i].u)!=find_set(E[i].v)) {
            A[idx_A++]=E[i];
            uni(E[i].u,E[i].v);
        }
    }

    return idx_A;

}


int input(int num_vertex) {

    int i;

    for (i=0 ; i<num_vertex ; i++) {
        scanf("%lf %lf",&V[i].x,&V[i].y);
    }

    return num_vertex;
}

int edgify(int num_vertex) {

    int i, j, k;

    for (i=0, k=0 ; i<num_vertex ; i++) {
        for (j=0 ; j<num_vertex ; j++) {
            E[k].u = i;
            E[k].v = j;
            E[k].w = dis(i,j);
            k++;
        }
    }

    return k;

}


int main() {

    int i, num_vertex, test, blanker=1;
    double sum;

    scanf("%d",&test);
    getchar();

    while (test--) {

        gets(blank);

        scanf("%d",&num_vertex);
        getchar();

        sum = 0.0;

            int num_edge = edgify(input(num_vertex));

            int tree_count = kruskal(num_vertex,num_edge);

            for (i=0; i<tree_count ; i++) {
                sum = sum + A[i].w;
            }
            if (blanker++>1) putchar('\n');
            printf("%.2lf\n",sum);
    }

    return 0;
}

[UVa] 11466 - Largest Prime Divisor

Method:

1. Generate all primes till sqrt(99999999999999) and got on 
table.
2. For any number (if negative make it positive) used these till
the complete division is done or the table is fully used.
3. If the number is completely divided (becomes 1) just print the
last prime that was a divisor (provided there were 2 divisors at 
least).
4. If not fully divided, then you have a potential divisor in your 
hand. If there was at least one prime divisor from the collection 
print the remaining part that is still in your hand.
5. For any other case print -1.

Sample Input:

32
-32
-1
1
2
3
25412689632451
23554125478568
-96325415789658
32145222225856
32547854125223
99999999999999
11111111111111
99999999999998
99999999999997
-16
-17
-19
-24
0

Sample Output:

-1
-1
-1
-1
-1
-1
1164409
363444721
3912804281
3525017
21441599
909091
909091
7142857142857
119189511323
-1
-1
-1
3

#include <cstdio>
#include <iostream>
#include <cmath>
#define MAX 10001000
using namespace std;
bool ver[MAX]={false};
long long primes[1000000];
int sieve() {
    int i, j, k;
    k=0;
    for (i=2 ; i<=MAX ; i++) {
        if (ver[i]==false) {
            primes[k++]=(long long)i;
            for (j=2 ; i*j<=MAX ; j++) {
                ver[i*j]=true;
            }
        }
    }
    primes[0]=2;
    return k;
}

int main() {

    bool isNegative;
    int i, j, divcount, plim=sieve();;
    long long num, lastdiv;
    while (cin >> num && num) {
        isNegative=false;
        if (num<0) {
            num*=(-1);
            isNegative=true;
        }
        for (i=0, divcount=0, lastdiv=-1 ; i<plim && num>1 && primes[i]<=num ; i++) {
            if (num%primes[i]==0) {
                divcount++;
                while (num>1 && num%primes[i]==0) {
                    num/=primes[i];
                }
                lastdiv = primes[i];
            }
            if (num==1) {
                break;
            }
        }

        if (num==1) {
            if (divcount>1) cout << lastdiv << endl;
            else cout << -1 << endl;
        } else {
            if (divcount>0) cout << num << endl;
            else cout << -1 << endl;
        }
    }

    return 0;

}

[UVa] 974 - Kaprekar Numbers

Method:

Used DP again. :D I love pre-calculation in runtime. It's so nifty.
Checked all numbers from 1-40000 for a valid Kaprekar representation 
and stored the valid ones. There are about 20-30 numbers, forgot it.

#include <stdio.h>

int val[40000];

int main() {

    int i, j, k=0, key, p1, p2, start, end, cases=1, test;

    for (i=1 ; i<=40000 ; i++) {
        key = i*i;
        for (j=10 ; ((int)key/j)>0 ; j*=10) {
            p1 = ((int)key/j)*j;
            p2 = key-p1;
            p1/=j;
            if (p1+p2==i && p1 && p2) {
                val[k++]=i;
                break;
            }
        }
    }

    scanf("%d",&test);

    while (test--) {
        scanf("%d %d",&start,&end);

        printf("case #%d\n",cases++);
        for (i=0 ; i<k && val[i]<start ; i++);
        for (i, j=0 ; i<k && val[i]<=end ; i++) {
            printf("%d\n",val[i]);
            j=1;
        }
        if (!j) {
            printf("no kaprekar numbers\n");
        }
        if (test) printf("\n");
    }

    return 0;

}

[UVa] 534 - Frogger

Method:

Wasn't much hard as I was told already that it was minimax problem.
Used the Maximin algorithm

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

double st[300][2];
double min(double a, double b) {
    if (a>b) return a;
    else return b;
}
double max(double a, double b) {
    if (a<b) return a;
    else return b;
}
double w[300][300], d[300][300];


int main() {
    int i, j, k, n, sc=1;

    while (scanf("%d",&n)!=EOF && n) {
        scanf("%lf %lf",&st[1][0],&st[1][1]);
        scanf("%lf %lf",&st[n][0],&st[n][1]);
        for (i=2 ; i<n ; i++) {
            scanf("%lf %lf",&st[i][0],&st[i][1]);
        }

        for (i=1 ; i<=n ; i++) {
            for (j=1 ; j<=n ; j++) {
                d[i][j]=w[i][j]=(double)sqrt((double)pow(st[i][0]-st[j][0],2)+(double)pow(st[i][1]-st[j][1],2));
            }
            d[i][i]=0.000;
        }

        for (k=1 ; k<=n ; k++) {
            for (i=1 ; i<=n ; i++) {
                for (j=1 ; j<=n ; j++) {
                    d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
                }
            }
        }
        printf("Scenario #%d\nFrog Distance = %.3lf\n\n",sc++,d[1][n]);
    }
    return 0;
}

[UVa] 11917 - Do your own Homework

Method:
Straightforward, take input, then make the decision if the 
strings match.
If <=D 1,
else if <=D+5 2,
else 3.
Now print based on the stat, simple

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct s {
    char name[100];
    int req;
} sub[1000]={0,0};

int main() {

    int test, fs, i, n_sp_list, d, cases=1;
    char querry[100];

    scanf("%d",&test);

    while (test--) {
        for (scanf("%d",&n_sp_list), i=0 ; i<n_sp_list ; i++) {
            scanf("%s",&sub[i].name);
            scanf("%d",&sub[i].req);
        }
        scanf("%d",&d);
        scanf("%s",&querry);
        for (i=0, fs=0 ; i<n_sp_list ; i++) {
            if (!strcmp(sub[i].name,querry)) {
                if (sub[i].req<=d) {
                    fs=2;
                    break;
                } else if (sub[i].req<=(d+5)) {
                    fs=1;
                    break;
                } else {
                    fs=0;
                    break;
                }
            }
        }
        if (fs==0) {
            printf("Case %d: Do your own homework!\n",cases++);
        } else if (fs==1) {
            printf("Case %d: Late\n",cases++);
        } else {
            printf("Case %d: Yesss\n",cases++);
        }
    }
    return 0;
}

[UVa] 11900 - Boiled Eggs

Method:

1. Take all the input, store the weights sequentially and they are
already sorted, if you didn't notice.
2. Then simply keep adding eggs from that until either one of 
p or q is exceeded.
3. Print the count.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gms[1000]={0};

int main() {

    int test, n, p, q, c, i, cases=1;

    scanf("%d",&test);

    while (test--) {
        scanf("%d %d %d",&n,&p,&q);

        for (i=0 ; i<n ; i++) {
            scanf("%d",&gms[i]);
        }
        for (i=0, c=0 ; i<n ; i++) {
            if (i>=p || c+gms[i]>q) {break;}
            else c+=gms[i];
        }
        printf("Case %d: %d\n",cases++,i);
    }

    return 0;
}

[UVa] 962 - Taxicab Numbers

Method:

I used DP concept here
1. First generate all cubes up to 1000000000. It comes down to
an array of 1000 cubes
2. Then run a two dimensional loop, it means 
   loop { 
        loop {}
   }
where the cubes are added for possible taxicab numbers. 
Storing them is on your part. In my method I used a verifier
to see if a number was found earlier each time it's found and
if so I added it. You can get then all down at one go and then
create another array with no repetitions. Mine takes more time.
3. Then when given any lower limit and range you can perform
linear searches, won't exceed time limit.

FYI, the number of Taxicab numbers in total is 1554. My 2nd 
step generates 1562 where 8 numbers are repeated. You can see
which are they by enabling the last disabled for loop.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int bar[2000], found[10000000]={0};
bool ver[1000100000]={false};

int cmp(const void *a, const void *b) {
    return (*(int*)a-*(int*)b);
}

int main() {
    int i, low_lim, rng, j, k, key, counter, *get, l, insert;
    for (i=0 ; i*i*i<=1000000000 ; i++) {
        bar[i]=i*i*i;
    }
    int lim = i;

    for (j=1, k=0 ; j<1001 ; j++) {
        for (i=j+1 ; i<1001 ; i++) {
            if (bar[i]+bar[j]>1000100000) continue;
            if (ver[bar[i]+bar[j]]==true) {
                found[k++]=bar[i]+bar[j];
            } else {
                ver[bar[i]+bar[j]]=true;
            }
            /*key=bar[i]+bar[j];
            for (l=0, insert=0 ; l<k ; l++) {
                if ()
            }*/
        }


    }

    qsort(found,k,sizeof(int),cmp);

    /*for (i=0, counter=0 ; i<k ; i++) {
        if (i>0 && found[i]==found[i-1]) {
            counter++;
        }
    }*/

    /*k=k-counter;*/

    while (scanf("%d",&low_lim)!=EOF) {
        scanf("%d",&rng);

        for (i=0 ; i<k && found[i]<low_lim ; i++);
        for (i, insert=0 ; i<k && found[i]<=low_lim+rng ; i++) {
            insert=1;
            if (found[i]!=found[i-1]) printf("%d\n",found[i]);
        }
        if (!insert)
            printf("None\n");

    }

    return 0;
}