UVa 10830 - A New Function

For n=100 on observation::

i  :  n/i

2   50
3   33
4   25
5   20
6   16
7   14
8   12
9   11
10   10
11   9
12   8
13   7
14   7
15   6
16   6
17   5
18   5
19   5
20   5
21   4
22   4
23   4
24   4
25   4
26   3
27   3
28   3
29   3
30   3
31   3
32   3
33   3
34   2
35   2
36   2
37   2
38   2
39   2
40   2
41   2
42   2
43   2
44   2
45   2
46   2
47   2
48   2
49   2
50   2

Count of n/i :

2 - 17
3 - 8
4 - 5
5 - 4
6 - 2
7 - 2
8 - 1
9 - 1
10 - 1
11 - 1
12 - 1
14 - 1
16 - 1
20 - 1
25 - 1
33 - 1
50 - 1

Case 1: 3150

First i numbers less than sqrt(n) ans can be calculated easily as (n/i-1)*i   (ie. the numbers from 2 to sqrt(n) in O(sqrt(n))).

For numbers from (sqrt(n) to n) it can be seen that intervals of constant n/i are formed,which can be calculated as

(n/i-1)*(Summation of all the numbers in interval).

On further observation it can be seen that that the intevals boundary need not to be calculated seperately as it can be observed above that range(34,50) has value 2 which is same as (n/3+1,n/2),,,

range(26,33) has value 2 which is same as (n/4+1,n/3),,,and so on..

Hence the solution can be written in O(sqrt(n))..

My code:

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

typedef map<int,int> mi;

#define si(a) scanf("%lld",&a)

#define sii(a,b) scanf("%lld %lld",&a,&b)

#define siii(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define pi(a) printf("%d\n",a)

#define nl printf("\n");

#define pb push_back

#define mp make_pair

#define all(c) (c).begin(),(c).end()

#define f(i,a,b) for(i=a;i<b;i++)

#define rf(i,a,b) for(i=a;i>=b;i--)

#define clr(x,a) memset(x,a,sizeof(x))

#define MAX 1000100

#define MOD 1000000007

ll n,m;

map<ll,ll> mm;

int main(){

    ll r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;

    ll ans=0;string p;

    t=0;

    while(1){

        t++;

        si(n);

        if(n==0)

            break;

        ans=0;

        for(i=2;i*i<n;i++){

// For first i numbers less than sqrt(n)

            ans+=(n/i-1)*i;

//the interval (y,x) with n/i value=i can be calculated as discussed above with y>sqrt(n)

            x=n/i;

            y=n/(i+1)+1;

            if(y>i){

                z=(i-1)*(x*x+x-y*y+y)/2;

                ans+=z;

            }

        }

        if(i*i==n)

            ans+=(n/i-1)*i;

        printf("Case %lld: %lld\n",t,ans);

    }

    return 0;

}

UVa 10616 - Divisible Group Sums

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%lld",&a)
#define sii(a,b) scanf("%lld %lld",&a,&b)
#define siii(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pi(a) printf("%lld\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

ll d,n,m,dp[300][50][30],a[MAX];

ll solve(ll i,ll m,ll sum){
    if(m==0 && sum==0)
        return dp[i][m][sum]=1;
    if(m==0 && sum!=0)
        return dp[i][m][sum]=0;
    if(i>=n || m<0)
        return 0;
    if(dp[i][m][sum]!=-1)
        return dp[i][m][sum];
    return dp[i][m][sum]=solve(i+1,m,sum)+solve(i+1,m-1,((sum+a[i])%d+d)%d);
}

int main(){
    ll r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0,q;
    ll ans=0;string p;

    t=0;
    while(1){
        sii(n,q);
        if(n==0 && q==0)
            break;
        t++;
        printf("SET %lld:\n",t);

        f(i,0,n)
            si(a[i]);
        f(i,1,q+1){
            clr(dp,-1);
            sii(d,m);
            printf("QUERY %lld: %lld\n",i,solve(0,m,0));
        }
    }

    return 0;
}

UVa 253 - Cube painting

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m;

int a[24][6] = {
  {1,2,3,4,5,6},
  {1,4,2,5,3,6},
  {1,5,4,3,2,6},
  {1,3,5,2,4,6},

  {2,3,1,6,4,5},
  {2,6,3,4,1,5},
  {2,4,6,1,3,5},
  {2,1,4,3,6,5},

  {3,1,2,5,6,4},
  {3,2,6,1,5,4},
  {3,6,5,2,1,4},
  {3,5,1,6,2,4},

  {4,5,6,1,2,3},
  {4,1,5,2,6,3},
  {4,2,1,6,5,3},
  {4,6,2,5,1,3},

  {5,6,4,3,1,2},
  {5,3,6,1,4,2},
  {5,1,3,4,6,2},
  {5,4,1,6,3,2},

  {6,5,3,4,2,1},
  {6,4,5,2,3,1},
  {6,2,4,3,5,1},
  {6,3,2,5,4,1}
};
int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p,s1,s2;


    while(getline(cin,p)){
        s1=p.substr(0,6);
        s2=p.substr(6,6);
        z=0;
        f(i,0,24){
            c=0;
            string l;
            f(j,0,6){
                x=a[i][j]-1;
                l+=s1[x];
            }
            if(l==s2){
                z=1;
                break;
            }
        }
        if(z)
            cout<<"TRUE";
        else
            cout<<"FALSE";
        nl;
    }

    return 0;
}

UVa 10608-Friends

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,mk[MAX],c;
vi v[MAX];

int dfs(int x){
    c++;
    mk[x]=1;
    int i;
    f(i,0,v[x].size()){
        if(!mk[v[x][i]])
            dfs(v[x][i]);
    }
}

int main(){
    int r,k,i,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    while(t--){
        clr(mk,0);
        sii(n,m);
        f(i,0,m){
            sii(x,y);
            v[x].pb(y);
            v[y].pb(x);
        }
        z=0;
        f(i,1,n+1){
            if(!mk[i]){
                c=0;
                dfs(i);
                z=max(z,c);
            }
        }
        f(i,0,n+5)
            v[i].clear();
        pi(z);
    }

    return 0;
}

UVa 10106-Product

//\\__ hr1212 __//\\

import java.io.*;
import java.math.*;
import java.util.*;

public class Main{

static int i,n,m,z,x,y,j,k,l,r;
static int a[];
static String s,p,q;
static int MAX=1000010;

public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
BigInteger b1=BigInteger.ZERO;
BigInteger b2=BigInteger.ZERO,b3=BigInteger.ZERO;
i=0;
while((s=br.readLine())!=null){
if(i%2==0)
b1=new BigInteger(s);
else
b2=new BigInteger(s);
if(i%2==1){
b3=b1.multiply(b2);
System.out.println(b3);
}
i++;
}


out.close();

}
static class InputReader {

private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar;
private int snumChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

int res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public long nextLong() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

long res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public String readString() {
int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}

UVa 196 - Spreadsheet

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,b[1010][1010];
string a[1010][1010];

int solve(int i,int j){
    if(b[i][j]!=1e9)
        return b[i][j];
    int z=0,k,l,x,y;
    string s,p;
    f(k,1,a[i][j].size()){
        if(a[i][j][k]>='A' && a[i][j][k]<='Z')
            s+=a[i][j][k];
        if(a[i][j][k]>='0' && a[i][j][k]<='9')
            p+=a[i][j][k];
        if(a[i][j][k]=='+' || k==a[i][j].size()-1){
            x=0;y=0;
            f(l,0,s.size())
                y=y*26+(s[l]-'A'+1);
            f(l,0,p.size())
                x=x*10+(p[l]-'0');
            x--;y--;
            z+=solve(x,y);
            s.clear();p.clear();
        }
    }

    return b[i][j]=z;
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    while(t--){
        sii(m,n);
        f(i,0,n){
            f(j,0,m){
                b[i][j]=1e9;
                cin>>a[i][j];
                if(a[i][j][0]!='=')
                    b[i][j] = atoi(a[i][j].c_str());
            }
        }
        f(i,0,n){
            f(j,0,m){
                if(b[i][j]==1e9)
                    solve(i,j);
                if(j==m-1)
                    printf("%d",b[i][j]);
                else
                    printf("%d ",b[i][j]);
            }
            nl;
        }
    }

    return 0;
}

UVa 116 - Unidirectional TSP

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%lld",&a)
#define sii(a,b) scanf("%lld %lld",&a,&b)
#define siii(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

ll k,n,m,a[105][105],dp[105][105],b[105][105];

vector<ll> w[105];

int cmp(pair<ll,ll> p,pair<ll,ll> q){
    if(p.first!=q.first)
        return p.first<q.first;
    return p.second<q.second;
}

void solve(ll i,ll j){
    if(b[i][j]!=-1){
        w[k].pb(b[i][j]);
        solve(b[i][j],j+1);
    }
}

int main(){
    ll r,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(sii(n,m)!=EOF){
        clr(dp,0);
        f(i,0,n)
            f(j,0,m)
                si(a[i][j]);
        f(i,0,n){
            dp[i][m-1]=a[i][m-1];
            b[i][m-1]=-1;
        }
        rf(j,m-2,0){
            f(i,0,n){
                vector<pair<ll,ll> > v;
                dp[i][j]=a[i][j];
                ll ll=(i-1+n)%n,rr=(i+1)%n;
                x=dp[i][j+1];y=dp[ll][j+1];z=dp[rr][j+1];
                v.pb(mp(x,i));v.pb(mp(y,ll));v.pb(mp(z,rr));
                sort(all(v),cmp);
                dp[i][j]+=v[0].first;
                b[i][j]=v[0].second;
            }
        }

        z=LONG_LONG_MAX;
        f(i,0,n)
            z=min(z,dp[i][0]);
        k=0;
        f(i,0,n){
            if(dp[i][0]==z){
                w[k].pb(i);
                solve(i,0);
                k++;
            }
        }
        x=0;
        f(i,0,k){
            c=0;
            f(j,0,k){
                f(l,0,m){
                    if(w[i][l]!=w[j][l]){
                        if(w[i][l]<w[j][l])
                            c++;
                        break;
                    }

                }
                if(c==k-1)
                    break;
            }
            if(c==k-1)
                break;
        }
        f(j,0,m)
            if(j!=m-1)
                cout<<w[i][j]+1<<" ";
            else
                cout<<w[i][j]+1<<endl;
        cout<<z<<endl;
        f(i,0,k)
            w[i].clear();
    }

    return 0;
}

UVa 200 - Rare Order

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,a[30][30],mk[30],b[30];
char s[1000000][25];
vi v;

void dfs(int x){
    int i;
    mk[x]=1;
    f(i,0,26){
        if(a[x][i] && !mk[i] && b[i])
            dfs(i);
    }
    v.pb(x);
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;
    n=0;
    while(scanf("%s",s[n])!=EOF){
    clr(a,0);
    clr(mk,0);
    clr(b,0);
    v.clear();
    f(i,0,strlen(s[n]))
        b[s[n][i]-'A']=1;
    n=1;
    while(1){
        scanf("%s",s[n]);
        if(s[n][0]=='#')
            break;
        f(i,0,strlen(s[n]))
            b[s[n][i]-'A']=1;
        n++;
    }
    f(i,0,n-1){
        f(j,0,min(strlen(s[i]),strlen(s[i+1]))){
            x=s[i][j]-'A';y=s[i+1][j]-'A';
            if(x!=y){
                a[x][y]=1;
                break;
            }
        }
    }
    f(i,0,26){
        if(!mk[i] && b[i])
            dfs(i);
    }
    f(i,0,26){
        c=0;
        if(b[i]){
            f(j,0,v.size())
                if(v[j]==i){
                    c=1;
                    break;
                }
            if(!c)
                v.pb(i);
        }
    }
    rf(i,v.size()-1,0)
        printf("%c",char(v[i]+'A'));
    nl;
    n=0;
    }
    return 0;
}

UVa 11953 - Battleships

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int c,n,m,mk[105][105];
char s[105][105];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void dfs(int x,int y){
    mk[x][y]=1;
    int i,p,q;
    f(i,0,4){
        p=x+dx[i];q=y+dy[i];
        if(p>=0 && p<n && q>=0 && q<n && s[p][q]!='.' && !mk[p][q])
            dfs(p,q);
    }
}

int main(){
    int r,k,i,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    f(l,1,t+1){
        clr(mk,0);
        si(n);
        f(i,0,n)
            scanf("%s",s[i]);
        c=0;
        f(i,0,n){
            f(j,0,n){
                if(!mk[i][j] && s[i][j]=='x'){
                    dfs(i,j);
                    c++;
                }
            }
        }
        printf("Case %d: %d\n",l,c);
    }

    return 0;
}

UVa 11094 - Continents

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int l,r,n,m,mk[30][30],st,c;
char s[30][30],land;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void dfs(int x,int y){
    c++;
    mk[x][y]=1;
    if(x==l && y==r)
        st=1;
    int i,j,p,q;
    f(i,0,8){
        p=x+dx[i];q=(y+dy[i]+m)%m;
        if(p>=0 && p<n && !mk[p][q] && s[p][q]==land)
            dfs(p,q);
    }
}

int main(){
    int k,i,x=0,y=0,j,t,z,x1=0,y1=0;
    ll ans=0;

    while(sii(n,m)!=EOF){
        clr(mk,0);
        f(i,0,n)
            scanf("%s",s[i]);
        sii(l,r);
        land=s[l][r];
        z=0;
        f(i,0,n){
            f(j,0,m){
                st=0;c=0;
                if(!mk[i][j] && s[i][j]==land){
                    dfs(i,j);
                    if(!st)
                        z=max(z,c);
                }
            }
        }
        pi(z);
    }

    return 0;
}

UVa 10946 - You want what filled?

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int c,n,m,mk[60][60];
vi b[30];
char s[60][60];
vector<pair<char,int> > v;

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void dfs(int x,int y,char ch){
    c++;
    mk[x][y]=1;
    int p,q,i;
    f(i,0,4){
        p=x+dx[i];q=y+dy[i];
        if(p>=0 && p<n && q>=0 && q<m && s[p][q]==ch && !mk[p][q])
            dfs(p,q,ch);
    }
}

int cmp(pair<char,int> p,pair<char,int> q){
    if(p.second!=q.second)
        return p.second>q.second;
    return p.first<q.first;
}

int main(){
    int r,k,i,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    t=0;
    while(1){
        t++;
        v.clear();
        sii(n,m);
        if(n==0 && m==0)
            break;
        printf("Problem %d:\n",t);
        clr(mk,0);
        f(i,0,26)
            b[i].clear();
        f(i,0,n){
            scanf("%s",s[i]);
        }
        f(i,0,n){
            f(j,0,m){
                if(!mk[i][j] && s[i][j]!='.'){
                    c=0;
                    dfs(i,j,s[i][j]);
                    b[s[i][j]-'A'].pb(c);
                }
            }
        }
        f(i,0,26){
            f(j,0,b[i].size()){
                v.pb(mp(i+'A',b[i][j]));
            }
        }
        sort(all(v),cmp);
        f(i,0,v.size()){
            printf("%c %d\n",v[i].first,v[i].second);
        }
    }

    return 0;
}

UVa 10336 - Rank the Languages

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,mk[1000][1000],b[30];
char s[1000][1000];
vector<pair<char,int> > v;

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void dfs(int x,int y,char ch){
    mk[x][y]=1;
    int p,q,i;
    f(i,0,4){
        p=x+dx[i];q=y+dy[i];
        if(p>=0 && p<n && q>=0 && q<m && s[p][q]==ch && !mk[p][q])
            dfs(p,q,ch);
    }
}

int cmp(pair<char,int> p,pair<char,int> q){
    if(p.second!=q.second)
        return p.second>q.second;
    return p.first<q.first;
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    f(l,1,t+1){
        printf("World #%d\n",l);
        v.clear();
        sii(n,m);
        clr(mk,0);
        clr(b,0);
        f(i,0,n){
            scanf("%s",s[i]);
        }
        f(i,0,n){
            f(j,0,m){
                if(!mk[i][j]){
                    dfs(i,j,s[i][j]);
                    b[s[i][j]-'a']++;
                }
            }
        }
        f(i,0,26){
            if(b[i])
                v.pb(mp(i+'a',b[i]));
        }
        sort(all(v),cmp);
        f(i,0,v.size()){
            printf("%c: %d\n",v[i].first,v[i].second);
        }
    }

    return 0;
}

UVa 722 - Lakes

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int c,n,m,mk[105][105];
char a[2000][2000],s[105];

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void dfs(int x,int y){
    c++;
    mk[x][y]=1;
    int p,q,i;
    f(i,0,8){
        p=x+dx[i];q=y+dy[i];
        if(p>=0 && p<n && q>=0 && q<m && !mk[p][q] && a[p][q]!='1')
            dfs(p,q);
    }
}


int main(){
    int r,k,i,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    sscanf( gets(s), "%d", &t);
    gets(s);
    while(t--){
        clr(mk,0);n=0;
         sscanf( gets(s), "%d %d", &x, &y);
        x--;y--;
        while(gets(a[n]) && strcmp(a[n],"")!=0)
            n++;
        m=strlen(a[0]);
        c=0;
        dfs(x,y);
        pi(c);
        if(t)
            nl;
    }

    return 0;
}

UVa 352 - The Seasonal War

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,a[100][100],mk[100][100];
int dx[]={0,0,1,1,1,-1,-1,-1};
int dy[]={1,-1,0,1,-1,0,1,-1};

void dfs(int x,int y){
    mk[x][y]=1;
    int p,q,i;
    f(i,0,8){
        p=x+dx[i];q=y+dy[i];
        if(p>=0 && p<n && q>=0 && q<n && !mk[p][q] && a[p][q]!=0)
            dfs(p,q);
    }
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;char p[100];
    l=0;
    while(si(n)!=EOF){
        l++;
        f(i,0,n){
            scanf("%s",p);
            f(j,0,n){
                a[i][j]=p[j]-'0';
                mk[i][j]=0;
            }
        }
        c=0;
        f(i,0,n){
            f(j,0,n){
                if(a[i][j] && !mk[i][j]){
                    dfs(i,j);
                    c++;
                }
            }
        }
        printf("Image number %d contains %d war eagles.\n",l,c);
    }

    return 0;
}

UVa 12442 - Forwarding Emails

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 50005
#define MOD 1000000007

int n,m,mk[MAX],length[MAX];
vi v[MAX];

int dfs(int x){
    mk[x]=1;
    int c=1;
    if(!mk[v[x][0]])
        c+=dfs(v[x][0]);
    mk[x]=0;
    return length[x]=c;
}

int main(){
    int r,k,i,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    f(l,1,t+1){
        clr(mk,0);
        clr(length,-1);
        si(n);
        f(i,0,n){
            sii(x,y);
            v[x].pb(y);
        }
        z=-1;
        f(i,1,n+1){
            if(length[i]==-1)
                dfs(i);
            if(length[i]>z){
                z=length[i];
                y=i;
            }
        }
        printf("Case %d: %d\n",l,y);
        f(i,0,n+5)
            v[i].clear();
    }

    return 0;
}

UVa 11906 - Knight in a War Grid

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007
#define F first
#define S second

int n,m,mk[105][105],cnt[105][105],wt[105][105];

int main(){
    int odd,even,p,q,r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;

    si(x1);
    f(t,1,x1+1){
        clr(mk,0);
        clr(wt,0);
        odd=0;even=0;
        sii(n,m);
        sii(l,r);
        si(z);
        f(i,0,z){
            sii(x,y);
            wt[x][y]=1;
        }
        vector<pii > v;
        if(l!=0 && r!=0 && l!=r){
            v.pb(mp(l,r));v.pb(mp(-l,r));v.pb(mp(l,-r));v.pb(mp(-l,-r));
            v.pb(mp(r,l));v.pb(mp(-r,l));v.pb(mp(r,-l));v.pb(mp(-r,-l));
        }
        else if(l==0 && r!=0){
            v.pb(mp(l,r));v.pb(mp(l,-r));
            v.pb(mp(r,l));v.pb(mp(-r,l));
        }
        else if(r==0 && l!=0){
            v.pb(mp(l,r));v.pb(mp(-l,r));
            v.pb(mp(r,l));v.pb(mp(r,-l));
        }
        else if(l==r && l!=0){
            v.pb(mp(l,r));v.pb(mp(-l,r));v.pb(mp(l,-r));v.pb(mp(-l,-r));
        }
        queue<pii > qq;
        qq.push(mp(0,0));
        mk[0][0]=1;
        while(!qq.empty()){
            pii pp=qq.front();
            x=pp.F;y=pp.S;
            qq.pop();
            c=0;
            f(i,0,v.size()){
                p=x+v[i].F;q=y+v[i].S;
                if(p>=0 && p<n && q>=0 && q<m && !wt[p][q]){
                    if(!mk[p][q]){
                        qq.push(mp(p,q));
                        mk[p][q]=1;
                    }
                    c++;
                }
            }
            if(c&1)
                odd++;
            else
                even++;
        }
        printf("Case %d: %d %d\n",t,even,odd);
    }

    return 0;
}

UVa 11831 - Sticker Collector Robot

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007


int n,m,cnt,id,l;
char a[2000][2000],p[MAX];
vector<char> v;
map<char,int> mm;

void solve(int x,int y,char dir){

    id++;
    if(a[x][y]=='*'){
        cnt++;
        a[x][y]='.';
    }
    if(id==l){
        pi(cnt);
    }
    else if(p[id]=='D'){
        solve(x,y,v[(mm[dir]+1)%4]);
    }
    else if(p[id]=='E'){
        solve(x,y,v[(mm[dir]-1+4)%4]);
    }
    else{
        int p=x,q=y;
        if(dir=='N')
            p=p-1;
        if(dir=='L')
            q=q+1;
        if(dir=='S')
            p=p+1;
        if(dir=='O')
            q=q-1;

        if(p<0 || p>=n || q<0 || q>=m || a[p][q]=='#')
            solve(x,y,dir);
        else
            solve(p,q,dir);
    }
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,z,x1=0,y1=0;
    ll ans=0;
    char dir;

    mm['N']=0;mm['L']=1;mm['S']=2;mm['O']=3;
    v.pb('N');v.pb('L');v.pb('S');v.pb('O');
    while(1){
        siii(n,m,l);
        if(n==0 && m==0 && l==0)
            break;
        f(i,0,n){
            scanf("%s",a[i]);
            f(j,0,m){
                if(a[i][j]=='N' || a[i][j]=='S' || a[i][j]=='L' || a[i][j]=='O'){
                    x=i;y=j;dir=a[i][j];
                }
            }
        }
        scanf("%s",p);
        id=-1;cnt=0;
        solve(x,y,dir);
    }

    return 0;
}

UVa 118 - Mutant Flatworld Explorers

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int id,n,m,mk[2000][2000];
string p;

vector<char> v;
map<char,int> mm;

void solve(int x,int y,char dir){

    id++;
    if(id==p.size()){
        printf("%d %d %c\n",x,y,dir);
    }
    else if(p[id]=='R'){
        solve(x,y,v[(mm[dir]+1)%4]);
    }
    else if(p[id]=='L'){
        solve(x,y,v[(mm[dir]-1+4)%4]);
    }
    else{
        int p=x,q=y;
        if(dir=='N')
            q=q+1;
        if(dir=='E')
            p=p+1;
        if(dir=='S')
            q=q-1;
        if(dir=='W')
            p=p-1;

        if(p<0 || p>n || q<0 || q>m){
            if(!mk[x][y]){
                printf("%d %d %c LOST\n",x,y,dir);
                mk[x][y]=1;
            }
            else
                solve(x,y,dir);
        }
        else
            solve(p,q,dir);
    }
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;
    char ch;

    mm['N']=0;mm['E']=1;mm['S']=2;mm['W']=3;
    v.pb('N');v.pb('E');v.pb('S');v.pb('W');
    sii(n,m);
    while(sii(x,y)!=EOF){
        cin>>ch;
        cin>>p;
        id=-1;
        solve(x,y,ch);
    }

    return 0;
}

UVa 125 - Numbering Paths

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,graph[50][50];

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    t=-1;
    while(si(m)!=EOF){
        t++;
        clr(graph,0);
        n=0;
        f(i,0,m){
            sii(x,y);
            graph[x][y]=1;
            n=max(n,max(x,y));
        }

        n++;
        f(k,0,n){
            f(i,0,n)
                f(j,0,n)
                    if(graph[i][k] && graph[k][j])
                        graph[i][j]+=graph[i][k]*graph[k][j];
        }
        f(k,0,n){
            if(graph[k][k]){
                f(i,0,n){
                    f(j,0,n)
                        if(graph[i][k] && graph[k][j])
                            graph[i][j]=-1;
                }
            }
        }
        printf("matrix for city %d\n",t);
        f(i,0,n){
            f(j,0,n)
                if(j!=n-1)
                    printf("%d ",graph[i][j]);
                else
                    printf("%d",graph[i][j]);
            nl;
        }
    }

    return 0;
}

UVa 297 - Quadtrees

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,x,s[50][50],b[50][50];
string p;

void build(int a,int b,int c,int d){
    int i,j;
    x++;
    if(p[x]=='p'){
        build(a,(b+d)/2,(a+c)/2,d);
        build(a,b,(a+c)/2,(b+d)/2);
        build((a+c)/2,b,c,(b+d)/2);
        build((a+c)/2,(b+d)/2,c,d);
    }
    else if(p[x]=='f'){
        f(i,a,c)
            f(j,b,d)
                s[i][j]=1;
    }
}

int main(){
    int i,r,k,c=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;

    si(t);
    while(t--){
        ans=0;
        clr(s,0);
        cin>>p;
        x=-1;
        build(0,0,32,32);
        f(i,0,32)
            f(j,0,32)
                b[i][j]=s[i][j];
        cin>>p;
        x=-1;
        build(0,0,32,32);
        f(i,0,32)
            f(j,0,32)
                if(s[i][j] || b[i][j])
                    ans++;
        printf("There are %d black pixels.\n",ans);
    }

    return 0;
}

UVa 11235 - Frequent values

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 300010
#define MOD 1000000007

/*
On observation it can be seen that it is a problem of Range Max Query as the sequence given is non-decreasing..

Here cnt[] is used to store the cnt of each number and srt[] and ed[] store the starting index and ending index of element respectively.

Segment tree is formed from array of count of elements(cnt[]).
*/


class SegmentTree{
    private:
        vi st,A;
        int n;

    int left(int p){
        return (p << 1);
    }
    int right(int p){
        return ((p << 1)+1);
    }

    void build(int p,int L,int R){
        if(L==R){
            st[p]=A[L];
        }
        else{
            int p1,p2;
            build(left(p),L,((L+R) >> 1));
            build(right(p),((L+R) >> 1)+1,R);
            p1=st[left(p)];p2=st[right(p)];
            st[p]=((p1>=p2) ? p1 : p2);
        }
    }

    int rmq(int p,int L,int R,int i,int j){
        if(i>R || j<L) return -1;
        if(L>=i && R<=j) return st[p];
        int p1,p2;
        p1=rmq(left(p),L,((L+R) >> 1),i,j);
        p2=rmq(right(p),((L+R) >> 1)+1,R,i,j);
        if(p2==-1) return p1;
        if(p1==-1) return p2;
        return ((p1>=p2) ? p1 : p2);
    }

    public:
        SegmentTree(const vi &_A){
            A=_A;n=(int)A.size();
            st.assign(4*n,0);
            build(1,0,n-1);
        }
        int rmq(int i,int j){
            return rmq(1,0,n-1,i,j);
        }
};

int n,m,a[MAX],cnt[MAX],srt[MAX],ed[MAX];

int main(){
    int q,r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(1){
        si(n);
        if(n==0)
            break;
        si(q);
        clr(cnt,0);
        f(i,0,n){
            si(a[i]);
            a[i]+=150000;

//a[i] is increased by arbitary number as the input can be negative....

            cnt[a[i]]++;
            if(cnt[a[i]]==1)
                srt[a[i]]=i;
        }
        vi A;
        f(i,0,n){
            A.pb(cnt[a[i]]);
            ed[a[i]]=srt[a[i]]+cnt[a[i]]-1;
        }

/*
Within a given range (x,y)::
            If  st[a[x]]=x  &&  ed[a[y]]=y  then the answer of given range would be the max of cnt in that range that can be solved using Range Max Query on cnt[] so cnt[] is used to make segment tree....
*/

        SegmentTree st(A);
        while(q--){
            sii(x,y);
            x--;y--;

//  If starting and ending index has same element then answer is (y-x+1)..

            if(a[x]==a[y])
                pi(y-x+1);
            else{

/*
if starting element is some a[x] and ending element is some a[y] then
Count of elements of a[x] in given range = ed[a[x]]-x+1
Count of elements of a[y] in given range = y-srt[a[y]]+1
And the remaining mid interval can be calculated from Range Max Query of it from segment tree...
answer is max of above three counts....
*/

                int c1=0,c2=0,c3=0;
                c1=ed[a[x]]-x+1;
                c2=y-srt[a[y]]+1;
                x1=ed[a[x]]+1;y1=srt[a[y]]-1;
                if(y1>=x1)
                    c3=st.rmq(x1,y1);
                ans=max(c1,max(c2,c3));
                pi(ans);
            }
        }
    }

    return 0;
}

UVa 11503 - Virtual Friends

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 100010
#define MOD 1000000007

int n,m,p[MAX],ht[MAX],sz[MAX];

map<string,int> mm;

int findp(int x){
    return (p[x]==x)?x:findp(p[x]);
}

void unionset(int x,int y){
    if(findp(x)!=findp(y)){
        x=findp(x);y=findp(y);
        if(ht[x]>ht[y]){
            p[y]=x;
            sz[x]+=sz[y];
        }
        else{
            p[x]=y;
            sz[y]+=sz[x];
            if(ht[x]==ht[y])
                ht[y]++;
        }
    }
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string pp,q;

    si(t);
    while(t--){
        mm.clear();
        si(n);
        c=1;
        clr(p,0);
        clr(ht,0);
        clr(sz,0);
        f(i,1,MAX){
            p[i]=i;
            sz[i]=1;
        }
        f(i,0,n){
            cin>>pp>>q;
            if(mm.find(pp)==mm.end())
                mm[pp]=c++;
            if(mm.find(q)==mm.end())
                mm[q]=c++;
            unionset(mm[pp],mm[q]);
            x=mm[pp];y=mm[q];
            printf("%d\n",max(sz[findp(mm[pp])],sz[findp(mm[q])]));
        }
    }

    return 0;
}

UVa 10507 - Waking up brain

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,graph[30][30],mk[30],con[30];

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0,yr,prevc;
    ll ans=0;string p;

    while(si(n)!=EOF){
        prevc=0;
        yr=0;
        clr(mk,0);
        clr(graph,0);
        clr(con,0);
        si(m);
        cin>>p;
        f(i,0,3){
            mk[p[i]-'A']=1;
            con[p[i]-'A']=3;
        }
        f(i,0,m){
            cin>>p;
            graph[p[0]-'A'][p[1]-'A']=1;
            graph[p[1]-'A'][p[0]-'A']=1;
        }
        while(1){
            c=0;
            f(i,0,26){
                if(con[i]>=3)
                    c++;
            }
            if(prevc==c || c==n)
                break;

            prevc=c;
            yr++;

            vi v;
            f(i,0,26){
                f(j,0,26){
                    if(graph[i][j] && mk[i] && !mk[j]){
                        con[j]++;
                        if(con[j]==3)
                            v.pb(j);
                    }
                }
            }
            f(i,0,v.size())
                mk[v[i]]=1;
            f(i,0,26){
                if(!mk[i])
                    con[i]=0;
            }
        }
        if(c!=n)
            printf("THIS BRAIN NEVER WAKES UP\n");
        else
            printf("WAKE UP IN, %d, YEARS\n",yr);
    }

    return 0;
}

UVa 793 - Network Connections

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,ht[MAX],p[MAX];
char s[MAX];

int findp(int x){
    return (p[x]==x)?x:findp(p[x]);
}

void unionset(int x,int y){
    if(findp(x)!=findp(y)){
        x=findp(x);y=findp(y);
        if(ht[x]>ht[y])
            p[y]=x;
        else{
            p[x]=y;
            if(ht[x]==ht[y])
                ht[y]++;
        }
    }
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;
    char ch;

    scanf("%d\n",&t);
    while(t--){
        x1=0;y1=0;
        clr(ht,0);
        scanf("%d\n\n",&n);
        f(i,1,n+1)
            p[i]=i;
        while(1){
            gets(s);
            if (strcmp(s, "") == 0 || feof(stdin)) break;
            sscanf(s, "%c %d %d", &ch, &x, &y);
            if(ch=='c')
                unionset(x,y);
            else if(ch=='q'){
                if(findp(x)==findp(y))
                    x1++;
                else
                    y1++;
            }
        }
        printf("%d,%d\n",x1,y1);
        if(t)
            nl;
    }

    return 0;
}

UVa 11991 - Easy Problem from Rujia Liu?

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,a[MAX];
vi v[MAX];

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(sii(n,m)!=EOF){
        z=0;
        f(i,1,n+1){
            si(x);
            v[x].pb(i);
            z=max(z,x);
        }
        while(m--){
            sii(k,x);
            if(v[x].size()<k)
                pi(0);
            else
                pi(v[x][k-1]);
        }
        f(i,0,z+1)
            v[i].clear();
    }

    return 0;
}

UVa 10895 - Matrix Transpose

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,a[MAX],b[MAX];
vector<pii > v[MAX];

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(sii(n,m)!=EOF){
    f(i,1,n+1){
        si(x);
        f(j,0,x){
            si(a[j]);
        }
        f(j,0,x){
            si(b[j]);
        }
        f(j,0,x){
            v[a[j]].pb(mp(i,b[j]));
        }
    }
    printf("%d %d\n",m,n);
    f(i,1,m+1){
        pi(v[i].size());
        f(j,0,v[i].size()){
            printf(" %d",v[i][j].first);
        }
        nl;
        f(j,0,v[i].size()){
            printf("%d",v[i][j].second);
            if(j!=v[i].size()-1)
                printf(" ");
        }
        nl;
        v[i].clear();
    }
    }
    return 0;
}

UVa 599 - The Forrest for the Trees

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 800
#define MOD 1000000007

int k,n,m,b[30],mk[30];
char s[MAX];
vi v[MAX];

void dfs(int x){
    mk[x]=1;
    int i;
    k++;
    f(i,0,v[x].size()){
        if(!mk[v[x][i]])
            dfs(v[x][i]);
    }
}

int main(){
    int r,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    while(t--){
        clr(b,0);
        clr(mk,0);
        x1=y1=0;
        while(1){
            scanf("%s",s);
            if(s[0]=='*')
                break;
            x=s[1]-'A';y=s[3]-'A';
            v[x].pb(y);
            v[y].pb(x);
        }
        gets(s);
        gets(s);
        f(i,0,strlen(s)){
            if(s[i]>='A' && s[i]<='Z')
                b[s[i]-'A']=1;
        }
        f(i,0,26){
            if(b[i] && !mk[i]){
                k=0;
                dfs(i);
                if(k==1)
                    x1++;
                else
                    y1++;
            }
        }
        f(i,0,26)
            if(b[i])
                v[i].clear();
        printf("There are %d tree(s) and %d acorn(s).\n",y1,x1);
    }

    return 0;
}

UVa 10107 - What is the Median?

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%lld\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m;
vi v;

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(si(x)!=EOF){
        v.pb(x);
        sort(all(v));
        n=v.size();
        if(n%2==0){
            pi(((ll)v[n/2]+v[n/2-1])/2);
        }
        else
            pi((ll)v[n/2]);
    }

    return 0;
}

UVa 146 - ID Codes

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m;

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(1){
        cin>>p;
        if(p=="#")
            break;
        if(next_permutation(all(p)))
            cout<<p<<endl;
        else
            printf("No Successor\n");
    }

    return 0;
}