UVa 10954 Add All

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n,x;

    while(scanf("%d", &n)==1 and n)
    {
        priority_queue<int> pq;
        // priority_queue < int, vector<int>, greater<int> > pq;


        REP(i,n)
        {
            scanf("%d", &x);
            pq.push(-x);
        }
        LL sm = 0;
        while(SZ(pq)>1)
        {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            sm += -(a+b);
            pq.push(a+b);
        }
        printf("%lld\n", sm);
    }
    return 0;
}

UVa 11577 Letter Frequency

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int cnt[27];
    int t;
    string s;
    scanf("%d",&t);
    cin.ignore();
    while(t--)
    {
        memset(cnt,0,sizeof cnt);
        getline(cin,s);
        int mx = 0;
        REP(i,SZ(s))
        {
            if((s[i]>='a' and s[i]<='z') or (s[i]>='A' and s[i]<='Z'))
            {
                s[i] = tolower(s[i]);
                int tt = s[i]-'a';
                cnt[tt]++;
                mx = max(mx,cnt[tt]);
            }
        }

        REP(i,27) if(cnt[i]==mx) putchar(i+'a');
        puts("");
    }
    return 0;
}

UVa 10530 Guessing Game

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n;
    vector <int> th, tl;
    string s;

    while(cin>>n)
    {
        if(n==0) return 0;

        cin.ignore();
        getline(cin,s);

        if(s=="too low")
        {
            tl.push_back(n);
        }
        else if(s=="too high")
        {
            th.push_back(n);
        }
        else
        {
            bool fl = false;

            REP(i,SZ(tl))
            {
                if(n<=tl[i]){fl=true; break;}
            }
            REP(i,SZ(th))
            {
                if(n>=th[i]){fl=true; break;}
            }

            if(fl) puts("Stan is dishonest");
            else puts("Stan may be honest");

            tl.clear(); th.clear();
        }
    }
    return 0;
}

UVa 12570 Keep Rafa At Chelsea

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n,T,cs=0;
    char ch;
    cin>>T;
    while(T--)
    {
        printf("Case %d: ",++cs);
        cin>>n;
        int ls=0, res, fl=0;
        REP(i,n)
        {
            cin>>ch;
            if(ch=='D') ls++;
            else if(ch=='L') ls++;
            else ls=0;

            if(ls>=3 and !fl) {fl=1,res = i+1;}
        }
        if(!fl) puts("Yay! Mighty Rafa persists!");
        else pri(res);
    }
    return 0;
}

UVa 12342 Tax Calculator

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

LL per(LL n, LL x)
{
    LL res = ceil((double)((n*x)/(100*1.0)));
    return res;
}

int main()
{
    int n,T,cs=0;
    scanf("%d", &T);
    while(T--)
    {
        LL tx = 0;
        printf("Case %d: ", ++cs);

        cin>>n;

        if(n>(180000+300000+400000+300000))
        {
            tx += 0+per(300000,10)+per(400000,15)+per(300000,20)+per(n-(180000+300000+400000+300000),25);
        }
        else if(n>(180000+300000+400000))
        {
            tx += 0+per(300000,10)+per(400000,15)+per(n-(180000+300000+400000),20);
        }
        else if(n>(180000+300000))
        {
            tx += 0+per(300000,10)+per(n-(180000+300000),15);
        }
        else if(n>(180000))
        {
            tx += 0+per(n-(180000),10);
        }
        else tx = 0;

        if(tx>0 and tx<2000) tx=2000;

        pri(tx);
    }
    return 0;
}

UVa 10684 The Jackpot

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int main()
{
    int n,a[12345];

    while(cin>>n and n)
    {
        REP(i,n) cin>>a[i];
        LL sm=0,res=0;
        REP(i,n)
        {
            sm += a[i];
            if(sm<=0) sm = 0;
            else res = max(sm,res);
        }
        if(res>0) printf("The maximum winning streak is %lld.\n", res);
        else puts("Losing streak.");
    }
    return 0;
}

SPOJ/LightOJ 1164 Horrible Queries

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

#define sz 100007
LL a[sz], tr[sz*4], prop[sz*4];

void update(int node, int b, int e, int i, int j, LL val)
{
    if(b>=i and e<=j)
    {
        tr[node] += (e-b+1)*val;
        prop[node] += val;
        return;
    }
    int mid=(b+e)>>1;
    int lft=node<<1 ,rgt=lft+1;

    if(j<=mid) update(lft,b,mid,i,j,val);
    else if(i>mid) update(rgt,mid+1,e,i,j,val);
    else
    {
        update(lft,b,mid,i,j,val);
        update(rgt,mid+1,e,i,j,val);
    }
    tr[node] = tr[lft] + tr[rgt] + prop[node]*(e-b+1);
}

LL query(int node, int b, int e, int i, int j, LL car)
{
    if(b>=i and e<=j)
    {
        return tr[node]+car*(e-b+1);
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) query(lft,b,mid,i,j,car+prop[node]);
    else if(i>mid) query(rgt,mid+1,e,i,j,car+prop[node]);
    else
    {
        return (query(lft,b,mid,i,j,car+prop[node]) + query(rgt,mid+1,e,i,j,car+prop[node]));
    }
}

int main()
{
   // freopen("F:\out.txt", "w", stdout);
    int n,qu,T,op,p,q,v,cs=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(tr, 0, sizeof tr);
        memset(prop, 0, sizeof prop);
       // printf("Case %d:\n",++cs);
        scanf("%d%d",&n,&qu);
        REP(i,qu)
        {
            scanf("%d", &op);

            if(op==0)
            {
                scanf("%d%d%d",&p,&q,&v);
                p--,q--;
                update(1,0,n-1,p,q,v);
            }
            else if(op==1)
            {
                scanf("%d%d",&p,&q);
                p--,q--;
                LL res = query(1,0,n-1,p,q,0);
                printf("%lld\n", res);
            }
        }
    }

    return 0;
}

LightOJ 1093 Curious Robinhood

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;
#define sz 100007

int ar[sz],tr[3*sz];

void build(int node, int b, int e)
{
    if(b==e)
    {
        tr[node] = ar[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = tr[lft] + tr[rgt];
}

int query(int node, int b, int e, int i, int j)
{
    if(i<=b and j>=e) return tr[node];
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;
    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return (query(lft,b,mid,i,j) + query(rgt,mid+1,e,i,j));
}

void update(int node, int b, int e, int idx, int val)
{
    if(b==e)
    {
        ar[b] += val;
        tr[node] = ar[b];
        return;
    }

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;

    if(idx<=mid) update(lft,b,mid,idx,val);
    else if(idx>mid) update(rgt,mid+1,e,idx,val);
    tr[node] = tr[lft] + tr[rgt];
}


int main()
{
    int T,n,q,x,idx,val,lt,rt,cs=0;
    scanf("%d", &T);
    while(T--)
    {
        printf("Case %d:\n", ++cs);
        scanf("%d%d", &n, &q);

        REP(i,n) scanf("%d", &ar[i+1]);

        build(1,1,n);

        REP(i,q)
        {
            scanf("%d", &x);

            if(x==1)
            {
                scanf("%d", &idx);
                printf("%d\n", ar[idx+1]);
                ar[idx+1] = 0;
                update(1,1,n,idx+1,0);
            }
            else if(x==2)
            {
                scanf("%d%d", &idx, &val);
                update(1,1,n,idx+1,val);
            }
            else if(x==3)
            {
                scanf("%d%d", &lt, &rt);
                printf("%d\n",query(1,1,n,lt+1,rt+1));
            }
        }
    }
    return 0;
}

UVa 12532 Interval Product

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

#define sz 100007
int a[sz], tr[sz*4];

void build(int node,int b,int e)
{
    if(b==e)
    {
        tr[node] = a[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = tr[lft] * tr[rgt];
}

int query(int node, int b, int e, int i, int j)
{
    if(i<=b and e<=j) return tr[node];

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return (query(lft,b,mid,i,j) * query(rgt,mid+1,e,i,j));
}

void update(int node, int b, int e, int idx, int val)
{
    if(b==e)
    {
        a[idx] = val;
        tr[node] = val;
        return;
    }
 
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;

    if(idx<=mid)
        update(lft,b,mid,idx,val);
    else if(idx>mid)
        update(rgt,mid+1,e,idx,val);

    tr[node] = tr[lft] * tr[rgt];
}

int main()
{
    int n,q,x,y;
    char ch;
    string tst;

    while(cin>>n>>q)
    {
        tst = "";

        REP(i,n)
        {
            cin>>x;

            if(x>0) x=1;
            else if(x<0) x=-1;

            a[i+1] = x;
        }

        build(1,1,n);

        REP(i,q)
        {
            cin>>ch;
            if(ch=='C')
            {
                int idx,val;
                cin>>idx>>val;

                if(val>0) val = 1;
                else if(val<0) val = -1;

                update(1,1,n,idx,val);
            }
            else if(ch=='P')
            {
                cin>>x>>y;
                int res = query(1,1,n,x,y);
                if(res==0) tst+="0";
                else if(res>0) tst+="+";
                else tst+="-";
            }
        }
        pri(tst);
    }
    return 0;
}

UVa 11235 Frequent Values

#include <bits/stdc++.h>
#define LL long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

#define sz 100007
int a[sz], ltfrq[sz], rtfrq[sz], tr[4*sz];

void build(int node, int b, int e)
{
    if(b==e)
    {
        tr[node] = ltfrq[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = max(tr[lft], tr[rgt]);
}

int query(int node, int b, int e, int i, int j)
{
    if(b>=i and e<=j) return tr[node];

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft+1;

    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return max(query(lft,b,mid,i,j), query(rgt,mid+1,e,i,j));
}

int main()
{
    int n,q,l,r,res;
    while(scanf("%d", &n)==1 and n!=0)
    {
        scanf("%d",&q);
        REP(i,n) scanf("%d",&a[i+1]);

        ltfrq[1] = 1;
        FOR(i,2,n)
        {
            if(a[i]==a[i-1]) ltfrq[i] = ltfrq[i-1] + 1;
            else ltfrq[i] = 1;
        }

        rtfrq[n] = n;
        for(int i=n-1; i>=1; i--)
        {
            if(a[i]==a[i+1]) rtfrq[i] = rtfrq[i+1] + 1;
            else rtfrq[i] = 1;
        }

        build(1,1,n);

        REP(i,q)
        {
            scanf("%d%d",&l,&r);
         
            if(a[l]==a[r]) res = r-l+1;
            else
            {
                res = max(rtfrq[l],query(1,1,n,l+rtfrq[l],r));
            }
            printf("%d\n", res);
        }
    }
    return 0;
}

UVa 10608 - Friends

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

// maximum nodes in a connected subgraph

vector<int>adj[30007];
int vis[30007];
int cnt;

void dfs(int u)
{
    vis[u]=1;
    cnt++;
    REP(i,SZ(adj[u]))
    {
        if(vis[adj[u][i]]==0) dfs(adj[u][i]);
    }
}

int main()
{
    int T, n, m, u, v;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        FOR(i,1,m)
        {
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int mx=0;
        memset(vis, 0, sizeof vis);
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                cnt=0;
                dfs(i);
                mx=max(mx, cnt);
            }
        }
        pri(mx);

       FOR(i,1,n) adj[i].clear();
    }
    return 0;
}



// disjoint sets solution .. gotta take care of the pair counting -_-

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

int par[30000];

void init(int node)
{
    REP(i,node) par[i] = i;
}

int find(int r)
{
    return par[r]==r ? r : par[r] = find(par[r]);
}

void make_union(int a,int b)
{
    int u=find(a), v=find(b);

    if(u != v)
        par[u]=v;
}

int main()
{
    int T,node,edge,u,v;

    cin>>T;

    while(T--)
    {
        cin>>node>>edge;

        init(node);

        REP(i,edge)
        {
            cin>>u>>v;
            make_union(u,v);
        }

        REP(i,node) find(i);

        REP(i,node) prii(i,par[i]);

        int cnt,mx = -1;

        REP(i,node)
        {
            cnt = 1;   //*********
            FOR(j,i+1,node-1)
            {
                if(par[i] == par[j]) cnt++;      //*********
            }
            mx = max(mx,cnt);
        }

        pri(mx);
    }
    return 0;
}

UVa 459 - Graph Connectivity

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

map<char,char> par;

char findr(char ch)
{
    if(par[ch]=='\0') return ch;

    char x = findr(par[ch]);
    par[ch]= x;
    return x;
}

int main()
{
    ll tc;
    string s;
    char ch;
    bool fl = 0;
    int mx = 1;
    scl(tc);
    while(tc--)
    {
        par.clear();

        if(fl) printf("\n");
        fl=1;

        cin>>s;
        ch = s[0];

        getchar();

        while(getline(cin,s) and s!="")
        {
            char ch1 = s[0], ch2 = s[1];
            char u = findr(ch1), v = findr(ch2);
            if(u!=v) par[v] = u;
        }
        int cnt = 0;
        FOR(i,(int)'A',ch)
        {
            if(par[i]=='\0') cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

UVa 10226 Hardwood Species

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

int main()
{
    int T;
    string s;

    cin>>T;
    getchar();
    getchar();

    while(T--)
    {
        map <string, int> mp;
        set <string> st;

        int cnt = 0;

        while(getline(cin,s) and s[0])
        {
            mp[s]++;
            cnt++;
            st.insert(s);
        }

        set<string> :: iterator it;

        for(it=st.begin(); it!=st.end(); it++)
        {
            double xx = (double) (mp[*it]*100)/cnt;

            cout << *it << " " << fixed << setprecision(4) << xx << "\n";

        }
        if(T) puts("");

        mp.clear();
        st.clear();
    }
    return 0;
}

UVa 11340 Newspaper

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

int main()
{
    int T,n, hi,x;
    string s;
    char ch;
    cin>>T;
    while(T--)
    {
        map <char, int> mp;

        cin>>hi;

        while(hi--)
        {
            cin>>ch>>n;
            mp[ch] = n;
        }

        int cnt = 0;
        cin>>x;
        getchar();

        while(x--)
        {
            getline(cin,s);
            REP(i,SZ(s))
            {
                cnt += mp[ s[i] ];
            }
        }

        double xx = (double) (cnt*1.0/100);
        cout << fixed << setprecision(2) <<  xx << '$' << "\n";
    }
    return 0;
}

UVa 355 - The Bases Are Loaded

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;

bool isoka(string s, int bp)
{
    int tmp;

    REP(i,SZ(s))
    {
        tmp = isdigit(s[i]) ? s[i] - '0' : s[i] - 55;   //***

        if(tmp >= bp) return 0;     //*** Invalid Number of Any Base
    }
    return 1;
}

int main()
{
    int bp, bt;
    string s;

    while(cin>>bp>>bt>>s)
    {
        if(!isoka(s,bp))
        {
            printf("%s is an illegal base %d number\n", s.c_str(), bp);
        }
        else
        {
            LL dec = strtoll(s.c_str(), NULL, bp);      //*** String to Decimal Auto Convert

            string tst = "";

            while(dec)
            {
                tst += (dec%bt <= 9) ? dec%bt + '0' : dec%bt + 55;      //*** Mod and Divide -- Dec2AnyBaseConvert
                dec /= bt;
            }

            if(!SZ(tst)) tst += "0";       //***

            reverse(ALL(tst));

            printf("%s base %d = %s base %d\n", s.c_str(), bp, tst.c_str(), bt);
        }
    }
    return 0;
}

UVa 784 - Maze Exploration

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

string gr[33];
int r,c;

void DFS(int i, int j)
{
    if(i<0 or j<0 or i==r or j==c or (gr[i][j] != ' ' and gr[i][j] != '*')) return ;

    gr[i][j] = '#';

    DFS(i-1,j);
    DFS(i-1,j+1);
    DFS(i-1,j-1);
    DFS(i,j+1);
    DFS(i,j-1);
    DFS(i+1,j);
    DFS(i+1,j+1);
    DFS(i+1,j-1);
}

int main()
{
    int T;
    cin>>T;
    getchar();
    while(T--)
    {
        int idx = 0, mx = -1;
        while(getline(cin,gr[idx++]) and gr[idx-1][0] != '_')
        {
            mx = max(mx,SZ(gr[idx-1]));
        }

        r = idx;
        c = mx;

        REP(i,r)
        {
            REP(j,c)
            {
                if(gr[i][j] == '*')
                {
                    DFS(i,j);
                }
            }
        }

        REP(i,r) cout << gr[i] << "\n";
    }
    return 0;
}


/*
2
XXXXXXXXX
X X X
X * X
X X X
XXXXXXXXX
X X
X X
X X
XXXXX
_____
XXXXX
X   X
X * X
X   X
XXXXX
_____

*/

UVa 10336 - Rank The Languages

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

ll t,r,c;
string sa[100007];

struct DT
{
    int freq;
    char letter;
}arr[30];

int cnt[27],id;
char ch;

bool cmp(DT a, DT b)
{
    if(a.freq!=b.freq) return a.freq>b.freq;
    else return a.letter<b.letter;
}

void dfs(int i, int j)
{
    if(i<0 or j<0 or i==r or j==c or sa[i][j]=='@') return;

    if(ch==sa[i][j])
        sa[i][j]='@';
    else return;

    dfs(i,j+1);
    dfs(i,j-1);
    dfs(i-1,j);
    dfs(i+1,j);
}

int main()
{
    scl(t);
    FOR(cs,1,t)
    {
        memset(cnt,0,sizeof cnt);
        scll(r,c);
        REP(i,r) cin>>sa[i];

        REP(i,r)
        {
            REP(j,c)
            {
                if(sa[i][j]!='@')
                {
                    cnt[sa[i][j]-'a']++;
                    ch = sa[i][j];
                    dfs(i,j);
                }
            }
        }

        int id=0;
        REP(i,26)
        {
            if(cnt[i]) arr[id].letter= i+'a', arr[id].freq=cnt[i], id++;
        }
        sort(arr,arr+id,cmp);

        printf("World #%d\n", cs);
        REP(i,id)
        {
            printf("%c: %d\n", arr[i].letter, arr[i].freq);
        }
    }
    return 0;
}

UVa 10062 - Tell Me The Frequencies

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

struct DT
{
    int asci;
    int freq;
}data[500];

bool cmp(DT a, DT b)
{
    if(a.freq < b.freq) return true;
    else if(a.freq == b.freq and a.asci > b.asci) return true;

    return false;
}

int val[500];

int main()
{
    string s;
    int f = 0;

    while(getline(cin,s))
    {
        memset(val, 0 , sizeof val);

        REP(i,SZ(s))
        {
            val[ s[i] ]++;
        }

        int idx = 0;

        REP(i,500)
        {
            if(val[i])
            {
                data[idx].asci = i;
                data[idx].freq = val[i];
                idx++;
            }
        }

        sort(data,data+idx,cmp);

        if(f) puts("");
        f++;

        REP(i,idx)
        {
            cout << data[i].asci << " " << data[i].freq << "\n";
        }
    }
    return 0;
}

UVa 572 - Oil Deposits

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

char gr[105][105];
int r,c;

void DFS(int i, int j)
{
    if(i < 0 or j < 0 or i == r or j == c or gr[i][j] != '@') return;

    gr[i][j] = '*';

    DFS(i-1,j);
    DFS(i-1,j+1);
    DFS(i-1,j-1);
    DFS(i,j+1);
    DFS(i,j-1);
    DFS(i+1,j);
    DFS(i+1,j+1);
    DFS(i+1,j-1);

    return;
}

int main()
{
    while(cin>>r>>c and r+c)
    {
        REP(i,r) cin>>gr[i];

        int cnt = 0;

        REP(i,r)
        {
            REP(j,c)
            {
                if(gr[i][j] == '@')
                {
                    cnt++;
                    DFS(i,j);
                }
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

UVa 11244 - Counting Stars

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

char gr[105][105];
int r,c,cnt;

void DFS(int i, int j)
{
    if(i<0 or j<0 or i==r or j==c) return;
    if(gr[i][j] != '*') return;

    gr[i][j] = '#', cnt++;

    DFS(i-1,j);
    DFS(i-1,j+1);
    DFS(i-1,j-1);
    DFS(i+1,j);
    DFS(i+1,j+1);
    DFS(i+1,j-1);
    DFS(i,j+1);
    DFS(i,j-1);

    return ;
}

int main()
{
    while(cin>>r>>c and r+c)
    {
        REP(i,r) cin>>gr[i];

        int res = 0;

        REP(i,r)
        {
            REP(j,c)
            {
                cnt = 0;

                if(gr[i][j] == '*')
                {
                    DFS(i,j);
                }
                if(cnt==1) res++;
            }
        }
        pri(res);
    }

    return 0;
}

UVa 11878 - Homework Checker

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
using namespace std;

int main()
{
    char ch,chh;
    char r[7];
    int a,b,cnt=0;

    while(cin>>a>>ch>>b>>chh>>r)
    {
        if(r[0]=='?') continue;

        if(ch=='+')
        {
            if(a+b == atoi(r)) cnt++;
        }
        else
        {
            if(a-b == atoi(r)) cnt++;
        }
    }

    pri(cnt);

    return 0;
}

UVa 156 - Anagrams

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main()
{
    string s;
    map<string,int> freq;
    map<string,string> store;

    while(cin>>s and s!="#")
    {
        string tmp = s;

        transform(ALL(s), s.begin(), ::tolower);    ///***
        sort(ALL(s));
        freq[s]++;
        store[s] = tmp;

    }

    vector <string> vs;
    map<string,int> :: iterator it;

    for(it=freq.begin(); it!=freq.end(); it++)
    {
        if(it->second == 1)     ///***
        {
            vs.push_back( store[it->first] );   ///***
        }
    }

    sort(ALL(vs));

    REP(i,SZ(vs))
    {
        cout << vs[i] << "\n";
    }
    return 0;
}

UVa 10038 - Jolly Jumpers

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

int a[12345], ar[12345];

int main()
{
    int n;
    while(cin>>n)
    {
        memset(ar,0,sizeof ar);

        REP(i,n)
        {
            cin>>a[i];
            if(i) ar[abs(a[i] - a[i-1])]++;
        }

        int f = 0;
        FOR(i,1,n-1)
        {
            if(ar[i]==0)
            {
                f=1;
                pri("Not jolly");
                break;
            }
        }
        if(!f) pri("Jolly");
    }

    return 0;
}

Modified Sorting Using Compare Function

struct node
{
   int x, y, z;
} A[5];

ধরেন, আপনি A অ্যারেটা z ভ্যারিয়েবল অনুযায়ী বড় থেকে ছোট আকারে সাজাবেন। এক্ষেত্রে sort() কীভাবে ইউজ করা যায় দেখা যাক।

প্রথমেই sort() ফাংশনের প্যারামিটারগুলো দেখি।

sort(starting element pointer, ending ending pointer + 1, compare function name);

অর্থাৎ, যদি ফাংশন নেম comp হয় আর আপনি পুরা A অ্যারেটা সর্ট করতে চান comp ফাংশন অনুযায়ী, তাহলে লাইনটা হবে নিম্নরূপঃ

sort(A + 0, A + 4 + 1, comp);

বা

sort(A, A + 5, comp);

এখানে A + 0 অর্থাৎ A[0] হল অ্যারের প্রথম এলিমেন্ট।
A + 4 অর্থাৎ A[4] হল অ্যারের শেষ এলিমেন্ট।

তাহলে আপনি যদি অ্যারেটার ১ নং ইন্ডেক্স থেকে ৩নং ইন্ডেক্স সর্ট করতে চাইতেন শুধু, তাহলে লাইনটা কেমন হত?

sort(A + 1, A + 3 + 1, comp);

অর্থাৎ

sort(A + 1, A + 4, comp);

এবার আসি comp ফাংশনে। দেখা যাক এটি কীভাবে কাজ করে।

comp ফাংশনটা জাস্ট একটা ডিজাইন যেটার কাজ হল বলে দেওয়া sort() ফাংশনটা কীভাবে কাজ করবে।

comp-এ সব সময় দুটা প্যারামিটার রাখতে হয়, এবং এটা রিটার্ন করবে ট্রু অর ফলস, অর্থাৎ bool টাইপ।

comp-এর কাজ হল বলে দেওয়া, অ্যারের যে কোন দুটা এলিমেন্টের মধ্যে কোনটা আগে থাকবে এবং কোনটা পরে থাকবে, অর্থাৎ এক্ষেত্রে comp বলে দিবে যে A অ্যারের ১ আর ৩ নং এলিমেন্টের মধ্যে ১-এর z বড় হয়, তাহলে তারা ঠিকই আছে, তাদের সর্টের প্রয়োজন নাই। যদি এলিমেন্টটার z ছোট হয়, তাহলে সর্ট করতে হবে।

comp ফাংশনটা অনেকটা দাঁড়াচ্ছে তাহলেঃ

bool comp (node p, node q)
{ };

এখানে, p, q প্যারামিটার দুটা হল A অ্যারের দুটা এলিমেন্ট, এবং অবশ্যই p অ্যারেতে আগে অবস্থিত আর q পরে অবস্থিত।

p, q এর টাইপ node কারণ অ্যারেটার টাইপও নোড।

যেহেতু p হচ্ছে অ্যারেতে যে এলিমেন্ট আগে আছে আর q হচ্ছে যেটা পরে আছে, তার মানে, p.z > q.z হলে p আর q সর্টেডই আছে? আর যদি না হয়, তাহলে তাদের সর্ট করতে হবে।

comp ফাংশনটা বলে দেয় যে সর্টেড আছে কিনা। অর্থাৎ, সর্টেড থাকলে (মানে আপনি যেভাবে সর্টেড রাখতে চান, এক্ষেত্রে আমরা চাচ্ছি z অনুযায়ী descending) ফাংশনটা true return করবে, নতুবা ফলস।

আর একটা ইম্পর্ট্যান্ট কথা। আপনার ফাংশন যেন অবশ্যই বলে দেয় p.z = q.z হলে কী হবে!

p.z = q.z হলে আপনি x বা y অনু্যায়ীও চেক করতে পারেন। ধরেন, p.z = q.z হলে আমি চাই x অনু্যায়ী ascendingly sort হবে। তখন আমার ফাংশনে তা-ই লিখে দিতে হবে। কিন্তু p.x = q.x হলে? সেক্ষেত্রে আবার y অনুযায়ীও দেখতে পারেন। কিন্তু তাও সমান হলে?

সেক্ষেত্রে false রিটার্ন করা মাস্ট। এটা একটা ইম্পর্ট্যান্ট পার্ট। এটা না করলে আপনি কিন্তু এটার্নাল লুপে পরে যেতে পারেন।

এবার ফাংশনটা লিখে দেখা যাক।

bool cmp (node p, node q)
{
      if (p.z > q.z)
         return true;
      else if (p.z == q.z)
     {
         if (p.x < q.x)
         return true;
      else return false; //অর্থাৎ, p.x == q.x হলে false রিটার্ন্ট হচ্ছে
    }
    else return false;
};

এ ফাংশনটা বুঝাচ্ছে যে, আপনি এমনভাবে সর্ট করতে চান যেন সর্টেড অ্যারের যে এলিমেন্ট আগে থাকবে, তার z ভ্যারিয়েবলের মান পরের এলিমেন্টের z থেকে বড় হবে। যদি তাদের z সমান হয়, তবে যেটা আগে আছে তার x পরেরটার থেকে ছোট হবে।

এবার নিজের কোড করে প্র্যাক্টিস করে জিনিসটা হাতে আনতে হবে।

PS: অপারেটর ওভারলোড করেও করা যায়। কিন্তু ফাংশন লিখে করা আমার কাছে ইজিয়ার লাগে, অপারেটর ওভারলোডিং-এর দরকার কখনও হয়নি ফাংশন ইউজের জন্য~

 

Hope this helps~

by - Tahsin Masrur

UVa 454 - Anagrams

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

string anagrams(string s)   ///removing spaces from the string
{
    string tst (s);
    tst.erase(remove(ALL(tst),' '), tst.end());     ///**
    sort(ALL(tst));
    return tst;
}

int main()
{
    string s[1234];
    int T;

    cin>>T;

    getchar();
    getchar();

    while(T--)
    {
        int idx = 0;
       
        while(getline(cin,s[idx++]) and s[idx-1]!="")

        sort(s,s+idx);

        REP(i,idx)
        {
            FOR(j,i+1,idx-1)
            {
                if(anagrams(s[i]) == anagrams(s[j]))
                {
                    cout << s[i] << " = " << s[j] << endl;
                }
            }
        }
        if(T) cout << "\n";
    }
    return 0;
}

UVa 200 - Rare Order

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Case #%d:\n", ++cs);
using namespace std;

int main()
{
    string s[123456];
    int idx = 0, mxln = -1;

    while(cin>>s[idx++])
    {
        mxln = max(mxln, SZ(s[idx-1]));
        if(s[idx-1]=="#") break;
    }

    map<char,int> mp;
    char ch;

    int totalstring = idx - 1;

    REP(i,mxln)   /// nice koddur jaba? max string len porjonto
    {
        REP(j,totalstring)  /// pashe koddur jabe? total jotota string toto
        {
            if(i < SZ(s[j]))    // niche jotokkhon prjnto string lenth er moddhe thakbe totokkhn char prnt korbe
                ch = s[j][i];

            if(mp[ch]==0) printf("%c", ch), mp[ch]++;
        }
    }
    printf("\n");

    return 0;
}

UVa 353 - Pesky Palindromes

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Scenario #%d:\n", ++cs);
using namespace std;

bool ispal(string s)
{
    string n = s;
    reverse(ALL(s));
    if(n==s) return 1;
    else return 0;
}

int main()
{
    string s,tst;
    while(cin>>s)
    {
        map <string,int> mp;
        int cnt = 0;

        REP(i,SZ(s))
        {
            FOR(j,1,SZ(s)-i)
            {
                tst = s.substr(i,j);
                if(mp[tst]==0 and ispal(tst)) cnt++;
                mp[tst]++;
            }
        }
        printf("The string '");  cout << s;  printf("' contains %d palindromes.\n", cnt);
    }
    return 0;
}

UVa 401 - Palindromes

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Scenario #%d:\n", ++cs);
using namespace std;

int main()
{
    string s,tst;
    map<char,char> mp;

    mp['A'] = 'A';
    mp['E'] = '3';
    mp['H'] = 'H';
    mp['I'] = 'I';
    mp['J'] = 'L';
    mp['L'] = 'J';
    mp['M'] = 'M';
    mp['O'] = 'O';
    mp['S'] = '2';
    mp['T'] = 'T';
    mp['U'] = 'U';
    mp['V'] = 'V';
    mp['W'] = 'W';
    mp['X'] = 'X';
    mp['Y'] = 'Y';
    mp['Z'] = '5';
    mp['1'] = '1';
    mp['2'] = 'S';
    mp['3'] = 'E';
    mp['5'] = 'Z';
    mp['8'] = '8';

    while(cin>>s)
    {
        int p = 0, m = 0;
       
        tst = s;

        reverse(ALL(tst));

        if(tst == s) p = 1;

        tst = "";

        REP(i,SZ(s))
        {
            tst += mp[s[i]];
        }

        reverse(ALL(tst));

        if(s == tst) m = 1;

             if(p and m)   cout << s ,  printf(" -- is a mirrored palindrome.\n");
        else if(m and !p)  cout << s ,  printf(" -- is a mirrored string.\n");
        else if(!m and p)  cout << s ,  printf(" -- is a regular palindrome.\n");
        else if(!m and !p) cout << s ,  printf(" -- is not a palindrome.\n");

        cout << "\n";
    }
    return 0;
}

UVa 10450 - World Cup Noise

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Scenario #%d:\n", ++cs);
using namespace std;

LL ar[55];

void fib()
{
    ar[1] = 2, ar[2] = 3;

    FOR(i,3,55)
    {
        ar[i] = ar[i-1] + ar[i-2];
    }
}

int main()
{
    int cs = 0;
 
    fib();

    int n,x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        pcs;
        pri(ar[x]);
        puts("");
    }
    return 0;
}

UVa 10429 - List of Conquests

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Case %d: ", ++cs);
using namespace std;

int main()
{
    int n;
    string s,ss;
    map <string,int> mp;
    set <string> st;

    cin>>n;

    while(n--)
    {
        cin>>s;
        getline(cin,ss);
        mp[s]++;
        st.insert(s);
    }

    set <string> :: iterator it;

    for(it = st.begin(); it != st.end(); it++)
    {
        prii(*it, mp[*it]);
    }

    return 0;
}

UVa 637 - Booklet Printing

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Case %d: ", ++cs);
using namespace std;

/// Think a real world situation. you are told to print a book of sheets. as you need to use 1 press sheet
/// for 4 pages. so take required sheets ceil(n/4.0) . count totalpage in takne sheet.
/// loop from your last sheet to frst sheet.. if u're on sheet that's greater than our input sheet nmbr then leave it blank
/// *** Think Real World; Assume yourself a printsman."" The problem is solved"

int main()
{
    int n;

    while(cin>>n and n)
    {
        if(n==1)
        {
             printf("Printing order for %d pages:\n", n);
             printf("Sheet 1, front: Blank, 1\n");
             continue;
        }

        int ReqSheet = ceil(n/4.0);

        int TotalPageInSheet = ReqSheet * 4;

        printf("Printing order for %d pages:\n", n);

        int lst = TotalPageInSheet;
        int fst = 1;

        FOR(i,1,ReqSheet)
        {
            printf("Sheet %d, front: ", i);

            if(lst > n)
                printf("Blank, ");
            else
                printf("%d, ",lst);

            printf("%d\n", fst);

            lst--;
            fst++;

            printf("Sheet %d, back : ", i);

            printf("%d", fst);

            if(lst > n)
                printf(", Blank\n");
            else
                printf(", %d\n",lst);

            lst--;
            fst++;
        }
    }
    return 0;
}

UVa 490 - Rotating Sentences

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define WRITE(fn) freopen(fn, "w", stdout);
#define pcs printf("Case %d: ", ++cs);
using namespace std;

/// If you’ve already reached the end of one of the strings, print a space.

int main()
{
    string s[105];
    int i = 0, mxln=-1;

    while(getline(cin,s[i++]))
    {
        mxln = max(mxln, SZ(s[i-1]));
    }

    int totalstring = i-1;

    REP(i,mxln)
    {
        REV(j,totalstring)
        {
            if(SZ(s[j]) > i)    /// in the coln, if mx col len exceeds the len of that string then, print space
            {
                printf("%c", s[j][i]);
            }
            else
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}

UVa 11728 - Alternate Task

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define PI 2*acos(0.0)
#define pcs printf("Case %d: ", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

int sum(int n)
{
    int sm = 0;
    for(int j=1; j*j<=n; j++)
    {
        if(n%j==0)
        {
            sm += j;
            if(j!=n/j) sm+=n/j;
        }
    }
    return sm;
}

int cs = 0;

int main()
{
    int x;

    while(cin>>x and x)
    {
        int f = 0, ans;

        for(int i = x; i>=1; i--)
        {
            if(sum(i)==x)
            {
                f=1;
                ans = i;
                break;
            }
        }
        pcs;
        if(!f) pri(-1);
        else pri(ans);
    }

    return 0;
}

UVa 10195 - The Knights Around The Round Table

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define PI 2*acos(0.0)
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/// Radius of inscribed circle = Triangle Area / Half Perimeter
/// s = (a+b+c)/2+1e-8; -> add eps for case 0,0,0

int main()
{
    double a,b,c,s,area,r;

    while(cin>>a>>b>>c)
    {
        s = (a+b+c)/2+1e-8;  ///** add eps
        area = sqrt(s*(s-a)*(s-b)*(s-c));
        r = area/s;
        printf("The radius of the round table is: %.3lf\n", r);
    }
    return 0;
}

UVa 10684 - The Jackpot

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

///This is an maximum sub array sum problem.
///Here we need find maximum subarray sum in 1D array.

int main()
{
    int mx,n,x,sm;

    while(cin>>n and n)
    {
        mx = sm = 0;

        REP(i,n)
        {
            cin>>x;

            sm += x;

            mx = max(sm,mx);

            if(sm < 0) sm = 0;
        }

        if(mx) printf("The maximum winning streak is %d.\n", mx);
        else pri("Losing streak.");
    }

    return 0;
}

UVa 10940 - Throwing Cards Away II

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define hi printf("Hello World\n")
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

int ar[5000009];

int main()
{
    int n, idx = 1;

    ar[idx++] = 1;

    int fl = 2, cnt = 2, go = 1;

    while(go < 5000005)
    {
        ar[idx++] = cnt;

        if(cnt==fl) fl*=2, cnt = 0;

        cnt+=2;

        go++;
    }
     while(cin>>n and n)
            printf("%d\n", ar[n]);

    return 0;
}

UVa 10935 - Throwing Cards Away I

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hi printf("Hello World\n")
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;

int main()
{
    int n,x;

    while(cin>>n and n)
    {
        queue <int> q;

        FOR(i,1,n) q.push(i);

        printf("Discarded cards:");

        while(SZ(q)>1)
        {
            printf(" %d", q.front());
            q.pop();

            x = q.front();
            q.push(x);

            q.pop();

            if(SZ(q) > 1) printf(",");
        }

        printf("\nRemaining card: %d\n", q.front());
    }
    return 0;
}

UVa 119 - Greedy Gift Givers

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hi printf("Hello World\n")
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;


int main()
{
    int n,m,tk;
    string s;
    int cnt = 0;

    while(cin>>n)
    {
        vector <string> vs;
        map <string, int > mp;

        REP(i,n)
        {
            cin>>s;
            vs.push_back(s);
            mp[s]=0;
        }

        REP(i,n)
        {
            cin >> s >> tk >> m ;

            if(m==0) continue;

            mp[s] -= m * (tk/m);    //** mp[s] += (tk - tk%m); ??? why gives wa!!

            REP(i,m)
            {
                cin>>s;
                mp[s] += tk/m;
            }
        }

        if(cnt) puts("");
        cnt++;

        REP(i,SZ(vs))
        {
            prii(vs[i], mp[ vs[i] ]);
        }
    }

    return 0;
}

UVa 484 - The Department of Redundancy

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hi printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;

int main()
{
    int a[MX];
    map<int,int> mp;
    int n, idx = 0;
   
    while(cin>>n)
    {
        if(mp[n]==0)
            a[idx++]=n;
        mp[n]++;
    }

    REP(i,idx)
    {
        prii(a[i],mp[ a[i] ]);
    }

    return 0;
}

UVa 573 - The Snail

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hi printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;

int main()
{
    double well,init,climb,slide,fatig;

    while(cin>>well>>climb>>slide>>fatig and well)
    {
        double ht = 0, cnt = 0;

        double ff = climb * (fatig/100);

        while(1)
        {
            cnt++;

            if(climb>=0)
                ht += climb;

            if(ht>well) break;

            ht -= slide;

            climb -= ff;

            if(ht<0) break;
        }

        if(ht>well) printf("success on day %.0lf\n", cnt);
        else printf("failure on day %.0lf\n", cnt);
    }
    return 0;
}

UVa 371 - Ackermann Function

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hii printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;

int main()
{
    LL lo,hi;
    LL val,tot,mx,ind;

    while(cin>>lo>>hi and lo+hi)
    {
        if(hi < lo) swap(hi,lo);

        mx  = -1;
        LL vv, cnt = 0;

        FOR(i,lo,hi)
        {
            vv = i;
            cnt = 0;

            if(vv == 1)
            {
                cnt = 3;
                if(cnt>mx) mx = cnt, ind = i;
                continue;
            }

            while(vv!=1)
            {
                if(vv%2)
                {
                    vv = 3*vv + 1;
                }
                else
                {
                    vv /= 2;
                }
                cnt++;
            }
            if(cnt>mx) mx = cnt, ind = i;
        }
        printf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n", lo, hi, ind, mx);
    }
    return 0;
}

UVa 11650 - Mirror Clock

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

int main()
{
    int T,h,m,ans;

    cin>>T;

    while(T--)
    {
        scanf("%d:%d", &h, &m);

        int tt = h*60 + m;

        ans = 1440 - tt;
        ans %= 720; /// its a 12 hr clock so, mod by 720

        int hh = ans/60, mm = ans%60;
        if(hh == 0) hh+=12;   /// bcoz of 12 hr clock , we dont' have any 0 hour.. we've 12 hr so..

        printf("%02d:%02d\n", hh, mm);
    }
    return 0;
}

UVa 11677 - Alarm Clock

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hi printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;

int main()
{
    int h,m,hh,mm;

    while(cin>>h>>m>>hh>>mm and h+hh+m+mm)
    {
        int t = h*60 + m;
        int tt = hh*60 + mm;

        int ans = tt - t;

        if(ans <= 0) ans += 1440;

        ans %= 1440;

        pri(ans);
    }

    return 0;
}

UVa 11321 - Sort! Sort!! Sort!!!

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hi printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e5+10;

///** in cmp function take care of whats true according to the problem statement, what you wanna sort in ascending order and by default all others are false..

struct data{
    int nmbr;
    int mod;
};

bool cmp(data a, data b)
{
    if(a.mod < b.mod) return true;

    if(a.mod == b.mod)
    {
        if(a.nmbr%2 && b.nmbr%2 && (a.nmbr > b.nmbr)) return true;
        else if(a.nmbr%2==0 && b.nmbr%2==0 && (a.nmbr < b.nmbr)) return true;
        else if(a.nmbr%2 && b.nmbr%2==0) return true;
    }

    return false;
}

int main()
{
    data ar[MX];

    int n,m,x;

    while(cin>>n>>m)
    {
        cout << n << " " << m << "\n";

        if(n+m==0) break;

        REP(i,n)
        {
            cin>>x;
            ar[i].mod = x%m;
            ar[i].nmbr = x;
        }

        sort(ar,ar+n,cmp);

        REP(i,n)
        {
            cout << ar[i].nmbr << "\n";
        }
    }

    return 0;
}

UVa 1185 - Big Numbers

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
#define priii(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define hlw printf("Hello World\n");
#define pcs printf("CASE# %d:\n", ++cs);
#define WRITE(fn) freopen(fn, "w", stdout);
using namespace std;

/****/ int cs = 0;
const int INF = 1<<29;
const int MX  = 1e7+10;

/*
Algorithm:
We know that log(a*b) = log a + log b, so log n! = log 1 + log 2 + ... + log n.
Further more, we can get how many digits a number has by taking logarithm operation with a base of 10.
Also, there's a recursive function that N! = (N-1)! * N.
*/

double ans[MX];

void precal()
{
    ans[1] = log(1);
    FOR(i,2,MX)
    {
        ans[i] = ans[i-1] + log10(i);
    }
    return;
}

int main()
{
    precal();

    int T,x;
    cin>>T;
    while(T--)
    {
        cin>>x;
        printf("%d\n", (int)ans[x] + 1);
    }

    return 0;
}

UVa 637 - Parentheses Balance

//aarifshuvo  ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

int main()
{
    string s;
    int t;
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        getline(cin,s);

        stack<char> st;
        int fl = 0;

        REP(i,SZ(s))
        {
            if(s[i]=='(' or s[i]=='[') st.push(s[i]);
            else if(s[i]==')' or s[i]==']')
            {
                if(SZ(st))
                {
                    if(st.top()=='(' and s[i]==')') st.pop();
                    else if(st.top()=='[' and s[i]==']') st.pop();
                    else fl=1;
                }
                else fl=1;
            }
            if(fl) break;
        }
        if(SZ(st)) fl=1;
        if(fl) puts("No");
        else puts("Yes");
    }

    return 0;
}