UVA 10911 - Forming Quiz Teams

#include <bits/stdc++.h>
using namespace std;
int mx,n,x[20],y[20];
double dist[20][20],dp[1<<16];
double call(int pos)
{
    if(pos==mx)
        return 0;
    else if(dp[pos]!=-1)
        return dp[pos];
    else
    {
        int i,j;
        double d=1<<30;
        for(i = 0; i<2*n; i++)
        {
            if(!(pos&(1<<i)))
            {
                for(j=i+1; j<2*n; j++)
                {
                    if(!(pos&(1<<j)))
                    {
                        d = min(d,dist[i][j]+call(pos|(1<<i)|(1<<j)));
                    }
                }
            }
        }
        return dp[pos]=d;
    }
}
double dis(int i, int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

int main()
{
    char name[20];
    int i,j,cs=1;
    scanf("%d",&n);
    while(n)
    {
        mx = (1<<(2*n))-1;
        for(i=0; i<2*n; i++)
            scanf("%s %d %d",name,x+i,y+i);
        for(i=0; i<2*n; i++)
            for(j=i+1; j<2*n; j++)
                dist[i][j]=dist[j][i]=dis(i,j);
        for(i=0; i<=mx; i++)
            dp[i]=-1;
        printf("Case %d: %.2lf\n",cs++,call(0));
        scanf("%d",&n);
    }
    return 0;
}

UVA 10344 23 Out of 5

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long flag=0,ar[10]={0},vis[10];
void call(long pos,long sum)
{
    if(pos==5&&sum==23)
    {
        flag=1;
        return;
    }
    else
    {
        for(long i=0;i<5;i++)
        {
            if(vis[i]==0)
            {
                vis[i]=1;
                call(pos+1,sum+ar[i]);
                call(pos+1,sum*ar[i]);
                call(pos+1,sum-ar[i]);
                vis[i]=0;
            }
        }
    }
}
main()
{
    timesave;
    long a,b,c,d,e;
    while(cin>>a>>b>>c>>d>>e)
    {
        if(a==0&&b==0&&c==0&&d==0&&e==0)
            break;
        else
        {
            ar[0]=a;
            ar[1]=b;
            ar[2]=c;
            ar[3]=d;
            ar[4]=e;
        }
        flag=0;
        long i;
        for(i=0;i<5;i++)
        {
            vis[i]=1;
            call(1,ar[i]);
            vis[i]=0;
        }
        if(flag==1)
        {
            cout<<"Possible"<<endl;
        }
        else
            cout<<"Impossible"<<endl;
    }
}

UVA 10003 Cutting Sticks

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
int l, n, c[55], dp[55][55];
int recurse(int left, int right)
{
    if(dp[left][right] != -1)
        return dp[left][right];
    if(left + 1 == right)
        return dp[left][right] = 0;
    int best = 1000000;
    for(int i = left + 1; i < right; i++)
    {
        best = min(best, recurse(left, i) + recurse(i, right) + c[right] - c[left]);
    }
    return dp[left][right] = best;
}
int main()
{
    while(cin>>l)
    {
        if(l == 0)
            break;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &c[i]);
        c[0] = 0;
        c[n + 1] = l;

        memset(dp, -1, sizeof dp);

        printf("The minimum cutting is %d.\n", recurse(0, n + 1));
    }
}

UVA 10131- Is Bigger Smarter?

W[a[1]] < W[a[2]] < ... < W[a[n]]
S[a[1]] > S[a[2]] > ... > S[a[n]]


Now find the LCS which maintains the rules?


Sample Input:
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900 

Sample Output:
4
4
5
9
7

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

#define M 10001
struct node
{
    int W;
    int IQ;
    int id;
} ar[M];
bool comp(node a,node b)
{
    if(a.W != b.W)
        return a.W < b.W;
    return a.IQ > b.IQ;
}
int main()
{
    int n=0,L[M],ans[M],LIS;
     while(scanf("%d %d",&ar[n].W,&ar[n].IQ)==2)
    {
        ar[n].id=n+1;
        n++;
    }
    if(n==0)
        return 0;
    sort(ar,ar+n,comp);
    for(int i=0;i<n;i++)
        L[i]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(ar[j].W<ar[i].W&&ar[j].IQ>ar[i].IQ)
                L[i] = max(L[j] + 1, L[i]);
    int pos=0;
    for(int i=0;i<n;i++)
        if(L[i]>L[pos])
            pos = i;
    LIS = L[pos];
    printf("%d\n",LIS);
    int top=L[pos] - 1;
    ans[top]=ar[pos].id;
    for(int j=pos-1;j>=0;j--)
    {
        if(L[j]==L[pos]-1&&ar[j].W <ar[pos].W&&ar[j].IQ>ar[pos].IQ)
        {
            ans[--top]=ar[j].id;
            pos = j;
        }
    }
    for(int i=0;i<LIS;i++)
        printf("%d\n",ans[i]);
    return 0;
}

LOJ 1348 - Aladdin and the Return Journey

এখানে একটা গ্রাফ দেওয়া থাকবে এখন দুইটা অপারেশন দেবে
অপারেসনে বলবে যে ১ দিলে i নাম্বার নোডে  V আপডেট হবে
আর ০ দিলে i to j এর মধ্যে  টোটাল কত টা জিনি আছে সেইটা বলা লাগবে
প্রতিটা নোডে প্রথমে কত টা জিনি আছে সেইটা আগে থেকে বলে দেওয়া হবে

Input starts with an integer T (≤ 10), denoting the number of test cases.
Each Case starts with a blank line. Next line contains an integer n (2 ≤ n ≤ 30000). The next line contains n space separated integers between 0 and 1000, denoting the number of genies in the nodes respectively. Then there are n-1 lines each containing two integers: u v (0 ≤ u, v < n, u ≠ v) meaning that there is an edge from node u and v. Assume that the edges form a valid tree. Next line contains an integer q (1 ≤ q ≤ 10^5) followed by q lines each containing a query as described above.

উদাহরণ:

INPUT:
1
4
10 20 30 40
0 1
1 2
1 3
3
0 2 3
1 1 100
0 2 3

OUTPUT:

Case 1:

90

170

#include<bits/stdc++.h>
using namespace std;
#define D(x) cout<< #x " = "<< (x)<<endl
const int MAXM = 16;
const int MAXN = 1 << MAXM;
struct bit
{
    long long v[MAXN];
    int maxSize;
    void init(int n)
    {
        maxSize = n;
        memset(v, 0, sizeof v);
    }
    void add(int where, long long what)
    {
        for (where++; where <= maxSize; where += where & -where)
        {
            v[where] += what;
        }
    }
    long long query(int where)
    {
        long long sum = v[0];
        for (where++; where > 0; where -= where & -where)
        {
            sum += v[where];
        }
        return sum;
    }
    long long query(int from, int to)
    {
        return query(to) - query(from-1);
    }

};
bit ft;
int n;
int val[MAXN];
struct TreeDecomposition
{
    vector<int> g[MAXN], c[MAXN];
    int s[MAXN]; // subtree size
    int p[MAXN]; // parent id
    int r[MAXN]; // chain root id
    int t[MAXN]; // index used in segtree/bit/...
    int d[MAXN]; // depht
    int ts;
    void dfs(int v, int f)
    {
        p[v] = f;
        s[v] = 1;
        if (f != -1)
            d[v] = d[f] + 1;
        else
            d[v] = 0;
        for (int i = 0; i < g[v].size(); ++i)
        {
            int w = g[v][i];
            if (w != f)
            {
                dfs(w, v);
                s[v] += s[w];
            }
        }
    }
    void hld(int v, int f, int k)
    {
        ft.add(ts, val[v]);
        t[v] = ts++;
        c[k].push_back(v);
        r[v] = k;
        int x = 0, y = -1;
        for (int i = 0; i < g[v].size(); ++i)
        {
            int w = g[v][i];
            if (w != f)
            {
                if (s[w] > x)
                {
                    x = s[w];
                    y = w;
                }
            }
        }
        if (y != -1)
        {
            hld(y, v, k);
        }
        for (int i = 0; i < g[v].size(); ++i)
        {
            int w = g[v][i];
            if (w != f && w != y)
            {
                hld(w, v, w);
            }
        }
    }
    void init(int n)
    {
        for (int i = 0; i < n; ++i)
        {
            g[i].clear();
        }
    }
    void add(int a, int b)
    {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void build()
    {
        ts = 0;
        dfs(0, -1);
        hld(0, 0, 0);
    }
};
TreeDecomposition tree;
int magic(int a, int b)    // C : LCA btwn a and b
{
    if ( tree.r[a] == tree.r[b] )
    {
        int ia = tree.t[a];
        int ib = tree.t[b];
        if (ia > ib)
            swap(ia,ib);
        return ft.query(ia, ib);
    }
    int ans = 0;
    if (tree.d[tree.r[a]] > tree.d[tree.r[b]])
    {
        ans += ft.query(tree.t[tree.r[a]], tree.t[a]) +  magic(tree.p[tree.r[a]], b);
    }
    else
    {
        ans += ft.query(tree.t[tree.r[b]], tree.t[b]) +  magic(tree.p[tree.r[b]], a);
    }
    return ans;
}
void solve()
{
    scanf("%d", &n);
    tree.init(n+1);
    ft.init(n+1);
    for (int i = 0; i < n; ++i)
        scanf("%d", val + i);
    int u, v;
    for (int i = 0; i < (n - 1); ++i )
    {
        scanf("%d%d", &u,&v);
        tree.add(u,v);
    }
    tree.build();
    int queries;
    scanf("%d", &queries);
    int type, a, b;
    while (queries-- )
    {
        scanf("%d%d%d", &type, &a, &b);
        if (type)
        {
            int idx = tree.t[a];
            ft.add(idx, -ft.query(idx,idx));
            ft.add(idx, b);
        }
        else
        {
            printf("%d\n",magic(a, b));
        }
    }
}
int main()
{
    int tc;
    scanf("%d", &tc);
    for (int i = 0; i < tc; ++i)
    {
        printf("Case %d:\n", i+1);
        solve();
    }
    return 0;
}

LIGHT OJ-1081(Square Queries)

একটা ম্যাট্রিক্স দেওয়া থাকবে N*N গ্রিড এর
বের করা লাগবে
(I, J) to (I+S-1, J+S-1)  
এইটার মধ্যে ম্যাক্সিমাম মান কে? 
উদাহরণঃ 
ইনপুটঃ 

1

4 5

67  1  2  3

8  88  21  1

89  12  0  12

5  5  5  5

1 1 2

1 3 2

3 3 2

1 1 4

2 2 3

OUTPUT:
Case 1:
88
21
12
89
88

#include <bits/stdc++.h>
#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))
using namespace std;
int n,q;
int ara[505][505];
int sparse[505][505][16];
void build()
{
    for(int k=0; (1<<k)<=n; k++)
    {
        for(int i=0; i+(1<<k)-1<n; i++)
            for(int j=0; j+(1<<k)-1<n; j++)
            {
                if(k==0)
                    sparse[i][j][k]=ara[i][j];
                else
                {
                    int a=1<<(k-1);
                    sparse[i][j][k]=max(max(sparse[i][j][k-1],sparse[i+a][j][k-1]),max(sparse[i][j+a][k-1],sparse[i+a][j+a][k-1]));
                }
            }
    }
}
int main()
{
    int t;
    sf(t);
    TEST_CASE(t)
    {
        sff(n,q);
        loop(i,n) loop(j,n) sf(ara[i][j]);
        build();
        PRINT_CASE;
        while(q--)
        {
            int i,j,s;
            sfff(i,j,s);
            int k=log2(s);
            int a=1<<k;
            i--;
            j--;
            int ans=max(max(sparse[i][j][k],sparse[i+s-a][j][k]),max(sparse[i][j+s-a][k],sparse[i+s-a][j+s-a][k]));
            pf("%d\n",ans);
        }
    }
    return 0;
}

SPOJ PARTY - Party Schedule

Write a program which finds this optimal set of parties that offer the most fun. Keep in mind that your budget need not necessarily be reached exactly. Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.

INPUT:
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

OUTPUT:

49 26

48 32

#include <bits/stdc++.h>
#define INF 1000000000
#define MOD 1000000007
#define MAXN 1000005
#define ins insert
#define pb push_back
#define mp make_pair
#define sz size
#define rep(i, n) for(int i = 0; i < n; ++i)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%I64d",&n)
#define pdn(n) printf("%d\n",n)
#define plln(n) printf("%I64d\n",n)
#define pd(n) printf("%d ",n)
#define nl() printf("\n")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef vector<vi> vii;
typedef pair<int, int> pii;

int budget, parties;

int fun[101], fee[101];

int dp[101][501];

int solve(int idx, int rembudget)
{
    if(rembudget == 0)
        return 0;
    if(rembudget < 0)
        return 0;
    if(idx < 0)
        return 0;
    if(dp[idx][rembudget] != -1)
        return dp[idx][rembudget];
    int pr1 = 0, pr2 = 0;

    if(rembudget-fee[idx] >= 0)
        pr1 = fun[idx]+solve(idx-1, rembudget-fee[idx]);

    pr2 = solve(idx-1, rembudget);

    return dp[idx][rembudget] = max(pr1, pr2);
}

int main()
{
    while((cin >> budget >> parties) && (budget) && (parties))
    {
        for(int i = 0; i < 101; ++i)
            for(int j = 0; j < 501; ++j)
                dp[i][j] = -1;
        for(int i = 0; i < parties; ++i)
        {
            cin >> fee[i] >> fun[i];
        }
        for(int i = 0; i < 501; ++i)
            solve(parties-1, i);
        int ans = solve(parties-1, budget);
        int currmin = INF;
        for(int i = 0; i < 501; ++i)
        {
            if(dp[parties-1][i] == ans)
            {
                currmin = i;
                break;
            }
        }
        cout << currmin << " " << ans << endl;
    }
    return 0;

}

UVA 624 - CD

#include<bits/stdc++.h>
#define READ freopen("input.txt","r",stdin);
using namespace std;
typedef long long ll;
int target,n,ary[50];
vector<int>temp,res;
void call(int i,int sum,int c)
{
    if(i>=n)
    {
        int s=0,s2=0;
        for(int i=0; i<temp.size(); i++)
            s+=temp[i];
        for(int i=0; i<res.size(); i++)
            s2+=res[i];
        if(s>=s2)
        {
            if(s==s2)
            {
                if(temp.size()>res.size())
                    res=temp;
            }
            else
                res=temp;
        }
        return ;
    }
    if(sum+ary[i]<=target)
    {
        temp.push_back(ary[i]);
        call(i+1,sum+ary[i],c+1);
        temp.pop_back();
        c--;
    }
    else
        call(i+1,sum,c);
    call(i+1,sum,c);
}
int main()
{
    while(scanf("%d %d",&target,&n)==2)
    {
        temp.clear();
        res.clear();
        for(int i=0; i<n; i++)
            scanf("%d",&ary[i]);
        call(0,0,0);
        int s=0;
        for(int i=0; i<res.size(); i++)
        {
            s+=res[i];
            printf("%d ",res[i]);
        }
        printf("sum:%d\n",s);
    }
    return 0;
}

UVA 10739 - String to Palindrome

In this problem you are asked to convert a string into a palindrome with minimum number of operations. The operations are described below: Here you’d have the ultimate freedom. You are allowed to:
 • Add any character at any position
 • Remove any character from any position
• Replace any character at any position with another character
Print the minimum number of characters needed to turn the given string into a palindrome


INPUT:
6
tanbirahmed
shahriarmanzoor
monirulhasan
syedmonowarhossain
sadrulhabibchowdhury
mohammadsajjadhossain

OUTPUT:
Case 1: 5
Case 2: 7
Case 3: 6
Case 4: 8
Case 5: 8
Case 6: 8



#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>

using namespace std;

int table[1010][1010];
int main()
{
    int test,t,i,j,len;
    char x[1010],y[1010];
    scanf("%d",&test);
    t=1;
    while(t<=test)
    {
        scanf("%s",x);
        len=strlen(x);
        strcpy(y,x);
        reverse(y,y+len);
        for(i=0; i<=len; i++)
            table[i][0]=i;
        for(j=0; j<=len; j++)
            table[0][j]=j;
        for(i=1; i<=len; i++)
        {
            for(j=1; j<=len; j++)
            {
                if(x[i-1]==y[j-1])
                    table[i][j]=table[i-1][j-1];
                else
                    table[i][j]=min(table[i-1][j-1],min(table[i-1][j],table[i][j-1]))+1;
            }
        }
        printf("Case %d: %d\n",t++,table[len][len]/2);
    }
    return 0;
}

UVA 10100 - Longest Match

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a, b;
    int t = 0;
    while (getline(cin, a))
    {
        t++;
        getline(cin, b);
        if (a.length() == 0 || b.length() == 0)
            printf("%2d. Blank!\n", t);
        else
        {
            for (int i = 0; i < a.length(); i++)
                if (!(a[i] >= 'A' && a[i] <= 'Z' || a[i] >= 'a' && a[i] <= 'z' || a[i] >= '0' && a[i] <= '9'))
                    a[i] = ' ';
            for (int i = 0; i < b.length(); i++)
                if (!(b[i] >= 'A' && b[i] <= 'Z' || b[i] >= 'a' && b[i] <= 'z' || b[i] >= '0' && b[i] <= '9'))
                    b[i] = ' ';
            string c[501], d[501];
            istringstream strma(a);
            int n = 1;
            while (strma >> c[n])
                n++;
            istringstream strmb(b);
            int m = 1;
            while (strmb >> d[m])
                m++;
            int T[501][501];
            for (int j = 0; j < m; j++)
                T[0][j] = 0;
            for (int i = 1; i < n; i++)
            {
                T[i][0] = 0;
                for (int j = 1; j < m; j++)
                    if (c[i] == d[j])
                    {
                        T[i][j] = T[i - 1][j - 1] + 1;
                    }

                    else
                        T[i][j] = max(T[i - 1][j], T[i][j - 1]);
            }
            printf("%2d. Length of longest match: %d\n", t, T[n - 1][m - 1]);
        }
    }
    return 0;
}

UVA 10616 - Divisible Group Sums

#include<bits/stdc++.h>
using namespace std;
int n,m,d,q;
int ar[205],vis[205][205][15];
int dp(int i,int sum,int c)
{
    if(c==m&&sum==0)
        return 1;
    if(c==m&&sum!=0)
        return 0;
    if(i==n)
        return 0;
    if(vis[i][sum][c] != -1)
        return vis[i][sum][c];
    vis[i][sum][c] = dp(i+1, sum%d, c) + dp(i+1, (sum+ar[i])%d, c+1);
    return vis[i][sum][c];
}
int main()
{
    int i, j, res;
    j = 1;
    while(cin>>n>>q)
    {
        if(n==0&&q==0)
            break;
        for(i=0;i<n;i++)
        {
            scanf("%d",&ar[i]);
        }
        printf("SET %d:\n", j);
        for(i = 0; i < q; i++)
        {
            scanf("%d%d",&d,&m);
            memset(vis,-1,sizeof(vis));
            res = dp(0, 0, 0);
            printf("QUERY %d: %d\n", i+1, res);
        }
        j++;
    }
    return 0;
}

UVA 10878 - Decode the tape

#include<stdio.h>
char s[64];
int main()
{
    int i;
    int sum, found;
    while(gets(s))
    {
        int bit = 128;
        i = sum = found = 0;
        if(s[i] != '|')
            continue;
        for(;s[i];++i)
        {
            if(s[i]==' ')
                bit>>= 1;
            else if(s[i] == 'o')
            {
                sum += bit;
                bit >>= 1;
            }
        }
        printf("%c", sum);
    }
    return 0;
}

UVA 12662 - Good Teacher

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

int main()
{
    int n, q, x;
    char s[105][10];
    while(scanf("%d", &n) == 1)
    {
        for(int i = 1; i <= n; i++)
            scanf("%s", s[i]);
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d", &x);
            if(strcmp(s[x], "?"))
                puts(s[x]);
            else
            {
                int l, r, p;
                l = r = 0;
                p = x - 1;
                while(p > 0 && !strcmp(s[p], "?"))
                    p--, l++;
                if(p <= 0)
                    l = 0x3f3f3f;
                p = x + 1;
                while(p <= n && !strcmp(s[p], "?"))
                    p++, r++;
                if(p > n)
                    r = 0x3f3f3f;
                l++, r++;
                if(l == r)
                    printf("middle of %s and %s\n", s[x - l], s[x + r]);
                else if(l < r)
                {
                    for(int j = 0; j < l; j++)
                        printf("right of ");
                    printf("%s\n", s[x - l]);
                }
                else
                {
                    for(int j = 0; j < r; j++)
                        printf("left of ");
                    printf("%s\n", s[x + r]);
                }
            }
        }
    }
    return 0;
}

11309 - Counting Chaos

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

bool isPal(int h, int m)
{
    vector<int> vec, tmp, vec2 ;
    if(h == 0)
    {
        if(m < 10)
            return true;
        else
        {
            while(m != 0)
            {
                vec.push_back(m%10);
                m/=10;
            }
            tmp = vec;
            reverse(vec.begin(), vec.end());
            if(vec == tmp)
                return true;
            else
                return false;
        }
    }
    else
    {
        while(h != 0)
        {
            vec.push_back(h % 10);
            h/=10;
        }
        reverse(vec.begin(), vec.end());

        if(m<10)
            vec.push_back(0);
        while(m != 0)
        {
            vec2.push_back(m % 10);
            m/=10;
        }
        reverse(vec2.begin(), vec2.end());

        vec.insert(vec.end(), vec2.begin(), vec2.end());
        tmp = vec;
        reverse(vec.begin(), vec.end());
        if(vec == tmp)
            return true;
        else
            return false;
    }
}

int main()
{
    int casos, hh, mm;
    bool flag = 0;
    scanf("%d", &casos);
    while(casos--)
    {
        scanf("%d:%d", &hh, &mm);
        flag = false;

        while(flag != 1)
        {
            mm++;
            if(mm == 60)
            {
                mm = 0;
                hh++;
                if(hh == 24)
                    hh = 0;
            }
            if(isPal(hh,mm))
            {
                flag = true;
                if(hh < 10)
                    printf("0");
                printf("%d:", hh);
                if(mm<10)
                    printf("0");
                printf("%d\n", mm);
            }
        }
    }
    return 0;
}

UVA 12195 - Jingle Composing

#include<stdio.h>
int main()
{
    char s[201];
    while(gets(s))
    {
        if(s[0] == '*')
            break;
        int st = 0, i, find = 0, Sum = 0;
        for(i = 1; s[i]; i++)
        {
            if(s[i] == '/')
            {
                if(Sum == 1000000)
                    find++;
                Sum = 0;
            }
            switch(s[i])
            {
            case 'W':
                Sum += 1000000;
                break;
            case 'H':
                Sum +=  500000;
                break;
            case 'Q':
                Sum +=  250000;
                break;
            case 'E':
                Sum +=  125000;
                break;
            case 'S':
                Sum +=   62500;
                break;
            case 'T':
                Sum +=   31250;
                break;
            case 'X':
                Sum +=   15625;
                break;
            }
        }
        printf("%d\n", find);
    }
    return 0;
}

UVA 10589 - Area

#include <stdio.h>

int main()
{
    int n, a;
    while(scanf("%d %d", &n, &a)!=EOF)
    {
        if(n == 0 && a == 0)
            break;
        int m = 0, i;
        double x, y;
        for(i = 0; i < n; i++)
        {
            scanf("%lf %lf", &x, &y);
            if(x*x+y*y <= a*a && (x-a)*(x-a)+y*y <= a*a &&
                    x*x+(y-a)*(y-a) <= a*a && (x-a)*(x-a)+(y-a)*(y-a) <= a*a)
                m++;
        }
        printf("%.5lf\n", (double)m*a*a/n);
    }
    return 0;
}