[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;
}

[UVa] 336 - A Node Too Far

You see, I had a crazy time with this one. So no joke. I made my big mistake in designing the queue and finally used the STL.
Still, there are some really useful test cases I got. I corrected it later. It was in the empty verifier.
Input:

1
1 1
25 0
1 0
1 1
0 0
5
1 2 2 3 3 4 4 5 6 7
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
0 0
0

Output:

Case 1: 0 nodes not reachable from node 25 with TTL = 0.
Case 2: 0 nodes not reachable from node 1 with TTL = 0.
Case 3: 0 nodes not reachable from node 1 with TTL = 1.
Case 4: 6 nodes not reachable from node 1 with TTL = 0.
Case 5: 5 nodes not reachable from node 1 with TTL = 1.
Case 6: 4 nodes not reachable from node 1 with TTL = 2.
Case 7: 3 nodes not reachable from node 1 with TTL = 3.
Case 8: 2 nodes not reachable from node 1 with TTL = 4.
Case 9: 2 nodes not reachable from node 1 with TTL = 5.
Case 10: 2 nodes not reachable from node 1 with TTL = 6.
Case 11: 2 nodes not reachable from node 1 with TTL = 7.

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

int q[100], front, rear, color[100], graph[100][100], g_depth,  v[100], d[100], n_edge;
void init_q() { front = 0; rear = 0; }
void insert_q(int val) { q[rear++]=val; }
int del_q() { return q[front++]; }
int q_empty() { return (front==rear); }

int BFS(int src) {
    int depth=1, count=0, i, u;
    init_q();
    insert_q(src);
    for (i=1 ; i<=33 ; i++) {
        color[i]=0;
        d[i]=-1;
    }
    d[src]=0;

    color[src]=1;

    while (!q_empty()) {
        u = del_q();

        for (i=1 ; i<=33 ; i++) {
            if (graph[u][i]==1 && color[i]==0) {
                color[i]=1;
                insert_q(i);
                d[i]=d[u]+1;
            }
        }

    }

    for (i=1 ; i<=33 ; i++) {
        if (d[i]>0 && d[i]<=g_depth) {
            count++;
        }
    }

    return count;
}

int main()  {
    int i, j, x, y, cases=1, node, p_x, p_y, k;
    while (scanf("%d",&n_edge)&& n_edge) {
        for (i=0 ; i<=33 ; i++) {
            v[i]=-1;
            for (j=0 ; j<=33 ; j++) {
                graph[i][j]=0;
            }
        }
        for (i=1, node=1 ; i<=n_edge ; i++) {
            scanf("%d %d",&x,&y);          /*----------Renaming method----------*/
            for (k=1, p_x=-1; k<node ; k++) {
                if (v[k]==x && p_x==-1) {
                    p_x=k;
                    break;
                }
            }
            if (p_x<0) {
                v[node++]=x;
                p_x=node-1;
            }
            for (k=1, p_y=-1 ; k<node ; k++) {
                if (v[k]==y && p_y==-1) {
                    p_y=k;
                    break;
                }
            }
            if (p_y<0) {
                v[node++]=y;
                p_y=node-1;
            }
            graph[p_x][p_y]=graph[p_y][p_x]=1;
            graph[p_x][p_x]=graph[p_y][p_y]=1;
        }
        while (scanf("%d %d",&x,&g_depth)) {
            if (!x && !g_depth)
                break;
            for (i=1 ; i<=33 ; i++) {
                if (v[i]==x) {
                    break;
                }
            }
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cases++,node-BFS(i)-2,x,g_depth);
        }
    }
    return 0;
}

[UVa] 10946 - You want what filled?

Befoe anyone tries to straightaway put their beloved DFS() function in it, it's Flood Fill. I honestly didn't have a clue why. But the only logical thing seems to be that checking all 8 blocks is a waste when if there's a hole right at the corner it will be detected if one just above/below it exists. Anyway, if anyone has a better reason, please do tell me.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct r {
    char c;
    int val;
} res[100000]={0,0};
int x, y, color[100][100], d[100][100], f[100][100], p[100][100];
unsigned char graph[100][100];
int visit(int ux, int uy, unsigned char col) {
    int visited=1;
    if (color[ux][uy])
        return 0;
    color[ux][uy]=1;
    if (graph[ux-1][uy]==col) visited+=visit(ux-1,uy,col);
    if (graph[ux][uy-1]==col) visited+=visit(ux,uy-1,col);
    if (graph[ux][uy+1]==col) visited+=visit(ux,uy+1,col);
    if (graph[ux+1][uy]==col) visited+=visit(ux+1,uy,col);
    return visited;
}

int DFS() {
    int i, j, k=0;
    /*------------Initialization phase starts------------*/
    for (i=0 ; i<=x ; i++) {
        for (j=0 ; j<=y ; j++) {
            color[i][j]=0;
            d[i][j]=99999;
            f[i][j]=99999;
            p[i][j]=-1;
        }
    }
    /*-----------Initialization phase ends----------------*/

    for (i=1 ; i<=x ; i++) {
        for (j=1 ; j<=y ; j++) {
            if (color[i][j]==0 && graph[i][j]!='.') {
                res[k].c=graph[i][j];
                res[k].val=0;
                res[k].val+=visit(i,j,graph[i][j]);
                k++;
            }
        }
    }
    return k;

}

int cmp(const void *a, const void *b) {
    if (((struct r*)a)->val==((struct r*)b)->val)
        return (((struct r*)a)->c-((struct r*)b)->c);
    else
        return (((struct r*)b)->val-((struct r*)a)->val);
}

int main() {
    int i, j, k, prob=1;
    while (scanf("%d %d",&x,&y)!=EOF) {
        getchar();
        if (!x && !y) break; /*--End of input--*/
        for (i=1 ; i<=x ; i++) {
            for (j=1 ; j<=y ; j++) {
                graph[i][j]=getchar();
            }
            getchar();
        }

        k=DFS();
        qsort(res,k,sizeof(struct r),cmp);
        printf("Problem %d:\n",prob++);
        for (i=0 ; i<k ; i++) {
            printf("%c %d\n",res[i].c,res[i].val);
        }
    }
    return 0;

}

[UVa] 352 - Seasonal War

Another simple DFS.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int color[200][200], d[200][200], pi[200][200], f[200][200];
char graph[200][200]={0};
int time, nrows, ncols, count=0;


void DFS_visit(int ux, int uy) {
    int i, j, k, v;
    color[ux][uy]=1;
    time = time + 1;
    d[ux][uy] = time;
    i=ux-1;
    if (i<1) i++;

    for (; i<=ux+1 ; i++) {
        j=uy-1;
        if (j<1) j++;
        for ( ; j<=uy+1 ; j++) {

            if (color[i][j]==0 && graph[i][j]=='1') {
                DFS_visit(i,j);
            }
        }
    }
    color[ux][uy]=2;

    f[ux][uy] = time = time + 1;


}

void DFS() {
    int i, j, k, v;

    for (i=1 ; i<=nrows ; i++) {
        for (j=1 ; j<=ncols ; j++) {
            color[i][j]=0;
            pi[i][j]=-1;
            d[i][j]=99999;
            f[i][j]=99999;
        }
    }
    time = 0; /* - Global - */
    for (i=1 ; i<=nrows ; i++) {
        for (j=1 ; j<=ncols ; j++)
            if (color[i][j]==0 && graph[i][j]=='1') {

                count++;
                DFS_visit(i,j);
            }
    }

}

int main() {
    int i, j, image=1;
    while (scanf("%d",&nrows)!=EOF) {
        count=0;
        if (nrows==0)
            break;
        getchar();

        ncols=nrows;

        for (i=1 ; i<=nrows ; i++) {
            gets(&graph[i][1]);
        }

        DFS();

        printf("Image number %d contains %d war eagles.\n",image++,count);
    }
    return 0;
}

572 - Oil Deposits

Simple DFS

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int color[200][200], d[200][200], pi[200][200], f[200][200];
unsigned char graph[200][200]={0};
int time, nrows, ncols, count=0;


void DFS_visit(int ux, int uy) {
    int i, j, k, v;
    color[ux][uy]=1;
    time = time + 1;
    d[ux][uy] = time;
    i=ux-1;

    if (i<1) i++;

    for (; i<=ux+1 ; i++) {
        j=uy-1;
        if (j<1) j++;
        for ( ; j<=uy+1 ; j++) {
            if (i==ux && j==uy)
                continue;

            if (color[i][j]==0 && graph[i][j]=='@')
                DFS_visit(i,j);
        }
    }
    color[ux][uy]=2;

    f[ux][uy] = time = time + 1;


}

void DFS() {
    int i, j, k, v;

    for (i=1 ; i<=nrows ; i++) {
        for (j=1 ; j<=ncols ; j++) {
            color[i][j]=0;
            pi[i][j]=-1;
            d[i][j]=99999;
            f[i][j]=99999;
        }
    }
    time = 0; /* - Global - */
    for (i=1 ; i<=nrows ; i++) {
        for (j=1 ; j<=ncols ; j++)
            if (color[i][j]==0 && graph[i][j]=='@') {
                count++;
                DFS_visit(i,j);
            }
    }

}

int main() {
    int i, j;
    while (scanf("%d %d",&nrows,&ncols)!=EOF) {
        count=0;
        if (nrows==0 || ncols==0)
            break;
        getchar();

        for (i=1 ; i<=nrows ; i++) {
            for (j=1 ; j<=ncols ; j++) {
                scanf("%c",&graph[i][j]);
            }
            getchar();
        }

        DFS();

        printf("%d\n",count);


    }

}

[UVa] 567 - Risk

Could've been a lot better code, but I had to solve and submit it tomorrow (check the date) for the ACM Classes at my uni. I think the most logical algo to use here is Floyd-Warshall's APSP. But our trainer wanted this in BFS. Whatever, yielded a better BFS to use in other scenarios :). Yeah yeah, look at the bright side.

#include <stdio.h>
#include <queue>
using namespace std;
int color[30], pi[30], d[30], adj[30][30];
void BFS(int s, int p) {
    int i, u, v;
    for (i=20 ; i>=1 ; i--) {
        color[i]=0;
        d[i]=9999;
        pi[i]=-1;
    }

    color[s]=1;
    d[s]=0;
    pi[s]=-1;

    queue<int> q;

    q.push(s);

    while (!q.empty()) {
        u = q.front();
        q.pop();
        for (v=1 ; v<=20 ; v++) {
            if (color[v]==0 && adj[u][v]) {
                color[v]=1;
                d[v]=d[u]+1;
                pi[v]=u;
                q.push(v);
            }
        }
        color[u]=2;
    }

}


int main() {

    int i, j, f_pc, t_v, nq, x, y, test=1, dis;

    while (scanf("%d",&f_pc)!=EOF) {
        printf("Test Set #%d\n",test++);
        for (i=1 ; i<=20 ; i++) {
            for (j=1 ; j<=20 ; j++) {
                adj[i][j]=0;
            }
        }
        for (i=1 ; i<=f_pc ; i++) {
            scanf("%d",&t_v);
            adj[1][t_v]=1;
            adj[t_v][1]=1;
        }
        for (i=2 ; i<=19 ; i++) {
            scanf("%d",&f_pc);
            for (j=1 ; j<=f_pc ; j++) {
                scanf("%d",&t_v);
                adj[i][t_v]=1;
                adj[t_v][i]=1;
            }
        }



        scanf("%d",&nq);

        for (i=1 ; i<=nq ; i++) {
            scanf("%d %d",&x,&y);
            if (x>y) {
                if (!adj[x][y]) {
                    BFS(y,x);
                    dis=d[x];
                } else dis = 1;
                printf("%2d to %2d: %d\n",x,y,dis);
            }
            else {
                if (!adj[x][y]) {
                    BFS(x,y);
                    dis=d[y];
                } else dis=1;
                printf("%2d to %2d: %d\n",x,y,dis);
            }
        }
        printf("\n");

    }
    return 0;

}