Showing posts with label UVa. Show all posts
Showing posts with label UVa. Show all posts

Saturday, 9 September 2017

Identifying tea (UVa 13012, UVaLive 7211, Regionals 2015 >> Latin America) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
///     Raihan Ruhin (username : raihanruhin)
///     Online resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, n, x, cnt;
    //cin>>tc;
    while(cin>>n)
    {
        cnt=0;
        for(int i=0;i<5;i++)
        {
            cin>>x;
            if(x==n) cnt++;
        }
        cout<< cnt <<endl;
    }
    return 0;
}
at 362 comments:
Labels: , ,

Monday, 10 July 2017

Army Buddies (UVa 12356, UVaLive 5789, Regionals 2011 >> Latin America) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int l[MX], r[MX];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, q, lf, rg;

    while(cin>>n>>q)
    {
        if(!n && !q) return 0;
        for(int i=1;i<=n;i++)
            l[i]=i-1, r[i]=i+1;
        r[n]=0;
        while(q--)
        {
            cin>>lf>>rg;
            l[r[rg]] = l[lf];
            r[l[lf]] = r[rg];
            if(l[lf]) cout<<l[lf]<<" ";
            else cout<<"* ";
            if(r[rg]) cout<<r[rg]<<"\n";
            else cout<<"*\n";
        }
        cout<<"-\n";
    }
    return 0;
}
at 1 comment:
Labels: , ,

Sunday, 18 June 2017

Almost Shortest Path (UVa 12144, UVaLive 4210, Regionals 2008 >> Latin America - South America) 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 502

struct Z
{
    int v, cost;
    bool operator < (const Z &p) const
    {
        return p.cost<cost;
    }
};

Z z, z2;

int shortest[MX], forbidden[MX][MX];
vector<Z> adj[MX];
vector<int> parent[MX];
priority_queue<Z>pq;

int dijkstra(int src, int dst, int node)
{
    for(int i=0; i<node; i++)
        shortest[i]=1e9;

    z.v = src;
    z.cost = 0;
    pq.push(z);
    shortest[src]=0;

    while(!pq.empty())
    {
        z = pq.top();
        pq.pop();

        int l = adj[z.v].size();

        for(int i=0; i<l; i++)
        {
            z2 = adj[z.v][i];
            if(forbidden[z.v][z2.v]==1) continue;
            if(shortest[z2.v]>shortest[z.v]+z2.cost)
            {
                parent[z2.v].clear();
                parent[z2.v].push_back(z.v);
                z2.cost = shortest[z2.v]= shortest[z.v]+z2.cost;
                pq.push(z2);
            }
            else if(shortest[z2.v]==shortest[z.v]+z2.cost)
                parent[z2.v].push_back(z.v);

        }
    }
    return shortest[dst];
}

void removeEdge(int src, int dst)
{
    if(dst==src) return;
    for(int i=0;i<parent[dst].size();i++)
    {
        forbidden[ parent[dst][i] ][dst] = 1;
        removeEdge(src, parent[dst][i]);
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc,kk=1, node, edge, u, v, cost, src, dst;

    while(cin>>node>>edge && node)
    {
        cin>>src>>dst;


        for(int i=0; i<edge; i++)
        {
            cin>>u>>v>>cost;

            z.v = v;
            z.cost = cost;
            adj[u].push_back(z);
        }

        int tmp = 1e9;
        int mn = dijkstra(src, dst, node); //initial

        if(mn<1e9)
        {
            removeEdge(src, dst); //remove edges of shortest
            tmp = dijkstra(src, dst, node); //second time
        }
        if(tmp==1e9) tmp = -1;
        cout<<tmp<<endl;


        CLR(forbidden);
        for(int i=0;i<node;i++)
        {
            adj[i].clear();
            parent[i].clear();
        }
    }
    return 0;
}
at 2 comments:
Labels: , ,

Sunday, 4 June 2017

Football (UVa 12673, UVaLive 6530, Regionals 2013 >> Latin America) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

struct match{
    int score, receive;
    bool operator < (const match &m) const{
        return m.score-m.receive < score-receive ;
    }
};

match mth[MX];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, g;
    //cin>>tc;
    while(cin>>n>>g)
    {
        for(int i=0;i<n;i++)
            cin>>mth[i].score>>mth[i].receive;
        sort(mth, mth+n);

        int point = 0;

        for(int i=0;i<n;i++)
        {
            //cout<<mth[i].score<<" "<<mth[i].receive<<endl;
            if(mth[i].score>mth[i].receive)
                point += 3;
            else if(mth[i].score==mth[i].receive)
            {
                if(g>0)
                {
                    point += 3;
                    g--;
                }
                else point += 1;
            }
            else if(mth[i].score<mth[i].receive)
            {
                if(g>(mth[i].receive-mth[i].score))
                {
                    point += 3;
                    g= g-(mth[i].receive-mth[i].score)-1;
                }
                else if(g==(mth[i].receive-mth[i].score))
                {
                    point += 1;
                    g= g-(mth[i].receive-mth[i].score);
                }
                
            }
        }
        cout<<point<<endl;
    }
    return 0;
}
at No comments:
Labels: , ,

Saturday, 3 June 2017

Proving Equivalences (UVa 12167, UVaLive 4287, Regionals 2008 >> Europe - Northwestern) 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

vector<int>adj[20002];
stack<int>stk;

int t, lo[20002], tim[20002], vis[20002], sccrm[20002], scc, done;

void tarjan_scc(int u)
{
    t++;
    vis[u]=1;
    lo[u]=tim[u]=t;
    stk.push(u);

    for(int i=0;i<adj[u].size();i++)
    {
        int v = adj[u][i];
        if(!vis[v])
        {
            tarjan_scc(v);
            lo[u]=min(lo[u], lo[v]);
        }
        else if(vis[v]==1)
            lo[u]=min(lo[u], tim[v]);
    }

    if(lo[u]==tim[u])
    {
        scc++;
        do{
            done = stk.top();
            stk.pop();
            sccrm[done]=scc;
            vis[done]=2;
        }while(done!=u);
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, u, v;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n>>m;
        t=scc=0;
        while(!stk.empty()) stk.pop();
        for(int i=1;i<=n;i++)
        {
            adj[i].clear();
            vis[i]=0;
        }

        while(m--)
        {
            cin>>u>>v;
            adj[u].push_back(v);
        }
        for(int i=1;i<=n;i++)
            if(!vis[i])
                tarjan_scc(i);

        // checking zero indegree and outdegree of scc
        bool hasIndegree[scc+2], hasOutdegree[scc+2];
        CLR(hasIndegree);
        CLR(hasOutdegree);

        for(int i=1;i<=n;i++)
            for(int j=0;j<adj[i].size();j++)
                if(sccrm[i]!=sccrm[adj[i][j]]) //not in same scc
                {
                    hasIndegree[sccrm[i]]=true;
                    hasOutdegree[sccrm[adj[i][j]]]=true;
                }
        int zeroIndgree=0, zeroOutdegree=0;
        for(int i=1;i<=scc;i++)
        {
            if(!hasIndegree[i]) zeroIndgree++;
            if(!hasOutdegree[i]) zeroOutdegree++;
        }
        if(scc==1) cout<<0<<endl;
        else cout<<max(zeroIndgree, zeroOutdegree)<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }

    return 0;
}
at No comments:
Labels: , ,

Thursday, 1 June 2017

Interval Product (UVa 12532, UVaLive 6139, Regionals 2012 >> Latin America) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int z1, z2, node[MX*4];

void insert(int idx, int st, int ed, int s, int e, int val)
{
    if(st==s && ed==e)
    {
        if(val>0) node[idx]=1;
        else if(val<0) node[idx]=-1;
        else node[idx]=0;
        return;
    }
    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1;
    if(e<=mid) insert(lft, st, mid, s, e, val);
    else if(s>mid) insert(rgt, mid+1, ed, s, e, val);
    else
    {
        insert(lft, st, mid, s, mid, val);
        insert(rgt, mid+1, ed, mid+1, e, val);
    }
    node[idx] = node[lft] * node[rgt];
    return;
}

int query(int idx, int st, int ed, int s, int e)
{
    if(st==s && ed==e)
    {
        return node[idx];
    }
    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1;
    if(e<=mid) return query(lft, st, mid, s, e);
    else if(s>mid) return query(rgt, mid+1, ed, s, e);
    else return query(lft, st, mid, s, mid)*query(rgt, mid+1, ed, mid+1, e);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc,kk=1, n, q, x, y;
    char c;
    string s;
    while(cin>>n>>q)
    {
        for(int i=1;i<=n*4;i++)
            node[i]=1;

        for(int i=1; i<=n; i++)
        {
            cin>>x;
            insert(1, 1, n, i, i, x);
        }
        while(q--)
        {
            cin>>c>>x>>y;
            if(c=='C')
                insert(1, 1, n, x, x, y);
            else
            {
                z1 = query(1, 1, n, x, y);
                //cout<<z1.pos<<" "<<z1.neg<<" "<<z1.zero<<endl;
                if(z1==0)
                    cout<<"0";
                else if(z1<0)
                    cout<<"-";
                else cout<<"+";
            }
        }
        cout<<endl;
    }
    return 0;
}
at No comments:
Labels: , ,

Saturday, 9 July 2016

DNA Sorting (UVA 612, HDU 1379, POJ 1007, ZOJ 1188, UVALive 5414, Regionals 1998 >> North America - East Central NA) 

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, cnt;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n>>m;
        vector< pair<int, pair<int, string> > > v;
        for(int i=0;i<m;i++)
        {
            cin>>s;
            cnt=0;
            for(int j=0;j<n-1;j++)
                for(int k=j+1;k<n;k++)
                    if(s[j]>s[k])
                        cnt++;
            v.push_back(make_pair(cnt, make_pair(i,s)));
        }
        sort(v.begin(), v.end());
        if(kk>1) cout<<"\n";
        for(int i=0;i<m;i++)
            cout<<v[i].second.second<<"\n";
        kk++;
    }

    return 0;
}

at No comments:
Labels: , , , , ,

Friday, 8 July 2016

Prime Ring Problem (UVA 524, HDU 1016, UVALive 5270, ZOJ 1457, SCU 1545, Regionals 1996 >> Asia - Shanghai) 

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int ring[20], n;
bool isPrime[33], taken[20];

void print()
{
    cout<<ring[1];
    for(int i=2;i<=n;i++)
        cout<<" "<<ring[i];
    cout<<"\n";
return;
}

void backTrack(int tot, int lst) //(total taken already, last taken number)
{
    if(tot==n)
    {
        if(isPrime[lst+1])
            print();
        return;
    }

    for(int i=2;i<=n;i++)
        if(!taken[i])
            if(isPrime[lst+i])
            {
                taken[i]=1;
                ring[tot+1]=i;
                backTrack(tot+1, i);
                taken[i]=0;
            }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, m;
    string s;
    isPrime[2]=isPrime[3]=isPrime[5]=isPrime[7]=isPrime[11]=isPrime[13]=isPrime[17]=isPrime[19]=isPrime[23]=isPrime[29]=isPrime[31]=1;
    while(cin>>n)
    {
        CLR(taken);
        CLR(ring);
        ring[1]=taken[1]=1;//first circle fixed
        if(kk>1) cout<<"\n";
        cout<<"Case "<<kk++<<":\n";
        backTrack(1, 1); //first circle taken
    }
return 0;
}

at No comments:
Labels: , , , , ,

Saturday, 28 May 2016

Tariff Plan (UVA 12157, UVALive 4405, Regionals 2008 >> Asia - Kuala Lumpur) 

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, duration;
    string s;
    cin>>tc;
    while(tc--)
    {
        int mile=0, juice=0;
        cin>>n;
        while(n--)
        {
            cin>>duration;
            mile+=(duration/30+1)*10;
            juice+=(duration/60+1)*15;
        }
        if(mile<juice) cout<<"Case "<<kk++<<": Mile "<< mile <<"\n";
        else if(juice<mile) cout<<"Case "<<kk++<<": Juice "<< juice <<"\n";
        else cout<<"Case "<<kk++<<": Mile Juice "<< mile <<"\n";
    }

    return 0;
}
at No comments:
Labels: , ,

Friday, 27 May 2016

Prime Path (UVA 12101, SPOJ PPATH, POJ 3126, HDU 1973, UVALive 3639, Regionals 2006 >> Europe - Northwestern) 

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 10000

vector<int>prime;
bool status[MX+2];
int pl;

void PrimeGenerate(int n)
{
    int sq=sqrt(n);
    for(int i=3; i<=sq; i+=2)
    {
        if(!status[i])
            for(int j=i*i; j<=n; j+=(i<<1))
                status[j]=true;
    }

    status[0]=status[1]=true;
    for(int i=4;i<=n;i+=2) status[i]=true;

    prime.push_back(2);
    for(int i=3; i<=n; i+=2)
        if(!status[i])
            prime.push_back(i);
return;
}

int dp[MX], st, ed, taken[MX], dist[10010];
vector<int>v[10010];

int bfs(int num)
{
    if(num==ed) return 1;
    dist[num]=1;
    queue<int>Q;
    Q.push(num);
    while(!Q.empty())
    {
        int qq=Q.front();
        Q.pop();
        for(int i=0;i<v[qq].size();i++)
            if(!dist[v[qq][i]])
            {
                dist[v[qq][i]]=dist[qq]+1;
                if(v[qq][i]==ed) return dist[v[qq][i]];
                Q.push(v[qq][i]);
            }
    }
return 100000;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n;
    PrimeGenerate(MX);
    int loopst;

    pl=prime.size();
    for(int i=0;i<pl;i++)
        if(prime[i]>999)
        {
            loopst=i;
            break;
        }

    for(int i=loopst;i<pl;i++)
    {

        for(int j=loopst;j<pl;j++)
        {
            int tmp=prime[i];
            int tmp2=prime[j], cnt=0;

            while(tmp && tmp2)
            {
                if(tmp%10 != tmp2%10) cnt++;
                tmp/=10;
                tmp2/=10;
            }

            if(cnt==1)
            {
                v[prime[i]].push_back(prime[j]);
            }
        }
    }

    cin>>tc;
    while(tc--)
    {
        cin>>st>>ed;
        if(ed>st) swap(st, ed);
        CLR(dist);
        int ans=bfs(st);
        if(ans<100000) cout<<ans-1<<"\n";
        else cout<<"Impossible\n";
    }

return 0;
}
at No comments:
Labels: , , , , ,
Subscribe to: Posts (Atom)