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

UVa 10036 - Divisibility

It can be solved using 2d DP with the parameters as:

"i"- index of the array
"sum" - (Sum of the elements)%k

 Here recurrence can be defined as :

dp[i][sum]= max((dp[i+1][(sum+a[i])%k]) , (dp[i+1][(sum-a[i])%k]))

           where dp[i][sum] stores "1" if it would lead to dp[n][0] or else "0".

The tricky part of the question is that a[i] can be negative which can cause sum dimension to be negative..

But with some observation it can be solved easily by adding some value in sum and the modified recurrence would look like :

dp[i][sum]= max((dp[i+1][(sum+a[i]+z*k)%k]) , (dp[i+1][(sum-a[i]+z*k)%k]))

          where z=(a[i]/k)+1

Hence now sum can never be negative and it would easily compute the desired answer.

Base Case:

        -->Return "1" when i==n and sum=0.

        -->Return "0" when i>=n. 

//\\__ 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,k,a[MAX];
int dp[10005][105];

int solve(int i,int sum){
    if(i==n && sum==0)
        return 1;
    if(i>=n)
        return 0;
    if(dp[i][sum]!=-1)
        return dp[i][sum];
    int z=a[i]/k;
    z++;
    return dp[i][sum]=max((solve(i+1,(sum+a[i]+z*k)%k)) , (solve(i+1,(sum-a[i]+z*k)%k)));
}

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(dp,-1);
        sii(n,k);
        f(i,0,n){
            si(a[i]);
        }
        if(solve(0,0))
            printf("Divisible\n");
        else
            printf("Not divisible\n");
    }

    return 0;
}

UVa 10004 - Bicoloring

This is a standard bipartite graph question which involves coloring the graph in two colors such that the adjacent vertices never have the same color.

It can be solved easily by applying DFS and passing a parameter color(either "0" or "1") in my case and check for each vertex
--> if its adjacent is unmarked then mark it with a different color  
--> if it is already marked and that too with the same color as the present vertex then bipartite graph cannot be formed(here flag is set to check this).

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,flag,mk[MAX],color[MAX];
vi v[MAX];

int dfs(int x,int c){
    int i;
    mk[x]=1;
    color[x]=c;
    f(i,0,v[x].size()){
        if(!mk[v[x][i]])
            dfs(v[x][i],1-c);
        else if(color[v[x][i]]==color[x])
            flag=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;

    while(si(n)){
        if(n==0)
            break;
        clr(mk,0);
        clr(color,-1);
        si(m);
        f(i,0,m){
            sii(x,y);
            v[x].pb(y);
            v[y].pb(x);
        }
        flag=0;
        dfs(0,0);
        if(flag)
            printf("NOT BICOLORABLE.\n");
        else
            printf("BICOLORABLE.\n");
        f(i,0,n+5)
            v[i].clear();
    }

    return 0;
}

UVa 422 - Word-Search Wonder

Can be solved easily by considering both horizontal,vertical and both diagonals..
If match is found output the answer else print Not found.

//\\__ 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[500],q;

        si(n);
        f(i,0,n)
            cin>>p[i];
        while(cin>>q){
            m=q.size();
            if(q=="0")
                break;
            c=0;
            f(i,0,n){
                c=0;
                f(j,0,n){
                    if(p[i][j]==q[0]){
                        if(j+m<=n){
                            string s;
                            f(k,j,j+m)
                                s+=p[i][k];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+1<<","<<j+m<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(j-m+1>=0){
                            string s;
                            rf(k,j,j-m+1)
                                s+=p[i][k];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+1<<","<<j+2-m<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(i+m<=n){
                            string s;
                            f(k,i,i+m)
                                s+=p[k][j];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+m<<","<<j+1<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(i-m+1>=0){
                            string s;
                            rf(k,i,i-m+1)
                                s+=p[k][j];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+2-m<<","<<j+1<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(i+m<=n && j+m<=n){
                            string s;
                            f(k,0,m)
                                s+=p[i+k][j+k];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+m<<","<<j+m<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(i-m+1>=0 && j-m+1>=0){
                            string s;
                            f(k,0,m)
                                s+=p[i-k][j-k];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+2-m<<","<<j+2-m<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(i+m<=n && j-m+1>=0){
                            string s;
                            f(k,0,m)
                                s+=p[i+k][j-k];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+m<<","<<j+2-m<<endl;
                                c=1;
                                break;
                            }
                        }
                        if(i-m+1>=0 && j+m<=n){
                            string s;
                            f(k,0,m)
                                s+=p[i-k][j+k];
                            if(s==q){
                                cout<<i+1<<","<<j+1<<" "<<i+2-m<<","<<j+m<<endl;
                                c=1;
                                break;
                            }
                        }
                    }
                }
                if(c)
                    break;
            }
            if(!c)
                printf("Not found\n");
        }

    return 0;
}

UVa 11489 - Integer Game

The trick here is to count the numbers%3.
Let the cnt of elements of array  with (num%3==0) be x.
Let the cnt of elements of array  with (num%3==1) be y.
Let the cnt of elements of array  with (num%3==2) be z.

Then the question deals with the rem number should be divisible by 3 after removing an element that means that sum%3==0 after removing an element..
So if initial sum%3==0 then a number with %3==0 can only be removed at all attempts.
If initial sum%3==(1 or 2) then a number with %3==(1 or 2) respectively can be removed at first attempt (if available or S loses) and then %3==0 numbers can only be removed in successive attempts.
So the last person to remove %3==0 element wins the game...

//\\__ 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,tt=1;
    ll ans=0;string p;

    si(t);
    while(t--){
        printf("Case %d: ",tt++);
        cin>>p;
        x=0;y=0;z=0;ans=0;
        n=p.size();
        f(i,0,p.size()){
            l=p[i]-'0';
            if(l%3==0)
                x++;
            else if(l%3==1)
                y++;
            else
                z++;
            ans=(ans+l)%3;
        }
        if(ans==0){
            if(x%2==0)
                r=1;
            else
                r=0;
        }
        else if(ans==1){
            if(n==1)
                r=0;
            else if(y==0)
                r=1;
            else{
                if((x+1)%2==0)
                    r=1;
                else
                    r=0;
            }
        }
        else{
            if(n==1)
                r=0;
            else if(z==0)
                r=1;
            else{
                if((x+1)%2==0)
                    r=1;
                else
                    r=0;
            }
        }
        if(r)
            printf("T");
        else
            printf("S");
        nl;
    }

    return 0;
}

UVa 11450 - Wedding Shopping

Here I have used an adjacency list to v[i][j] which represents "i"th garment "j"th model value.
It can be solved using DP by defining two paramenters to be passed;:
1) "i"th index
2) "sum" obtained till "i"th index
Hence recurrence can be defines as:

for(j=0;j<v[i].size();j++)
    dp[i][sum]=max(dp[i][sum],solve(i+1,sum+v[i][j])).

which represents dp[i][sum]="0" if it is possible to reach value=sum till "i"th index else it would store negative value.

Base Case:
   when i==k && sum<=n --> ans=max(ans,sum)
                  that is on reaching "k"th element ans is the max sum obtained after considering all k values.
    when i>=k or sum>n  return -INF
                  as this value cannot be included in total as it exceeds the required value..

No Solution can be checked when included the lowest value of all "k" elements exceeds the required total value "n".

Top-Down Approach:

//\\__ 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[30][500],k;

vi v[50];

int solve(int i,int sum){
    int j,z=0;
    if(i==k && sum<=n)
        return dp[i][sum]=0;
    if(i>=k || sum>n)
        return -1e5;
    if(dp[i][sum]!=-1)
        return dp[i][sum];
    f(j,0,v[i].size())
        z=max(z,solve(i+1,sum+v[i][j]));
    return dp[i][sum]=z;
}

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(dp,-1);
        c=0;
        sii(n,k);
        f(i,0,k){
            si(x);
            f(j,0,x){
                si(y);
                v[i].pb(y);
            }
        }
        f(i,0,k)
            sort(all(v[i]));
        z=0;
        f(i,0,k)
            z+=v[i][0];
        if(z>n)
            c=1;
        if(c)
            printf("no solution\n");
        else{
            solve(0,0);
            rf(i,300,0){
                if(dp[k][i]!=-1)
                    break;
            }
            pi(i);
        }
        f(i,0,k+5)
            v[i].clear();
    }
    return 0;
}

UVa 10313 - Pay the Price

Problem : UVa 10313 - Pay the Price 

Here dp[i][j][k] means --: 

 "i" -- The last coin used

 "j" -- Total sum obtained

 "k" -- "No. of coins taken"

It can be calculated as:

dp[i][j][k]=dp[i-1][j][k]+dp[i][j-i][k-1].

where 1st condition is (when "i"th coin is not taken) and "2"nd condition is (when "i"th coin is taken so subtracting its value from sum-"j" and decreasing "k" as one coin is used.).It can be calculated by both Bottom-up Approach and Top-down Method just need a little optimisation to pass under the given constraints..

*Take care of corner cases like n=0 because there is 1 way to get 0 using 0 coins so::

Input :

0
0 0
0 1
0 0 0
0 0 1
0 1 1
0 1 2
200 30 75 

Output:

1
1
1
1
1
0
0
2347163627458

Top-Down Method :

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

ll n,m,dp[400][400][400];
char s[400];

ll solve(ll i,ll j,ll k){
    if(j==0 && k==0)
        return 1;
    if( i<1 || j<1 || k<=0)
        return 0;
    if(dp[i][j][k]!=-1)
        return dp[i][j][k];
    return dp[i][j][k]=solve(i-1,j,k)+solve(i,j-i,k-1);
}

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

// dp is cleared only once so previous values are automatically taken from dp and only new values are computed again otherwise would result in TLE.


    clr(dp,-1);
    while(gets(s)){
        z=sscanf(s,"%lld %lld %lld",&n,&l1,&l2);
        ans=0;
        if(z==1){
            f(i,1,min(n+1,301LL))
                ans+=solve(n,n,i);
            if(n==0)
                ans=1;
        }
        else if(z==2){
            f(k,1,min(l1+1,301LL))
                ans+=solve(n,n,k);
            if(n==0)
                ans=1;
        }
        else{
            f(k,l1,min(l2+1,301LL))
                ans+=solve(n,n,k);
            if(n==0 && l1==0)
                ans=1;
        }
        pi(ans);

    }

    return 0;
}

Bottom-Up Approach :

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

ll n,m,dp[400][400][400];

char s[300];

int main(){

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

    ll ans=0;string p,q[5];

    for(k=0;k<=300;k++){

        for(j=0;j<=300;j++){

            for(i=0;i<=300;i++){

                if(j==0 && k==0 && i!=0)

                    dp[i][j][k]=1;

                else if(i==0 || j==0 || k==0)

                    dp[i][j][k]=0;

                else{

                    dp[i][j][k]=dp[i-1][j][k];

                    if(j-i>=0 && k-1>=0)

                        dp[i][j][k]+=dp[i][j-i][k-1];

                }

            }

        }

    }

// 1D range sum is used to sum the result where dp[i][i][k] is the total ways to obtain sum "i" using "k" or less coins.

    for(i=1;i<=300;i++)

        for(j=1;j<=300;j++)

            dp[i][i][j]+=dp[i][i][j-1];

    while(gets(s)){

        z=sscanf(s,"%lld %lld %lld",&n,&l1,&l2);

        ans=0;

        if(z==1){

            z=min(n,300LL);

            ans=dp[n][n][z];

            if(n==0)

                ans=1;

        }

        else if(z==2){

            z=min(l1,300LL);

            ans=dp[n][n][z];

            if(n==0 && l1<=1)

                ans=1;

        }

        else{

            z=min(l2,300LL);

            y=max(l1-1,0LL);

            ans=dp[n][n][z]-dp[n][n][y];

            if(n==0 && l1==0)

                ans=1;

        }

        pi(ans);

    }

    return 0;

}