UVa 10714 - Ants

//\\__ 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 n,m,a[MAX];

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

    si(t);
    while(t--){
        sii(l,n);
        f(i,0,n)
            si(a[i]);
        ans=0;ans1=0;
        f(i,0,n){
            ans=max(ans,min(a[i],l-a[i]));
            ans1=max(ans1,max(a[i],l-a[i]));
        }
        cout<<ans<<" "<<ans1<<endl;
    }

    return 0;
}

UVa 11576 - Scrolling Sign

//\\__ 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[200];

    si(t);
    while(t--){
        sii(n,m);
        string s,q;
        f(i,0,m){
            cin>>q;
            if(i==0)
                s+=q;
            else{
                c=0;
                for(j=q.size()-1;j>=0;j--){
                    k=s.size()-1;
                    l=j;
                    while(q[l]==s[k] && l>=0 && k>=0){
                        l--;k--;
                    }
                    if(l==-1){
                        s+=q.substr(j+1,q.size()-j+1);
                        c=1;
                        break;
                    }
                }
                if(!c)
                    s+=q;
            }
        }
        cout<<s.size()<<endl;
    }

    return 0;
}

UVa 10466 - How Far?

//\\__ 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("%lf",&a)
#define sii(a,b) scanf("%lf %lf",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%lf\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 100
#define MOD 1000000007
#define F first
#define S second

double n,m,x[MAX],y[MAX];
vector<pair<double,double> > v;

int main(){
    double r,c=0,t,l,z,x1=0,y1=0,theta,rad,tm;
    ll ans=0;string p;
    int i,j,k;

        while(sii(n,z)!=EOF){

        v.clear();
        v.pb(mp(0,0));
        f(i,1,n+1){
            sii(l,r);
            v.pb(mp(l,r));
        }
        clr(x,0);clr(y,0);
        f(i,0,n){
            f(j,i+1,n+1){
                tm=v[i+1].S;
                r=v[i+1].F;
                theta=z*(360)/tm;
                while(theta>=360){
                    theta-=360;
                }
                rad=theta*M_PI/180;
                x[j]+=r*cos(rad);y[j]+=r*sin(rad);
            }
        }
        f(i,1,n+1){
            l=sqrt(x[i]*x[i]+y[i]*y[i]);
            if(i!=n)
                printf("%.4lf ",l);
            else
                printf("%.4lf\n",l);
        }
       
        }

    return 0;
}

UVa 111 - History Grading

//\\__ 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 50
#define MOD 1000000007

ll n,m,b[MAX],a[MAX],dp[MAX][MAX];

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;

    si(n);
    f(i,0,n){
        si(x);
        a[x-1]=i;
    }
    while(si(x)!=EOF){
        b[x-1]=0;
        f(i,1,n){
            si(x);
            b[x-1]=i;
        }

        clr(dp,0);
        f(i,0,n+1){
            f(j,0,n+1){
                if(i==0 || j==0)
                    dp[i][j]=0;
                else if(a[i-1]==b[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        cout<<dp[n][n]<<endl;
    }

    return 0;
}

UVa 10667 - Largest Block

//\\__ 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,a[200][200];

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--){
        si(n);
        si(m);
        clr(a,0);
        while(m--){
            sii(x,y);sii(x1,y1);
            x--;y--;x1;y1;
            f(i,x,x1){
                f(j,y,y1){
                    a[i][j]=1;
                }
            }
        }
        f(i,0,n){
            f(j,0,n){
                if(i-1>=0)
                    a[i][j]+=a[i-1][j];
                if(j-1>=0)
                    a[i][j]+=a[i][j-1];
                if(i-1>=0 && j-1>=0)
                    a[i][j]-=a[i-1][j-1];
            }
        }
        ans=0;
        f(i,0,n){
            f(j,0,n){
                f(l,i,n){
                    f(r,j,n){
                        z=a[l][r];
                        if(i-1>=0)
                            z-=a[i-1][r];
                        if(j-1>=0)
                            z-=a[l][j-1];
                        if(i-1>=0 && j-1>=0)
                            z+=a[i-1][j-1];
                        if(z==0)
                            ans=max(ans,(ll)(l-i+1)*(r-j+1));
                    }
                }
            }
        }
        pi(ans);
    }

    return 0;
}

UVa 11283 - Playing Boggle

//\\__ 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[20][20];
int dx[]={0,0,1,1,1,-1,-1,-1};
int dy[]={1,-1,0,1,-1,0,1,-1};

mi mm;
string p[10];

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

    f(i,0,20){
        if(i<=2)
            mm[i]=0;
        else if(i<=4)
            mm[i]=1;
        else if(i==5)
            mm[i]=2;
        else if(i==6)
            mm[i]=3;
        else if(i==7)
            mm[i]=5;
        else
            mm[i]=11;
    }
    si(t);
    while(t--){
        ans=0;
        f(i,0,4)
            cin>>p[i];
        si(m);
        while(m--){
            cin>>s;
            flag=0;
            if(s.size()<=16){
            f(i,0,4){
                f(j,0,4){
                    if(p[i][j]==s[0]){
                        clr(mk,0);
                        queue<pair<pii,pii > > q;
                        q.push(mp(mp(i,j),mp(1,(1 << (4*i+j)))));
                        while(!q.empty()){
                            pair<pii,pii > pp=q.front();
                            q.pop();
                            x=pp.first.first;y=pp.first.second;z=pp.second.first;r=pp.second.second;
                            if(z==s.size()){
                                flag=1;
                                break;
                            }
                            else if(z>s.size())
                                break;
                            f(l,0,8){
                                x1=x+dx[l];y1=y+dy[l];
                                if(x1>=0 && x1<4 && y1>=0 && y1<=4 && p[x1][y1]==s[z]){
                                    if(((1<<(4*x1+y1)) & r)==0)
                                    q.push(mp(mp(x1,y1),mp(z+1,r|(1<<(4*x1+y1)))));
                                }
                            }
                        }
                    }
                }
            }
            }
            if(flag)
                ans+=mm[s.size()];
        }
        printf("Score for Boggle game #%d: %d\n",tt++,ans);
    }

    return 0;
}

UVa 11152 - Colourful Flowers

//\\__ 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 a,b,r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;
    double r1,r2,a1,a2,a3,s;

    while(cin>>a>>b>>c){
        s=(a+b+c)/2.0;
        a2=sqrt(s*(s-a)*(s-b)*(s-c));
        r2=a2/s;
        a3=M_PI*r2*r2;
        r1=(a*b*c)/(4*a2);
        a1=M_PI*r1*r1;
        printf("%.4lf %.4lf %.4lf\n",a1-a2,a2-a3,a3);
    }

    return 0;
}

UVa 11552 - Fewest Flops

//\\__ 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,a[30];
vi v[MAX];

int dp[MAX][28];

int solve(int i,int ed){
    int j,k;
    if(i>=n)
        return dp[i][ed]=0;
    if(dp[i][ed]!=-1)
        return dp[i][ed];
    int z=1e9;
    if(v[i].size()==1){
        if(ed==v[i][0])
            z=solve(i+1,v[i][0]);
        else
            z=solve(i+1,v[i][0])+1;
    }
    else{
    for(j=0;j<v[i].size();j++){
        for(k=0;k<v[i].size();k++){
            if(j==k)
                continue;
            if(ed==v[i][j])
                z=min(z,solve(i+1,v[i][k])+(int)v[i].size()-1);
            else
                z=min(z,solve(i+1,v[i][k])+(int)v[i].size());
        }
    }
    }
    return dp[i][ed]=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--){
        si(k);
        cin>>p;
        n=p.size();
        for(i=0;i<n;i+=k){
            clr(a,0);
            f(j,i,i+k){
                a[p[j]-'a']++;
            }
            f(j,0,26){
                if(a[j]!=0)
                    v[i/k].pb(j+1);
            }
        }
        n=n/k;
        clr(dp,-1);
        cout<<solve(0,0)<<endl;
        f(i,0,1000)
            v[i].clear();
    }

    return 0;
}

UVa 10600 - ACM contest and Blackout

//\\__ 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,parent[MAX];
vi w;
vector<pair<int,pair<int,int> > > v;

int findp(int x){
    if(parent[x]==x)
        return x;
    return parent[x]=findp(parent[x]);
}

int sameset(int x,int y){
    return findp(x)==findp(y);
}

void unionset(int x,int y){
    if(!sameset(x,y))
        parent[findp(x)]=findp(y);
}

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

    si(t);
    while(t--){
        sii(n,m);
        v.clear();
        w.clear();
        f(i,0,m){
            siii(x,y,z);
            v.pb(mp(z,mp(x,y)));
        }
        f(i,0,n+1)
            parent[i]=i;
        cst=0;
        sort(all(v));
        f(i,0,v.size()){
            pair<int,pair<int,int> > pp=v[i];
            z=pp.first;x=pp.second.first;y=pp.second.second;
            if(!sameset(x,y)){
                w.pb(i);
                unionset(x,y);
                cst+=z;
            }
        }
        cout<<cst<<" ";
        cst1=1e9;
        f(j,0,w.size()){
            f(i,0,n+1)
                parent[i]=i;
            xx=0;
            f(i,0,v.size()){
                if(i==w[j])
                    continue;
                pair<int,pair<int,int> > pp=v[i];
                z=pp.first;x=pp.second.first;y=pp.second.second;
                if(!sameset(x,y)){
                    unionset(x,y);
                    xx+=z;
                }
            }
            c=0;
            f(i,1,n+1)
                if(parent[i]==i)
                    c++;
            if(c>1)
                continue;
            cst1=min(cst1,xx);
        }
        if(cst1==1e9 || cst1<cst)
            cst1=cst;
        cout<<cst1<<endl;
    }

    return 0;
}

UVa 10541 - Stripe

//\\__ hr1212 __//\\

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

public class Main{

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

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);

t=Integer.parseInt(br.readLine());
for(k=0;k<t;k++){
for(i=0;i<500;i++){
for(j=0;j<500;j++)
dp[i][j]=BigInteger.valueOf(-1);
}
s=br.readLine();
p=s.split(" ");

m=Integer.parseInt(p[0]);
n=Integer.parseInt(p[1]);
for(i=0;i<n;i++){
a[i]=Integer.parseInt(p[i+2]);
}
System.out.println(solve(1,0));
}

out.close();

}

static BigInteger solve(int i,int j){
if(j==n && i<=m+2)
return BigInteger.ONE;
if(j>=n || i>m)
return BigInteger.ZERO;
z=dp[i][j].compareTo(BigInteger.valueOf(-1));
if(z!=0)
return dp[i][j];
return dp[i][j]=solve(i+1,j).add(solve(i+a[j]+1,j+1));
}

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 1056 - Degrees of Separation

//\\__ 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[100][100];

map<string,int> mm;

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

    while(sii(n,m)!=EOF){
        if(n==0 && m==0)
            break;
        k=0;
        f(i,0,n){
            f(j,0,n)
                graph[i][j]=1e9;
        }
        f(i,0,n)
            graph[i][i]=0;
        while(m--){
            cin>>p>>q;
            if(mm.find(p)==mm.end())
                mm[p]=k++;
            if(mm.find(q)==mm.end())
                mm[q]=k++;
            graph[mm[p]][mm[q]]=1;
            graph[mm[q]][mm[p]]=1;
        }

        f(k,0,n){
            f(i,0,n){
                f(j,0,n){
                    graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
                }
            }
        }
        z=0;
        f(i,0,n){
            f(j,0,n){
                z=max(z,graph[i][j]);
            }
        }
        printf("Network %d: ",tt++);
        if(z==1e9)
            printf("DISCONNECTED\n");
        else
            pi(z);
        nl;
        mm.clear();
    }

    return 0;
}

UVa 11437 - Triangle Fun

//\\__ 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;

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;

    double ax,ay,bx,by,cx,cy,dx,dy,ex,ey,fx,fy,px,py,qx,qy,rx,ry,mad,cad,mbe,cbe,mcf,ccf,lpr,lqr,lpq,s,area;

    si(t);
    while(t--){
        cin>>ax>>ay>>bx>>by>>cx>>cy;
        dx=(cx+2*bx)/3;dy=(cy+2*by)/3;
        ex=(ax+2*cx)/3;ey=(ay+2*cy)/3;
        fx=(bx+2*ax)/3;fy=(by+2*ay)/3;

        mad=(ay-dy)/(ax-dx);cad=ay-mad*ax;
        mbe=(by-ey)/(bx-ex);cbe=by-mbe*bx;
        mcf=(cy-fy)/(cx-fx);ccf=cy-mcf*cx;

        px=(cbe-cad)/(mad-mbe);py=(mad*cbe-mbe*cad)/(mad-mbe);
        qx=(cbe-ccf)/(mcf-mbe);qy=(mcf*cbe-mbe*ccf)/(mcf-mbe);
        rx=(ccf-cad)/(mad-mcf);ry=(mad*ccf-mcf*cad)/(mad-mcf);

        lpr=sqrt((px-rx)*(px-rx)+(py-ry)*(py-ry));
        lqr=sqrt((qx-rx)*(qx-rx)+(qy-ry)*(qy-ry));
        lpq=sqrt((px-qx)*(px-qx)+(py-qy)*(py-qy));

        s=(lpr+lqr+lpq)/2;

        area=sqrt(s*(s-lpr)*(s-lqr)*(s-lpq));

        ans=(area+0.5);
        pi(ans);
    }

    return 0;
}

UVa 10003 - Cutting Sticks

//\\__ 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,dp[100][100];
vi v;

int solve(int i,int j){
    int k,z=1e9;
    if(i==j || i+1==j)
        return 0;
    if(i>j)
        return 1e9;
    if(dp[i][j]!=-1)
        return dp[i][j];
    f(k,i+1,j)
        z=min(z,solve(i,k)+solve(k,j));
    return dp[i][j]=z+v[j]-v[i];
}

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(m)){
        if(m==0)
            break;

        v.clear();
        clr(dp,-1);

        v.pb(0);
        si(n);
        f(i,0,n){
            si(x);
            v.pb(x);
        }
        v.pb(m);
        n++;
        printf("The minimum cutting is %d.\n",solve(0,n));
    }

    return 0;
}

UVa 11777 - Automate the Grades

//\\__ 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];

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

    si(t);
    while(t--){
        z=0;
        f(i,0,7)
            si(a[i]);
        sort(a+4,a+7);
        f(i,0,4)
            z+=a[i];
        z+=(a[5]+a[6])/2.0;
        printf("Case %d: ",tt++);
        if(z>=90)
            printf("A");
        else if(z>=80)
            printf("B");
        else if(z>=70)
            printf("C");
        else if(z>=60)
            printf("D");
        else
            printf("F");
        nl;
    }

    return 0;
}

UVa 10038 - Jolly Jumpers

//\\__ 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],b[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(si(n)!=EOF){
        f(i,0,n)
            si(a[i]);
        clr(b,0);
        f(i,0,n){
            b[abs(a[i]-a[i+1])]=1;
        }
        c=0;
        f(i,1,n){
            if(!b[i])
                c=1;
        }
        if(c)
            cout<<"Not jolly";
        else
            cout<<"Jolly";
        nl;
    }

    return 0;
}

UVa 11417 - GCD

//\\__ 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[1000];

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;

    f(k,2,505){
        ans=0;
        f(i,1,k){
            f(j,i+1,k+1){
                ans+=__gcd(i,j);
            }
        }
        a[k]=ans;
    }

    while(si(n)){
        if(n==0)
            break;
        pi(a[n]);
    }
    return 0;
}

UVa 10062 - Tell me the frequencies!

//\\__ 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;

mi mm;
vector<pii > v;

int cmp(pii p,pii 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;

    while(getline(cin,p)){
        if(c==1){
            nl;
        }
        c=1;
        f(i,0,p.size()){
            x=p[i];
            mm[x]++;
        }
        v.clear();
        for(mi::iterator it=mm.begin();it!=mm.end();it++){
            v.pb(mp(it->first,it->second));
        }
        sort(all(v),cmp);
        f(i,0,v.size()){
            printf("%d %d\n",v[i].first,v[i].second);
        }
        mm.clear();
    }

    return 0;
}

UVa 11877 - The Coco-Cola Store

//\\__ 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(si(n)){
        if(n==0)
            break;
        pi(n/2);
    }

    return 0;
}

UVa 12289 - One-Two-Three

//\\__ 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;

    si(t);
    while(t--){
        cin>>p;
        if(p.size()>3)
            pi(3);
        else{
            c=0;
            if(p[0]!='o')
                c++;
            if(p[1]!='n')
                c++;
            if(p[2]!='e')
                c++;
            if(c<=1)
                pi(1);
            else
                pi(2);
        }
    }

    return 0;
}

UVa 661 - Blowing Fuses

//\\__ 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 100
#define MOD 1000000007

int n,m,a[MAX],mk[MAX];

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

    while(siii(n,m,c)){

    if(n==0 && m==0 && c==0)
        break;
    f(i,1,n+1)
        si(a[i]);
    clr(mk,0);
    ans=0;z=0;
    while(m--){
        si(x);
        if(mk[x]){
            mk[x]=1-mk[x];
            ans-=a[x];
        }
        else{
            mk[x]=1;
            ans+=a[x];
            z=max(z,ans);
        }
    }
    printf("Sequence %d\n",tt++);
    if(z>c)
        printf("Fuse was blown.\n");
    else
        printf("Fuse was not blown.\nMaximal power consumption was %lld amperes.\n",z);
    nl;

    }
    return 0;
}

UVa 11636 - Hello World!

//\\__ 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[10000];

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

    a[1]=1;
    f(i,2,50)
        a[i]=a[i-1]*2;

    while(si(n)!=EOF){
        if(n<0)
            break;
        f(i,1,50)
            if(n<=a[i]){
                printf("Case %d: ",tt++);
                cout<<i-1<<endl;
                break;
            }
    }

    return 0;
}

UVa 10260 - Soundex

//\\__ 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;

map<char,int> mm;

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;

    mm['B']=mm['F']=mm['P']=mm['V']=1;
    mm['C']=mm['G']=mm['J']=mm['K']=mm['Q']=mm['S']=mm['X']=mm['Z']=2;
    mm['D']=mm['T']=3;
    mm['L']=4;
    mm['M']=mm['N']=5;
    mm['R']=6;

    while(cin>>p){
        c=0;
        string s;
        f(i,0,p.size())
            if(mm.find(p[i])!=mm.end())
                s+=(mm[p[i]]+'0');
            else if(s.size()!=0){
                f(j,0,s.size()){
                    while(s[j]==s[j+1] && j+1<s.size())
                        j++;
                    cout<<s[j];
                }
                s.clear();
            }
        if(s.size()!=0){
            f(j,0,s.size()){
                while(s[j]==s[j+1] && j+1<s.size())
                    j++;
                cout<<s[j];
            }
            s.clear();
        }
        nl;
    }

    return 0;
}

UVa 10450 - World Cup Noise

//\\__ 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("%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 100
#define MOD 1000000007

ll n,m,a[MAX];

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

    a[1]=2;a[2]=3;
    f(i,3,MAX){
        a[i]=a[i-1]+a[i-2];
    }
    si(t);
    while(t--){
        si(n);
        printf("Scenario #%d:\n",tt++);
        pi(a[n]);
        nl;
    }

    return 0;
}

UVa 507 - Jill Rides Again

//\\__ 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 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 ff first
#define s second

int n,m,a[MAX];

vector<pair<pii,pii > > v;

int cmp(pair<pii,pii > p,pair<pii,pii > q){
    if(p.ff.ff!=q.ff.ff)
        return p.ff.ff>q.ff.ff;
    else if(p.ff.s!=q.ff.s)
        return p.ff.s>q.ff.s;
    else
        return p.s.ff<q.s.ff;
}

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

    si(t);
    f(j,1,t+1){
        v.clear();
        si(n);
        f(i,1,n)
            si(a[i]);
        sum=0;
        st=1;
        f(i,1,n){
            if(a[i]+sum>=0){
                sum+=a[i];
                ed=i+1;
                if(sum>=0)
                    v.pb(mp(mp(sum,ed-st),mp(st,ed)));
            }
            else{
                sum=0;
                st=i+1;
            }
        }
        sort(all(v),cmp);
        if(v.size()==0)
            cout<<"Route "<<j<<" has no nice parts";
        else
            cout<<"The nicest part of route "<<j<<" is between stops "<<v[0].s.ff<<" and "<<v[0].s.s;
        nl;
    }

    return 0;
}

UVa 483 - Word Scramble

//\\__ 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(getline(cin,p)){
       string q;
       f(i,0,p.size()){
            if(p[i]!=' ')
                q+=p[i];
            else{
                if(q.size()!=0){
                    reverse(all(q));
                    cout<<q;
                    q.clear();
                }
                cout<<p[i];
            }
       }
       if(q.size()!=0){
            reverse(all(q));
            cout<<q;
            q.clear();
       }
       nl;
    }

    return 0;
}

UVa 11984 - A Change in Thermal Unit

//\\__ 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 tt,r,k,i,c=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;
    double x,y;

    tt=1;
    si(t);
    while(t--){
        sii(n,m);
        x=9*n/5.0+32;
        x+=m;
        y=(x-32)*5/9;
        printf("Case %d: %.2lf\n",tt++,y);
    }

    return 0;
}

UVa 10394 - Twin Primes

//\\__ 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 20001000
#define MOD 1000000007

int n,m,a[MAX];

vi v;
vector<pii > w;

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;

    clr(a,0);
    f(i,2,MAX){
        if(!a[i]){
            v.pb(i);
            for(j=2*i;j<MAX;j+=i)
                a[j]=1;
        }
    }
    f(i,0,v.size()-1){
        if(v[i+1]-v[i]==2){
            w.pb(mp(v[i],v[i+1]));
        }
    }
    while(si(n)!=EOF){
        printf("(%d, %d)\n",w[n-1].first,w[n-1].second);
    }

    return 0;
}

UVa 674 - Coin Change

//\\__ 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("%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

ll n,m,dp[5][100000],a[10];

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

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;

    a[0]=1;a[1]=5;a[2]=10;a[3]=25;a[4]=50;

    clr(dp,-1);
    while(si(n)!=EOF){
    if(n==0)
        pi(1);
    else
        cout<<solve(0,n)<<endl;
    }

    return 0;
}

UVa 11022 - String Factoring

//\\__ 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;

map<string,int> mm;

int solve(string p){
    if(p=="")
        return 0;
    int i,z,len,c,x,y;
    string q1,q2;
    if(mm.find(p)!=mm.end())
        return mm[p];
    c=0;
    f(i,1,p.size())
        if(p[i]!=p[0])
            c=1;
    if(!c)
        return mm[p]=1;
    z=p.size();
    len=p.size()/2;
    for(;len>=1;len--){
        for(i=0;i+len<p.size();i++){
            q1=p.substr(i,len);
            q2=p.substr(i+len,len);
            if(q1==q2){
                c=1;
                while(q1==p.substr(i+c*len,len)){
                    c++;
                }
                z=min(solve(p.substr(0,i))+solve(q1)+solve(p.substr(i+c*len,p.size()-i-c*len+1)),z);
            }
        }
    }
    return mm[p]=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;

    while(cin>>p){
        if(p=="*")
            break;
        mm.clear();
        cout<<solve(p)<<endl;
    }

    return 0;
}

UVa 11137 - Ingenuous Cubrency

//\\__ 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("%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

ll n,m,a[50],dp[30][100000];

ll solve(ll i,ll sum){
    if(sum==0)
        return 1LL;
    if(i>=22 || sum<0)
        return 0;
    if(dp[i][sum]!=-1)
        return dp[i][sum];
    return dp[i][sum]=solve(i,sum-a[i])+solve(i+1,sum);
}

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;

    f(i,1,25)
        a[i]=i*i*i;
    clr(dp,-1);
    while(si(n)!=EOF){
        pi(solve(1,n));
    }

    return 0;
}

UVa 11634 - Generate random numbers

//\\__ 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 10001
#define MOD 1000000007

int n,m,mk[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(cin>>x){
        if(x==0)
            break;
        c=x;
        t=0;
        clr(mk,0);
        while(c!=x || t==0){
            t++;
            mk[c]=1;
            z=c*c;
            z/=100;
            c=z%10000;
            if(mk[c]==1)
                break;
        }
        pi(t);
    }

    return 0;
}

UVa 11396 - Claw Decomposition

//\\__ 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 500
#define MOD 1000000007

int n,m,a[MAX],mk[MAX],col[MAX],flag;
vi v[MAX];

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

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

    while(cin>>n){
        if(n==0)
            break;
        z=-1;
        flag=0;
        clr(mk,0);
        while(cin>>x>>y){
            if(x==0 && y==0)
                break;
            v[x].pb(y);
            v[y].pb(x);
            z=max(z,max(x,y));
        }
        dfs(z,0);
        if(flag)
            printf("NO\n");
        else
            printf("YES\n");
        f(i,0,z+5)
            v[i].clear();

    }

    return 0;
}

UVa 11900 - Boiled Eggs

//\\__ 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];

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

    si(t);
    while(t--){
        siii(n,p,y);
        f(i,0,n)
            si(a[i]);
        x=0;c=0;
        f(i,0,n){
            if((x+a[i])<=y && c<p){
                x+=a[i];
                c++;
            }
        }
        printf("Case %d: ",tt++);
        pi(c);
    }

    return 0;
}

UVa 247 - Calling Circles

The question involves finding all SCC (Strongly Connected Components) and printing them.
Here the question can be solved easily due to smaller constraints (n<=25).

As the constraints are small we can apply Floyd Warshall Algorithm to calculate graph[i][j] which is "1" if we can reach to "j" from "i" else it is "0".

Then for each "i" check if graph[i][j] and graph[j][i] both are set as it implies that both can be reached from each other and so they can be included in same SCC.Take a mk[] array to mark the elements already taken and print each SCC for each unmarked "i".

Check the code for further reference :

//\\__ 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[50],graph[100][100];

map<string,int> mm;
vector<string> w;

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

    while(sii(n,m)){
        if(n==0 && m==0)
            break;
        if(tt!=1)
            nl;
        z=0;
        mm.clear();
        w.clear();
        clr(mk,0);
        clr(graph,0);
        f(i,0,m){
            cin>>p>>q;
            if(mm.find(p)==mm.end()){
                mm[p]=z++;
                w.pb(p);
            }
            if(mm.find(q)==mm.end()){
                mm[q]=z++;
                w.pb(q);
            }
            x=mm[p];y=mm[q];
            graph[x][y]=1;
        }
        f(k,0,n){
            f(i,0,n){
                f(j,0,n){
                    graph[i][j]|=(graph[i][k]&&graph[k][j]);
                }
            }
        }
        printf("Calling circles for data set %d:\n",tt++);
        f(i,0,n){
            vi v;
            if(!mk[i]){
                mk[i]=1;
                v.pb(i);
                f(j,0,n){
                    if(!mk[j]){
                        if(graph[i][j] && graph[j][i]){
                            v.pb(j);
                            mk[j]=1;
                        }
                    }
                }
            f(k,0,v.size()){
                cout<<w[v[k]];
                if(k!=v.size()-1)
                    cout<<", ";
            }
            nl;
            }
        }
    }

    return 0;
}

UVa 12467 - Secret word

The question can be solved easily in O(n*n) using naive algorithm to check the given string in its inversed string and printing the maximum matched prefix string.But it would result in TLE as the constraints are large (n<=1e6).

But it can be solved easily using KMP which would take O(n+n) time to calculate the answer.

Here process() is used to form an array(generally known as lps[]) of the given string which stores index such that if a mismatch occurs then from which previous index should the comparision be resumed.

kmpsearch() computes the maximum length matched of the given string in its inversed string which is "z" in my case.This method is mostly same as the process method() , the only difference is that kmpsearch() involves both the strings (p & q) whereas process() involves only processing the string to be searched(p).

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("%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,z,a[MAX];
string p,q;

void process(){
    int i,j;
    i=0;j=-1;a[0]=-1;
    while(i<n){
        while(j>=0 && p[i]!=p[j])
            j=a[j];
        i++;j++;
        a[i]=j;
    }
}

void kmpsearch(){
    int i,j;
    i=0;j=0;
    while(i<n){
        while(j>=0 && q[i]!=p[j])
            j=a[j];
        i++;j++;
        z=max(z,j);
    }
}

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

    si(t);
    while(t--){
        clr(a,0);
        cin>>p;
        n=p.size();
        q=p;
        reverse(all(q));
        z=0;
        process();
        kmpsearch();
        rf(i,z-1,0)
            printf("%c",p[i]);
        nl;
    }

    return 0;
}

UVa 10165 - Stone Game

This is a standard question of Nim's Game which has a standard solution that for a person who is starting the game can win only if XOR(^) of no. of stones in all the piles is non-zero.

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("%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(si(n)){
        if(n==0)
            break;
        y=0;
        f(i,0,n){
            si(x);
            y=y^x;
        }
        if(y==0)
            printf("No");
        else
            printf("Yes");
        nl;
    }

    return 0;
}