UVa - 10305 - Ordering Tasks

#include <bits/stdc++.h>
#define S 103
using namespace std;

vector <int> Order[S];
stack <int> ans;
int vis[S], cn;

void dfs(int src){
    if(vis[src])return;
    vis[src] = 1;
    int sz = Order[src].size();
    for(int z = 0; z < sz; z++){
        int v = Order[src][z];
        if(!vis[v])dfs(v);
    }
    ans.push(src);
}

int main(){
    int n, m, x, y;
    while(cin >> n >> m){
        if(!n && !m)return 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < m; i++){
            cin >> x >> y;
            Order[x].push_back(y);
        }
        for(int i = 1; i <= n; i++)if(!vis[i])dfs(i);
        int cn = 0, sz = ans.size();
        while(!ans.empty()){
            cn++;
            cout << ans.top();
            if(cn != sz)printf(" ");
            ans.pop();
        }
        puts("");
        for(int i = 0; i <= n; i++)Order[i].clear();
    }
    return 0;
}

UVa - 11518 - Dominos 2

#include <bits/stdc++.h>
#define S 10003
using namespace std;

vector <int> Dominos[S];
int vis[S], cn;

int dfs(int src){
    if(vis[src])return 0;
    vis[src] = 1;
    cn++;
    int sz = Dominos[src].size();
    for(int z = 0; z < sz; z++){
        int u = Dominos[src][z];
        dfs(u);
    }
    return cn;
}

int main(){
    int t, n, m, l, x, y, z;
    cin >> t;
    while(t--){
        cin >> n >> m >> l;
        for(int i = 0; i < m; i++){
            cin >> x >> y;
            Dominos[x].push_back(y);
        }
        memset(vis, 0, sizeof(vis));
        int ans = 0;
        for(int i = 0; i < l; i++){
            cn = 0;
            cin >> z;
            dfs(z);
            ans += cn;
        }
        cout << ans << endl;
        for(int i = 0; i <= n; i++)Dominos[i].clear();
    }
    return 0;
}

UVa - 11953 - Battleships

#include <bits/stdc++.h>
#define S 103
using namespace std;

int dirX[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dirY[] = {0, 1, 0, -1, 1, -1, -1, 1};

string battle[S];
int cnt, n;

void dfs(int i, int j){
    if(i < 0 || j < 0 || i >= n || j >= n || battle[i][j] == '.')return;
    battle[i][j] = '.';
    for(int z = 0; z < 8; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
}

int  main(){
    int t, cs = 0;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++)cin >> battle[i];
        cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(battle[i][j] == 'x'){
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << "Case " << ++cs << ": " << cnt << endl;
    }
    return 0;
}

UVa - 10946 - You want what filled?

#include <bits/stdc++.h>
#define S 53
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

struct data{
    char c;
    int cn;
}Letter[S*S];

string Land[S];
int cnt, x, y;
char tmp;

bool cmp(data a, data b){
    if(a.cn == b.cn)return a.c < b.c;
    return a.cn > b.cn;
}

void dfs(int i, int j){
    if(i < 0 || j < 0 || i >= x || j >= y || Land[i][j] != tmp)return;
    Land[i][j] = '.';
    cnt++;
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
}

int main(){
    int cs = 0;
    while(cin >> x >> y){
        if(!x && !y)return 0;
        memset(Letter, 0, sizeof(Letter));
        for(int i = 0; i < x; i++)cin >> Land[i];
        int ind = 0;
        for(int i = 0; i < x; i++){
            for(int j = 0; j < y; j++){
                if(Land[i][j] != '.'){
                    cnt = 0;
                    tmp = Letter[ind].c = Land[i][j];
                    dfs(i, j);
                    Letter[ind].cn = cnt;
                    ind++;
                }
            }
        }
        sort(Letter, Letter+ind, cmp);
        printf ("Problem %d:\n", ++cs);
        for(int j = 0; j < ind; j++)cout << Letter[j].c << " " << Letter[j].cn << endl;
    }
    return 0;
}

UVa - 785 - Grid Colouring

#include <bits/stdc++.h>
#define S 33
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

string Grid[S];
int len[S], ind, vis[S][S+50], vis2[S][S+50];
char tmp, tp;

void dfs2(int i, int j){
    if(i < 0 || j < 0 || i >= ind || j >= len[i] || vis2[i][j])return;
    if(Grid[i][j] != ' ' && Grid[i][j] != tp)return;
    vis2[i][j] = 1;
    Grid[i][j] = tp;
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs2(px, py);
    }
}

void dfs(int i, int j){
    if(i < 0 || j < 0 || i >= ind || j >= len[i] || vis[i][j])return;
    vis[i][j] = 1;
    if(Grid[i][j] != ' ' && Grid[i][j] != tmp){
        tp = Grid[i][j];
        dfs2(i, j);
    }
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
}

int main(){
    while(getline(cin, Grid[0])){
        ind = 1; len[0] = Grid[0].size();
        while(getline(cin, Grid[ind])){
            len[ind] = Grid[ind].size();
            if(Grid[ind][0] == '_')break;
            ind++;
        }
        memset(vis, 0, sizeof(vis));
        memset(vis2, 0, sizeof(vis2));
        for(int i = 0; i < ind; i++){
            for(int j = 0; j < len[i]; j++){
                if(Grid[i][j] != ' '){
                    tmp = Grid[i][j];
                    dfs(i, j);
                }
            }
        }
        for(int i = 0; i <= ind; i++){
            for(int j = 0; j < len[i]; j++){
                cout << Grid[i][j];
            }
            puts("");
        }
    }
    return 0;
}

UVa - 657 - The die is cast

#include <bits/stdc++.h>
#define scI(n) scanf("%d", &n)
#define scL(n) scanf("%lld", &n)
#define scS(n) scanf("%s", &n)
#define mn(n, m) (n > m)?m:n
#define mx(n, m) (n < m)?m:n
#define S 53
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

int n, m, tot;
string Die[S];
vector <int> Ans;

void dfs2(int i, int j){
    if(i < 0 || j < 0 || i >= m || j >= n)return;
    if(Die[i][j] != 'X')return;
    Die[i][j] = '.';
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs2(px, py);
    }
}

int dfs(int i, int j){
    if(i < 0 || j < 0 || i >= m || j >= n)return 0;
    if(Die[i][j] != '*' && Die[i][j] != 'X')return 0;
    if(Die[i][j] == '*')Die[i][j] = '.';
    if(Die[i][j] == 'X'){
        tot++;
        dfs2(i, j);
    }
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
    return tot;
}

int main(){
    int cs = 0;
    while(cin >> n >> m){
        if(!n && !m)return 0;
        for(int i = 0; i < m; i++)cin >> Die[i];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(Die[i][j] != '.'){
                    tot = 0;
                    Ans.push_back(dfs(i, j));
                }
            }
        }
        cout << "Throw " << ++cs << endl;
        sort(Ans.begin(), Ans.end());
        int sz = Ans.size();
        for(int i = 0; i < sz; i++){
            cout << Ans[i];
            if(i != sz-1)printf(" ");
        }
        puts("");
        puts("");
        Ans.clear();
    }
    return 0;
}

UVa - 10195 - The Knights Of The Round Table

#include <bits/stdc++.h>
#define scI(n) scanf("%d", &n)
#define scL(n) scanf("%lld", &n)
#define scS(n) scanf("%s", &n)
#define mn(n, m) (n > m)?m:n
#define mx(n, m) (n < m)?m:n
#define S 53
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

int main(){
    double a, b, c, p, ar, r;
    while(scanf("%lf %lf %lf", &a, &b, &c) == 3){
        if(!a || !b || !c){
            printf("The radius of the round table is: 0.000\n");
            continue;
        }
        p = (a+b+c)/2.0;
        ar = sqrt(p*(p-a)*(p-b)*(p-c));
        r = ar/p;
        printf("The radius of the round table is: %.3lf\n", r);
    }
    return 0;
}

UVa - 469 - Wetlands of Florida

#include <bits/stdc++.h>
#define scI(n) scanf("%d", &n)
#define scL(n) scanf("%lld", &n)
#define scS(n) scanf("%s", &n)
#define mn(n, m) (n > m)?m:n
#define mx(n, m) (n < m)?m:n
#define S 123
using namespace std;
typedef long long LL;

int dirX[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dirY[] = {0, 1, 0, -1, -1, 1, -1, 1};

int n, m, cnt, vis[S][S];
string WetLand[S];
string line;

int dfs(int i, int j){
    if(i < 0 || j < 0 || i >= n || j >= m || WetLand[i][j] == 'L' || vis[i][j])return 0;
    vis[i][j] = 1;
    cnt++;
    for(int z = 0; z < 8; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py)+1;
    }
    return cnt;
}

int main(){
    int t;
    bool sp = false;
    scI(t);
    getchar(); getchar();
    while(t--){
        n = 0, m = 0;
        if(sp)puts("");
        sp = true;
        while(getline(cin, line) && line.size() > 0){
            if(!line.size())break;
            if(line[0] == 'W' || line[0] == 'L'){
                if(!m)m = line.size();
                WetLand[n] = line;
                n++;
            }
            else{
                istringstream cinn(line);
                int x, y;
                cinn >> x; cinn >> y;
                cnt = 0;
                memset(vis, 0, sizeof(vis));
                cout << dfs(x-1, y-1) << endl;
            }
        }
    }
    return 0;
}

UVa - 11110 - Equidivisions

#include <bits/stdc++.h>
#define S 103
using namespace std;

int dirX[] = {1, 0, -1, 0};
int dirY[] = {0, 1, 0, -1};

int Equidivisions[S][S], n, cnt, r;

void dfs(int i, int j){
    if(i < 1 || j < 1 || i > n || j > n || Equidivisions[i][j] != r)return;
    cnt++;
    Equidivisions[i][j] = S;
    for(int z = 0; z < 4; z++){
        int px = i+dirX[z];
        int py = j+dirY[z];
        dfs(px, py);
    }
}

int main(){
    while(cin >> n){
        if(!n)return 0;
        memset(Equidivisions, 0, sizeof(Equidivisions));
        string inp;
        int x, y;
        getchar();
        for(int i = 1; i < n; i++){
            getline(cin, inp);
            istringstream cinn(inp);
            while(cinn >> x){
                cinn >> y;
                Equidivisions[x][y] = i;
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cnt = 0;
                if(Equidivisions[i][j] != S){
                    ans++;
                    r = Equidivisions[i][j];
                    dfs(i, j);
                    if(cnt == n)ans--;
                }
            }
        }
        puts((!ans)?"good":"wrong");
    }
    return 0;
}

UVa - 11244 - Counting Stars

#include <bits/stdc++.h>
#define S 103
using namespace std;

int n, m, f;
int xdir[] = {0, 1, 0, -1, 1, -1, 1, -1};
int ydir[] = {1, 0, -1, 0, 1, -1, -1, 1};
string globe[S];

int dfs(int i, int j){
    if(i < 0 || i >= n || j < 0 || j >= m || globe[i][j] == '.')return 0;
    globe[i][j] = '.';
    f++;
    for(int z = 0; z < 8; z++){
        int px = i+xdir[z];
        int py = j+ydir[z];
        dfs(px, py);
    }
    return f;
}

int main(){
    while(cin >> n >> m){
        if(!n && !m)return 0;
        for(int i = 0; i < n; i++)cin >> globe[i];
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                f = 0;
                if(globe[i][j] == '*'){
                    ans++;
                    if(dfs(i, j) != 1)ans--;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

UVa - 784 - Maze Exploration

#include <bits/stdc++.h>
#define S 33
using namespace std;


string maze[S];
int len[S], n, m;
int xdir[] = {0, 1, 0, -1};
int ydir[] = {1, 0, -1, 0};

void dfs(int i, int j){
    if(i < 0 || i >= m || j < 0 || j >= n || (maze[i][j] != ' ' && maze[i][j] != '*'))return;
    if(maze[i][j] == '*' || maze[i][j] == 32)maze[i][j] = '#';
    for(int z = 0; z < 4; z++){
        int px = i+xdir[z];
        int py = j+ydir[z];
        dfs(px, py);
    }
}

int main(){
    int t;
    cin >> t;
    getchar();
    while(t--){
        int i = 0;
        n = -1;
        while(getline(cin, maze[i])){
            len[i] = maze[i].size();
            n = max(n, len[i]);
            if(maze[i][0] == '_')break;
            i++;
        }
        m = i;
        int f = 0;
        for(int k = 0; k < i; k++){
            int nn = n-len[k];
            while(nn--)maze[k].push_back('_');
        }
        for(int k = 0; k < i; k++)
            for(int j = 0; j < n; j++)if(maze[k][j] == '*')dfs(k, j);
        for(int k = 0; k < i; k++){
            for(int j = 0; j < n; j++){
                if(maze[k][j] == '_')break;
                cout << maze[k][j];
            }
            puts("");
        }
        cout << maze[i] << endl;
    }
    return 0;
}

UVa - 10986 - Sending email

#include <bits/stdc++.h>
#define S 20003
using namespace std;

struct node{
    int e, w;
    node(int a, int b){
        e = a, w = b;
    }
    bool operator < (const node& p) const{
        return w > p.w;
    }
};

vector <int> route[S], cost[S];
int src, dest, dis[S];

void djkstra(){
    dis[src] = 0;
    priority_queue <node> PQ;
    PQ.push(node(src, 0));
    while(!PQ.empty()){
        node ED = PQ.top();
        int u = ED.e;
        PQ.pop();
        if(u == dest){
            cout << dis[dest] << endl;
            return;
        }
        int sz = route[u].size();
        for(int i = 0; i < sz; i++){
            int v = route[u][i];
            if(dis[u] + cost[u][i] < dis[v]){
                dis[v] = dis[u] + cost[u][i];
                PQ.push(node(v, dis[v]));
            }
        }
    }
    puts("unreachable");
}

int main(){
    int N, n, m, s, t, x, y, z, cs = 0;
    cin >> N;
    while(N--){
        cin >> n >> m >> s >> t;
        for(int i = 0; i < n; i++)dis[i] = INT_MAX;
        src = (s <= t)? s : t;
        dest = (s >= t)? s : t;
        for(int i = 1; i <= m; i++){
            cin >> x >> y >> z;
            route[x].push_back(y);
            route[y].push_back(x);
            cost[x].push_back(z);
            cost[y].push_back(z);
        }
        cout << "Case #" << ++cs << ": ";
        djkstra();
        for(int i = 0; i < n; i++)cost[i].clear(), route[i].clear();
    }
    return 0;
}

UVa - 10370 - Above Average

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    float x[10000], res, avg, count, ans;
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        res = 0;count = 0;
        for(int i = 1; i <= n; i++){
            cin >> x[i];
            res = res + x[i];
        }
        avg = res / n;
        for(int i = 1; i <= n; i++){
        if(avg < x[i])count++;
        }
        ans = (count / n) * 100;
        printf("%.3f%%", ans);
    }
    return 0;
}

UVa - 10347 - Medians

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main(){
    double a, b, c, s, ans;
    while(cin >> a >> b >> c){
        s = (a+b+c) / 2;
        ans = (4 * sqrt(s*(s-a)*(s-b)*(s-c))) / 3;
        if(ans > 0 )cout << fixed << setprecision(3) << ans << endl;
        else cout << "-1.000" << endl;
    }
    return 0;
}

UVa - 10346 - Peter's Smokes

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    long long x, y, ans;
    while(cin >> x >> y){
        ans = x;
        while(x >= y){
            ans = ans + x / y;
            x = x % y + x / y;
        }
        cout << ans << endl;
    }
    return 0;
}

UVa - 10344 - 23 out of 5

#include <bits/stdc++.h>
using namespace std;

vector <int> numbers;
int flag, visited[7];

void call(int curr, int sum){
    if(sum == 23 && curr == 5){
        printf("Possible\n");
        flag = 1;
        return;
    }
    for(int index = 0; index < 5; index++){
        if(flag)break;
        if(!visited[index]){
            visited[index] = 1;
            call(curr+1, sum+numbers[index]);
            call(curr+1, sum-numbers[index]);
            call(curr+1, sum*numbers[index]);
            visited[index] = 0;
        }
    }
}

int main(){
    int n, f = 0;
    while(1){
        for(int i = 0; i < 5; i++){
            scanf("%d", &n), numbers.push_back(n);
            if(n == 0)f++;
        }
        if(f == 5)break;
        memset(visited, 0, sizeof(visited));
        flag = 0;
        for(int i = 0; i < 5; i++){
            visited[i] = 1;
            call(1, numbers[i]);
            visited[i] = 0;
        }
        if(!flag)printf("Impossible\n");
        numbers.clear();
    }
    return 0;
}

UVa - 10336 - Rank the Languages

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int row, col;
char grid[1003][1003];

void dfs(int i, int j, char src){
    if(i < 0 || i >= row || j < 0 || j >= col)return;
    if(grid[i][j] != src)return;
    if(grid[i][j] == '.')return;
    if(grid[i][j] >= 'a' && grid[i][j] <= 'z')grid[i][j] = '.';
    dfs(i, j+1, src);
    dfs(i+1, j, src);
    dfs(i, j-1, src);
    dfs(i-1, j, src);
}

int main(){
    int cnt[27], t, cs = 0;
    cin >> t;
    while(t--){
        cin >> row >> col;
        memset(cnt, 0, sizeof(cnt));
        getchar();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                cin >> grid[i][j];
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++){
                if(grid[i][j] >= 'a' && grid[i][j] <= 'z'){
                    char src = grid[i][j];
                    cnt[grid[i][j]-97]++;
                    dfs(i, j, src);
                }
            }
        cout << "World #" << ++cs << endl;
        int mx = -1, mp;
        for(int i = 0; i < 27 ; i++){
            mx = -1;
            for(int j = 0; j < 27; j++)
                if(cnt[j] > mx)mx = cnt[j], mp = j;
            cnt[mp] = 0;
            if(mx)printf("%c: %d\n", mp+97, mx);
            if(mx == 0)break;
        }
    }
    return 0;
}

UVa - 10324 - Zeros and Ones

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

int main(){
    string ques;
    int cs = 1;
    while(getline(cin, ques)){
        int n, i, j, mn, mx;
        cin >> n;
        cout << "Case " << cs << ":" << endl;
        for(int m = 1; m <= n; m++){
            cin >> i >> j;
            int l = 0, o = 0;
            mn = min(i, j), mx = max(i, j);
            for(int k = mn; k <= mx; k++){
                if(ques[k] == '0')o++;
                else l++;
            }
            if(o == 0 || l == 0)cout << "Yes" << endl;
            else cout << "No" << endl;
        }cs++;
        getchar();
    }
    return 0;
}

UVa - 10323 - Factorial! You Must be Kidding!!!

#include<cstdio>

using namespace std;

int main(){
    int n;

    while(scanf("%d",&n)==1){
        if((n>=0 && n<=7) || (n<0 && n%2==0)) printf("Underflow!\n");
        else if(n==8) printf("40320\n");
        else if(n==9) printf("362880\n");
        else if(n==10) printf("3628800\n");
        else if(n==11) printf("39916800\n");
        else if(n==12) printf("479001600\n");
        else if(n==13) printf("6227020800\n");
        else printf("Overflow!\n");
    }

    return 0;
}

UVa - 10300 - Ecological Premium

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    long long r, a, b, c, t, f, i, h;
    while(scanf("%lld", &t) == 1){
        for(h = 1; h <= t; h++){
                r = 0;
                scanf("%lld", &f);
                for(i = 1; i <= f; i++){
                    scanf("%lld %lld %lld", &a, &b, &c);
                    r += (a * c);
                    }
                    printf("%lld\n", r);
    }
    }
    return 0;
}

UVa - 10293 - Word Length and Frequency

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;

int main(){
    string text;
    int cnt[1000], cn = 0, hyp;memset(cnt, 0, sizeof(cnt));
    while(getline(cin, text)){
        if(text == "#"){
            for(int i = 0; i < 1000; i++)if(cnt[i] > 0)cout << i << " " << cnt[i] << endl;
            memset(cnt, 0, sizeof(cnt)), cn = 0;
            cout << endl;
        }
        else{
            int sz = text.size();
            for(int i = 0; i < sz; i++){
                if(text[i] == '-')hyp = 1;
                else if((text[i] >= 'A' && text[i] <= 'Z') || (text[i] >= 'a' && text[i] <= 'z'))cn++, hyp = 0;
                else if(text[i] == '\'' || text[i] == '-')cn *= 1;
                else{
                    if(cn > 0 && hyp == 0)cnt[cn]++, cn = 0;
                }
                if(hyp == 0 && cn > 0 && i == sz-1)cnt[cn]++, cn = 0;
            }
        }
    }
    return 0;
}

UVa - 10282 - Babelfish

#include <iostream>
#include <algorithm>
#include <sstream>
#include <map>
#include <vector>
using namespace std;

int main(){
    int t, n;
    string first, second, input, word;
    map <string, string> diction;
    while(getline(cin, input) && input.size()){
        stringstream io;
        io << input;
        io >> first >> second;
        diction[second] = first;
    }
    while(cin >> word){
        if(diction.count(word))cout << diction[word] << endl;
        else cout << "eh" << endl;
    }

    return 0;
}

UVa - 10260 - Soundex

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    string input;
    while(cin >> input){
        int B = 0, C = 0, D = 0, M = 0, L = 0, R = 0;
        int sz = input.size();
        for(int i = 0; i < sz; i++){
            if((input[i] == 'B' || input[i] == 'F' || input[i] == 'P' || input[i] == 'V') && B == 0){
                cout << 1, B = 1, C = 0, D = 0, M = 0, L = 0, R = 0;
            }
            if((input[i] == 'C' || input[i] == 'G' || input[i] == 'J' || input[i] == 'K') && C == 0){
                cout << 2, B = 0, C = 1, D = 0, M = 0, L = 0, R = 0;
            }
            if((input[i] == 'Q' || input[i] == 'S' || input[i] == 'X' || input[i] == 'Z') && C == 0){
                cout << 2, B = 0, C = 1, D = 0, M = 0, L = 0, R = 0;
            }
            if((input[i] == 'D' || input[i] == 'T') && D == 0)cout << 3, B = 0, C = 0, D = 1, M = 0, L = 0, R = 0;

            if((input[i] == 'M' || input[i] == 'N') && M == 0)cout << 5, B = 0, C = 0, D = 0, M = 1, L = 0, R = 0;

            if(input[i] == 'L' && L == 0)cout << 4, B = 0, C = 0, D = 0, M = 0, L = 1, R = 0;

            if(input[i] == 'R' && R == 0)cout << 6, B = 0, C = 0, D = 0, M = 0, L = 0, R = 1;

            if(input[i] == 'A' || input[i] == 'E' || input[i] == 'I' || input[i] == 'O')
                B = 0, C = 0, D = 0, M = 0, L = 0, R = 0;

            if(input[i] == 'U' || input[i] == 'H' || input[i] == 'W' || input[i] == 'Y')
                B = 0, C = 0, D = 0, M = 0, L = 0, R = 0;
        }
        cout << endl;
    }
    return 0;
}

UVa - 10252 - Common Permutation

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    string first, second;
    int cnt1[26], cnt2[26];
    while(getline(cin, first) && getline(cin, second)){
        memset(cnt1, 0, sizeof(cnt1));
        memset(cnt2, 0, sizeof(cnt2));
        int sz1 = first.size(), sz2 = second.size();
        for(int i = 0; i < sz1; i++)cnt1[first[i]-97]++;
        for(int i = 0; i < sz2; i++)cnt2[second[i]-97]++;
        for(int i = 0; i < 26; i++)
            if(cnt1[i] > 0 && cnt2[i] > 0){
                if(cnt1[i] < cnt2[i])for(int j = 1; j <= cnt1[i]; j++)printf("%c", i+97);
                else for(int j = 1; j <= cnt2[i]; j++)printf("%c", i+97);
            }
        cout << endl;
    }
    return 0;
}

UVa - 10222 - Decode the Mad man

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int main(){
    char s[10015];
    int i;
    gets(s);
        for(i = 0; s[i]; i++){
            if(s[i] == 'A')printf("[");
            if(s[i] == ' ')printf(" ");
            if(s[i] == 'E')printf("q");
            if(s[i] == 'R')printf("w");
            if(s[i] == 'T')printf("e");
            if(s[i] == 'Y')printf("r");
            if(s[i] == 'U')printf("t");
            if(s[i] == 'I')printf("y");
            if(s[i] == 'O')printf("u");
            if(s[i] == 'P')printf("i");
            if(s[i] == '[')printf("o");
            if(s[i] == ']')printf("p");
            if(s[i] == 'S')printf("]");
            if(s[i] == 'D')printf("a");
            if(s[i] == 'F')printf("s");
            if(s[i] == 'G')printf("d");
            if(s[i] == 'H')printf("f");
            if(s[i] == 'J')printf("g");
            if(s[i] == 'K')printf("h");
            if(s[i] == 'L')printf("j");
            if(s[i] == ';')printf("k");
            if(s[i] == '\'')printf("l");
            if(s[i] == 'X')printf("\\");
            if(s[i] == 'C')printf("z");
            if(s[i] == 'V')printf("x");
            if(s[i] == 'B')printf("c");
            if(s[i] == 'N')printf("v");
            if(s[i] == 'M')printf("b");
            if(s[i] == ',')printf("n");
            if(s[i] == '.')printf("m");
            if(s[i] == '/')printf(",");
            if(s[i] == 'Z')printf("'");
            if(s[i] == 'a')printf("[");
            if(s[i] == 'e')printf("q");
            if(s[i] == 'r')printf("w");
            if(s[i] == 't')printf("e");
            if(s[i] == 'y')printf("r");
            if(s[i] == 'u')printf("t");
            if(s[i] == 'i')printf("y");
            if(s[i] == 'o')printf("u");
            if(s[i] == 'p')printf("i");
            if(s[i] == 's')printf("]");
            if(s[i] == 'd')printf("a");
            if(s[i] == 'f')printf("s");
            if(s[i] == 'g')printf("d");
            if(s[i] == 'h')printf("f");
            if(s[i] == 'j')printf("g");
            if(s[i] == 'k')printf("h");
            if(s[i] == 'l')printf("j");
            if(s[i] == 'x')printf("\\");
            if(s[i] == 'c')printf("z");
            if(s[i] == 'v')printf("x");
            if(s[i] == 'b')printf("c");
            if(s[i] == 'n')printf("v");
            if(s[i] == 'm')printf("b");
            if(s[i] == 'z')printf("'");
        }
        printf("\n");
    return 0;
}

UVa - 10189 - Minesweeper

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <map>
#include <vector>
using namespace std;

int main(){
    int row, col, cs = 0, blank = 0;
    while(cin >> row >> col){
        if(!row && !col)break;
        int cnt[row+3][col+3];
        memset(cnt, 0, sizeof(cnt));
        char input;
        getchar();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++){
                cin >> input;
                if(input == '*'){
                    cnt[i][j] = -3;
                    if(cnt[i+1][j] != -3)cnt[i+1][j]++;
                    if(cnt[i][j+1] != -3)cnt[i][j+1]++;
                    if(cnt[i-1][j] != -3)cnt[i-1][j]++;
                    if(cnt[i][j-1] != -3)cnt[i][j-1]++;
                    if(cnt[i+1][j+1] != -3)cnt[i+1][j+1]++;
                    if(cnt[i-1][j-1] != -3)cnt[i-1][j-1]++;
                    if(cnt[i+1][j-1] != -3)cnt[i+1][j-1]++;
                    if(cnt[i-1][j+1] != -3)cnt[i-1][j+1]++;
                }
            }
        if(blank)cout << endl;
        cout << "Field #" << ++cs << ":" << endl;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(cnt[i][j] == -3)cout << "*";
                else cout << cnt[i][j];
            }cout << endl;
        }blank = 1;
    }
    return 0;
}

UVa - 10170 - The Hotel with Infinite Rooms

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    long long S, D, Sum, temp;
    while(cin >> S >> D){
        Sum = 0, temp = S;
        while(1){
            Sum += S;
            S += 1;
            if(Sum >= D)break;
        }
        long long ans = S-1;
        cout << ans << endl;
    }
    return 0;
}

UVa - 10168 - Summation of Four Primes

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#define M 10000000
using namespace std;
bool prime[M];
int main(){
    for(int i = 2; i <= sqrt(M); i++)
        if(prime[i] == 0)
            for(int j = i+i; j <= M; j += i)prime[j] = 1;

    int n;
    while(cin >> n){
        if(n == 0)break;
        int m = 0, x, y;
        if(n < 8)cout << "Impossible." << endl;
        else{
            if(n % 2 == 0){
                cout << 2 << " " << 2 << " ";
                n -= 4;
            }
            if(n % 2 == 1){
                cout << 2 << " " << 3 << " ";
                n -= 5;
            }
            for(int j = 2; j < n; j++)
                if(!prime[j] && !prime[n-j]){
                    x = j;y = (n-j);
                    m = 1;
                    break;
                }
            if(m)cout << x << " " << y << endl;
        }
    }

    return 0;
}

UVa - 10130 - SuperSale

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int N, MW, dp[1003][33];
vector <int> Price, Weight;

int maxValue(int I, int W){
    if(I == N)return 0;
    int Price1, Price2;
    if(dp[I][W] != -1)return dp[I][W];
    if(W+Weight[I] <= MW)Price1 = Price[I] + maxValue(I+1, W+Weight[I]);
    else Price1 = 0;
    Price2 = maxValue(I+1, W);
    return dp[I][W] = max(Price1, Price2);
}

int main(){
    int T, P, W, G;
    cin >> T;
    while(T--){
        cin >> N;
        for(int i = 1; i <= N; i++)cin >> P >> W, Price.push_back(P), Weight.push_back(W);
        cin >> G;
        int ans = 0;
        for(int i = 0; i < G; i++)memset(dp, -1, sizeof(dp)), cin >> MW, ans += maxValue(0, 0);
        cout << ans << endl;
        Price.clear(), Weight.clear();
    }
    return 0;
}

UVa - 10127 - Ones

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int n, mul, ans;
    while(~scanf("%d", &n)){
        int mod = 1;
        for(int i = 1; ; i++){
            mod = (((mod%n) * (10%n))%n + 1)%n;
            if(!mod){
                ans = i+1;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

UVa - 10107 - What is the Median

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    vector <int> container;
    while(scanf("%d", &n) == 1){
        container.push_back(n);
        sort(container.begin(), container.end());
        int sz = container.size();
        if(sz%2 == 0)cout << (container[sz/2]+container[(sz/2)-1])/2 << endl;
        else cout << container[sz/2] << endl;
    }
    return 0;
}

UVa - 10070 - Leap Year or Not Leap Year

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    char years[10000];
    int mod_4, mod_15, mod_55, mod_100, mod_400, space = 0;
    freopen("in.txt", "r", stdin);
    while(scanf("%s", years) == 1){
        mod_4 = mod_15 = mod_55 = mod_100 = mod_400 = 0;
        int l = strlen(years), b = 0, h = 0, bl = 0;
        for(int i = 0; i < l; i++){
            mod_4 = ((mod_4*10) + (years[i]-48)) % 4;
            mod_15 = ((mod_15*10) + (years[i]-48)) % 15;
            mod_55 = ((mod_55*10) + (years[i]-48)) % 55;
            mod_100 = ((mod_100*10) + (years[i]-48)) % 100;
            mod_400 = ((mod_400*10) + (years[i]-48)) % 400;
        }
        if(space != 0)cout << endl;
        if((mod_4 == 0 && mod_100 != 0) || mod_400 == 0){
            puts("This is leap year.");
            b = 1;
        }
        if(mod_15 == 0){
            puts("This is huluculu festival year.");
            h = 1;
        }
        if(mod_55 == 0 && b){
            puts("This is bulukulu festival year.");
            bl = 1;
        }
        if(!h && !b && !bl)puts("This is an ordinary year.");
        space = 1;
    }
    return 0;
}

UVa - 10050 - Hartals

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int main(){
    vector <int> hartal;
    int test, days, party, h, hart[3653];
    cin >> test;
    while(test--){
        cin >> days >> party;
        memset(hart, 0, sizeof(hart));
        for(int i = 1; i <= party; i++){
            cin >> h;
            for(int j = h; j <= days; j += h)hart[j]++;
        }
        for(int i = 1; i <= days; i++)if(hart[i] != 0)hartal.push_back(i);
        int l = hartal.size(), ans = 0;
        for(int i = 0; i < l; i++)if(hartal[i] % 7 != 0 && hartal[i] % 7 != 6)ans++;
        cout << ans << endl;
        hartal.clear();
    }
    return 0;
}

UVa - 10041 - Vito's Family

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t, n, m, mn, x, ans;
    vector <int> street;
    cin >> t;
    while(t--){
        cin >> n, x = n, mn = 2111111111;
        while(n--)cin >> m, street.push_back(m);
        for(int i = 0; i < x; i++){
             ans = 0;
            for(int j = 0; j < x; j++)ans += abs(street[i] - street[j]);
            if(ans < mn)mn = ans;
        }
        cout << mn << endl;
        street.clear();
    }
    return 0;
}

UVa - 10009 - All Roads Lead Where

#include <bits/stdc++.h>
#define L 103
using namespace std;

vector <int> City[L];
int Vis[L], Path[L];
map <string, int> M;
map <int, char> M1;

void print_path(int v, int u){
    int p = Path[v];
    if(p != u)print_path(p, u);
    cout << M1[p];
}

void BFS(int src, int dest){
    queue <int> Q;
    Vis[src] = 1;
    Q.push(src);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        int sz = City[u].size();
        for(int i = 0; i < sz; i++){
            int v = City[u][i];
            if(!Vis[v]){
                Vis[v] = 1;
                Q.push(v);
                Path[v] = u;
            }
        }
    }
    print_path(dest, src);
    cout << M1[dest] << endl;
}

int main(){
    int test, n, q, f = 0;
    string start, endd;
    cin >> test;
    while(test--){
        cin >> n >> q;
        int k = 1;
        for(int i = 1; i <= n; i++){
            cin >> start >> endd;
            if(!M[start])M[start] = k, M1[k] = start[0], k++;
            if(!M[endd])M[endd] = k, M1[k] = endd[0], k++;
            City[M[start]].push_back(M[endd]);
            City[M[endd]].push_back(M[start]);
        }
        if(f)puts(""); f = 1;
        for(int i = 1; i <= q; i++){
            cin >> start >> endd;
            memset(Path, -1, sizeof(Path));
            memset(Vis, 0, sizeof(Vis));
            BFS(M[start], M[endd]);
        }
        M.clear(), M1.clear();
        for(int i = 1; i < k; i++)City[i].clear();
    }
    return 0;
}

UVa - 10008 - What's Cryptanalysis

#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main(){
    int i, n, j, cnt[30], ans[30];
    string input;
    char c;
    while(cin >> n){
        getchar();
        memset(cnt, 0, sizeof(cnt));
        memset(ans, 0, sizeof(ans));
        for(i = 0; i < n; i++){
            getline(cin, input);
            for(j = 0; input[j]; j++){
                if(input[j] >= 97 && input[j] <= 122){
                    cnt[input[j]-97]++;
                    ans[input[j]-97]++;
                }
                else if(input[j] >= 65 && input[j] <= 90){
                    cnt[input[j]-65]++;
                    ans[input[j]-65]++;
                }

            }
        }
        sort(ans, ans+26);
        for(i = 25; i >= 0; i--){
            if(ans[i] != 0){
                for(j = 0; j < 26; j++){
                    if(ans[i] == cnt[j]){
                        printf("%c %d\n", (j+65), cnt[j]);
                        cnt[j] = 0;
                    }
                }
            }


        }
    }
    return 0;
}

UVa - 10006 - Carmichael Numbers

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#define mx 65000
using namespace std;
bool sample[mx];
int main(){
    for(int i = 2; i <= sqrt(mx); i++)
        if(sample[i] == 0)
            for(int j = i+i; j < mx; j += i)sample[j] = 1;
    int number;
    while(scanf("%d", &number) == 1){
        if(number == 0)break;
        int cnt = 0;
        for(int i = 2; i < mx; i++){
            if((sample[i] == 0) && (number % i == 0))
                if((number-1) % (i-1) == 0)cnt++;
            if(cnt == 3)break;
        }
        if(cnt == 3)printf("The number %d is a Carmichael number.\n", number);
        else printf("%d is normal.\n", number);
    }

    return 0;
}

UVa - 10004 - Bicoloring

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector <int> node[203];
int red[203], green[203];
void bfs(int src){
    memset(red, 0, sizeof(red));
    memset(green, 0, sizeof(green));
    queue <int> container;
    container.push(src);
    int flag = 0;
    int visited[203] = {0};
    while(!container.empty()){
        int u = container.front();
        visited[u] = 1;
        for(int i = 0; i < node[u].size(); i++){
            int v = node[u][i];
            if(red[u] == 0){
                if(green[u] == 0)red[u] = 1;
            }
            if(red[u] == 1){
                if(red[v] == 0 && green[v] == 0)green[v] = 1;
            }
            if(green[u] == 1){
                if(red[v] == 0 && green[v] == 0)red[v] = 1;
            }

            if(red[u] == 1 && red[v] == 1)flag = 1;
            if(green[u] == 1 && green[v] == 1)flag = 1;

            if(!visited[v]){
                visited[v] = 1;
                container.push(v);
            }
        }
        container.pop();
    }
    if(flag == 1)cout << "NOT BICOLORABLE." << endl;
    else cout << "BICOLORABLE." << endl;
}

int main(){
    int N, E, x, y;
    while(cin >> N ){
        if(N == 0)break;
        cin >> E;
        for(int i = 0; i < E; i++)cin >> x >> y,node[x].push_back(y), node[y].push_back(x);
        bfs(x);
        for(int i = 0; i <= N; i++)node[i].clear();
    }
    return 0;
}

UVa - 10003 - Cutting Sticks

#include <bits/stdc++.h>
using namespace std;

vector <int> cut;
int dp[53][53];

int cutting_sticks(int x, int y){
    int sum, mn;
    if(x+1 == y)return 0;
    if(dp[x][y] != -1)return dp[x][y];
    mn = 111111111;
    for(int i = x+1; i < y; i++){
        sum = cutting_sticks(x, i) + cutting_sticks(i, y) + (cut[y]-cut[x]);
        mn = min(mn, sum);
    }
    dp[x][y] = mn;
    return dp[x][y];
}

int main(){
    int stick, piece, length;
    while(cin >> stick){
        if(!stick)break;
        cut.clear();
        memset(dp, -1, sizeof(dp));
        cut.push_back(0);
        cin >> piece;
        for(int i = 1; i <= piece; i++)cin >> length, cut.push_back(length);
        cut.push_back(stick);
        int sz = cut.size()-1;
        int ans = cutting_sticks(0, sz);
        cout << "The minimum cutting is " << ans << "." << endl;
    }
    return 0;
}

UVa - 1586 - Molar mass

#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int t;
    double c, h, o, n;
    string molecule;
    vector <char> container;
    cin >> t;
    getchar();
    while(t--){
        double cf = 12.01, hf = 1.008, of = 16.00, nf = 14.01, cc, hh, oo, nn;
        c = 0, h = 0, o = 0, n = 0;
        cin >> molecule;
        int sz = molecule.size();
        for(int i = 0; i < sz;){
                int j = i+1;
            if(molecule[i] =='C' || molecule[i] =='H' || molecule[i] =='O' || molecule[i] =='N'){
                while(molecule[j] >= '0' && molecule[j] <= '9')container.push_back(molecule[j]), j++;
                int sz1 = container.size();
                double sum = 0;
                for(int k = 0; k < sz1; k++)sum = (sum*10) + (container[k]-48);
                container.clear();
                if(sum == 0)sum = 1;
                if(molecule[i] == 'C')cc = cf*sum, c += cc;
                if(molecule[i] == 'H')hh = hf*sum, h += hh;
                if(molecule[i] == 'O')oo = of*sum, o += oo;
                if(molecule[i] == 'N')nn = nf*sum, n += nn;
                i = j;
            }
        }
        cout << fixed << setprecision(3) << c+h+n+o << endl;
    }
    return 0;
}

UVa - 1585 - Score

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int main(){
    int t, sum, cnt;
    string input;
    cin >> t;
    getchar();
    while(t--){
        cin >> input;
        int sz = input.size();
        sum = 0, cnt = 0;
        for(int i = 0; i < sz; i ++){
            if(input[i] == 'O')cnt++, sum += cnt;
            else cnt = 0;
        }
        cout << sum << endl;
    }
    return 0;
}

UVa - 1583 - Digit Generator

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int t, num, lower, sub, sum, temp, n, ans;
    cin >> t;
    string number;
    getchar();
    while(t--){
        cin >> number;
        num = 0;
        int sz = number.size();
        for(int i = 0; i < sz; i++)num = (num*10) + (number[i]-48);
        sub = 9 * sz, lower = num - sub;
        int flag = 0;
        for(int i = lower; i < num; i++){
            sum = i, temp = i;
            while(temp > 0){
                n = temp % 10;
                sum += n;
                temp /= 10;
            }
            if(sum == num){flag = 1, ans = i;break;}
        }
        if(flag)cout << ans << endl;
        else cout << 0 << endl;
    }
    return 0;
}

UVa - 1230 - MODEX

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
long long m;
long long Modex(long long b, long long p){
    if(p == 0)return 1;
    if(p % 2 == 0)
        return ((Modex(b, p / 2)) * (Modex(b, p / 2))) % m;
    else
        return (b * Modex(b, p - 1)) % m;
}
int main(){
    long long b, p;
    int t;
    while(scanf("%d", &t)){
        if(!t)break;
        for(int i = 0; i < t; i++){
            scanf("%lld %lld %lld", &b, &p, &m);
            printf("%lld\n", Modex(b, p));
        }
    }
    return 0;
}

UVa - 1213 - Sum of Different Primes

#include <bits/stdc++.h>
using namespace std;

vector <int> Primes;
int Prime[1160], dp[1133][17][193];
int N;

void sieve(){
    int sqr = sqrt(1156);
    for(int i = 2; i <= sqr; i++){
        if(!Prime[i])
        for(int j = i*i; j <= 1156; j += i){
            Prime[j] = 1;
        }
    }
}

int sum_dif_prime(int n, int k, int ind){
    if(!k || n <= 0 || Primes[ind] > N){
        if(!k && !n)return 1;
        return 0;
    }
    if(n > 0 && !k)return 0;
    if(dp[n][k][ind] != -1)return dp[n][k][ind];
    dp[n][k][ind] = sum_dif_prime(n-Primes[ind], k-1, ind+1) + sum_dif_prime(n, k, ind+1);
    return dp[n][k][ind];
}

int main(){
    sieve();
    for(int i = 2; i <= 1156; i++)if(!Prime[i])Primes.push_back(i);
    int K;
    while(cin >> N >> K){
        if(!N && !K)break;
        memset(dp, -1, sizeof(dp));
        int ans = sum_dif_prime(N, K, 0);
        cout << ans << endl;
    }
    return 0;
}

UVa - 1124 - Celebrity jeopardy

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    while(getline(cin, s))cout << s << endl;
    return 0;
}

UVa - 913 - Joana and the Odd Numbers

#include <iostream>
using namespace std;

int main(){
    long long n, sum, con, ans, p, m, o;
    while(cin >> n){
        p = (n - 1) / 2;
        m = p* (p+1);
        o = (n * (n+1)) / 2;
        sum = o - m;
        con = (sum*2) - 1;
        ans = con + (con - 2) + (con - 4);
        cout << ans << endl;
    }
    return 0;
}

UVa - 793 - Network Connections

#include <bits/stdc++.h>
#define L 100003
using namespace std;

int RP[L];

int find_set(int n){
    if(RP[n] == n)return n;
    return RP[n] = find_set(RP[n]);
}

void merge_set(int p, int q){
    int u = find_set(p);
    int v = find_set(q);
    if(u != v)RP[v] = u;
}

int main(){
    int n, x, y, t, sp = 0;
    char check[L], q;
    cin >> t;
    while(t--){
        cin >> n;
        int yes = 0, no = 0;
        for(int i = 1; i <= n; i++)RP[i] = i;
        getchar();
        while(true){
            gets(check);
            if(strcmp(check, "") == 0 || feof(stdin))break;
            sscanf(check, "%c %d %d", &q, &x, &y);
            if(q == 'c')merge_set(x, y);
            else{
                (find_set(x) == find_set(y)) ? yes++ : no++;
            }
        }
        if(sp)puts(""); sp = 1;
        cout << yes << "," << no << endl;
    }
    return 0;
}

UVa - 762 - We Ship Cheap

#include <bits/stdc++.h>
using namespace std;

vector <int> routes[100003];
vector <string> ans;
int path[100003], vis[100003], kk;
map <int, string> M1;

void print_path(int v, int u){
    int p = path[v];
    kk++;
    if(p != u)print_path(p, u);
    ans.push_back(M1[p]);
}

void BFS(int src, int dest){
    queue <int> Q;
    vis[src] = 1;
    Q.push(src);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        int sz = routes[u].size();
        for(int i = 0; i < sz; i++){
            int v = routes[u][i];
            if(!vis[v]){
                vis[v] = 1;
                path[v] = u;
                Q.push(v);
            }
        }
    }kk = 0;
    if(path[dest] == -1)puts("No route");
    else print_path(dest, src), ans.push_back(M1[dest]);
    int szz = ans.size();
    if(path[dest] != -1){
        for(int i = 0; i < szz-1; i++)cout << ans[i] << " " << ans[i+1] << endl;
    }
}

int main(){
    int n, tmp, f = 0;
    string start, endd;
    while(cin >> n){
        map <string, int> M;
        int k = 1;
        for(int i = 1; i <= n; i++){
            cin >> start >> endd;
            if(!M[start])M[start] = k, M1[k] = start, k++;
            if(!M[endd])M[endd] = k, M1[k] = endd; k++;
            routes[M[start]].push_back(M[endd]);
            routes[M[endd]].push_back(M[start]);
        }
        cin >> start >> endd;
        memset(path, -1, sizeof(path));
        memset(vis, 0, sizeof(vis));
        if(f)puts("");
        BFS(M[start], M[endd]);
        for(int i = 1; i <= n; i++)routes[i].clear();
        M.clear(), M1.clear();
        ans.clear();
        f = 1;
    }
    return 0;
}

UVa - 674 - Coin Change

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int Coin[] = {1, 5, 10, 20, 25};
int dp[7][7493];

int makeCoin(int I, int H){
    if(I >= 5){
        if(!H)return 1;
        else return 0;
    }
    if(dp[I][H] != -1)return dp[I][H];
    int Way1 = 0, Way2 = 0;
    if(H-Coin[I] >= 0)Way1 = makeCoin(I, H-Coin[I]);
    Way2 = makeCoin(I+1, H);
    cout << Way1 << " " << Way2 << " I = " << I << " H = " << H << endl;
    return dp[I][H] = Way1+Way2;
}

int main(){
    int N;
    memset(dp, -1, sizeof(dp));
    while(cin >> N){
        cout << makeCoin(0, N) << endl;
    }
    return 0;
}

UVa - 673 - Parentheses Balance

#include <iostream>
#include <cstdio>
#include <string>
#include <stack>
#include <cstring>
using namespace std;

int main(){
    int n;
    string input;
    cin >> n;
    getchar();
    while(n--){
        stack <char> container;
        getline(cin, input);
        if(!input.size()){
            cout << "Yes" << endl;continue;
        }
        if(input.size()%2){
            cout << "No" << endl;continue;
        }
        int flag = 0, sz = input.size();
        for(int i = 0; i < sz; i++){
            if(input[i] == '(' || input[i] == '[')container.push(input[i]);
            else if(!container.empty() && (input[i] == ']' && container.top() == '['))container.pop();
            else if(!container.empty() && (input[i] == ')' && container.top() == '('))container.pop();
            else{
                flag = 1;break;
            }
        }
        if(!flag && container.empty())cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

UVa - 671 - Spell checker

#include <bits/stdc++.h>
using namespace std;

struct data{
    int sz;
    string word;
}dic[10003];

int main(){
    string words;
    int t;
    map <string, int> M;
    cin >> t;
    while(t--){
        M.clear();
        int i = 0;
        for(i = 0; ; i++){
            cin >> words;
            if(words == "#")break;
            M[words] = 1;
            dic[i].word = words;
            dic[i].sz = words.size();
        }
        for(int j = 0; ; j++){
            cin >> words;
            if(words == "#")break;
            if(M[words]){
                cout << words << " is correct" << endl;
                continue;
            }
            int szz = words.size();
            cout << words <<":";
            for(int k = 0; k < i; k++){
                int cn;
                if(szz == dic[k].sz){
                    cn = 0;
                    for(int m = 0; m < szz; m++){
                        if(words[m] != dic[k].word[m]){
                            cn++;
                        }
                    }
                    if(cn <= 1)cout << " " << dic[k].word;
                }
                else if(abs(szz-dic[k].sz) == 1){
                    if(szz > dic[k].sz){
                        cn = 0;
                        for(int m = 0, n = 0; m < szz; m++, n++){
                            if(words[m] != dic[k].word[n])cn++, n--;
                        }
                        if(cn <= 1)cout << " " << dic[k].word;
                    }
                    else{
                        cn = 0;
                        for(int m = 0, n = 0; n < dic[k].sz; m++, n++){
                            if(words[m] != dic[k].word[n])cn++, m--;
                        }
                        if(cn <= 1)cout << " " << dic[k].word;
                    }
                }
            }
            cout << endl;
        }
        if(t)cout << endl;
    }
    return 0;
}

UVa - 661 - Blowing Fuses

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int main(){
    int n, m, c, m_lines, ans, mx, fuse, cs = 1;
    while(cin >> n >> m >> c){
        if(m == 0 && m == n && m == c)break;
        int n_lines[n+1], toggle[n+1];
        memset(toggle, 0, sizeof(toggle));
        for(int i = 1; i <= n; i++)cin >> n_lines[i];
        ans = 0;int cnt = 0;fuse = 0, mx = 0;
        while(cin >> m_lines){
            cnt++;
            if(toggle[m_lines] == 0)ans += n_lines[m_lines], toggle[m_lines] = 1;
            else ans -= n_lines[m_lines], toggle[m_lines] = 0;

            if(ans <= c){
                if(mx < ans)mx = ans;
            }
            else fuse = 1;

            if(cnt == m)break;
        }
        cout << "Sequence " << cs << endl;
        if(!fuse)cout << "Fuse was not blown." << "\n" << "Maximal power consumption was " << mx << " amperes." << endl;
        else cout << "Fuse was blown." << endl;cs++;
        cout << endl;
    }
    return 0;
}

UVa - 644 - Immediate Decodability

#include <bits/stdc++.h>
using namespace std;

struct data{
    int sze;
    string code;
}ar[13];

bool cmp(data a, data b){
    if(a.sze != b.sze)return a.sze < b.sze;
    return a.code < b.code;
}

int main(){
    int sz[13], cs = 0;
    string temp, inn;
    while(cin >> inn){
        int sz = 0, flag = 0;
        ar[sz].code = inn;
        ar[sz].sze = inn.size();
        sz += 1;
        while(cin >> inn){
            if(inn == "9")break;
            ar[sz].code = inn;
            ar[sz].sze = inn.size();
            sz += 1;
        }
        sort(ar, ar+sz, cmp);
        for(int i = 0; i < sz; i++){
            for(int j = i+1; j < sz; j++){
                temp.clear();
                if((ar[i].sze == ar[j].sze) && (ar[i].code == ar[j].code)){
                    flag = 1;break;
                }
                for(int k = 0; k < ar[i].sze; k++)temp.push_back(ar[j].code[k]);
                if(temp == ar[i].code){
                    flag = 1; break;
                }
            }
        }
        if(flag)cout << "Set " << ++cs << " is not immediately decodable" << endl;
        else cout << "Set " << ++cs << " is immediately decodable" << endl;
        for(int i = 0; i < sz; i++)ar[i].code.clear();
    }
    return 0;
}