Tuesday 31 March 2015

UVA 1561 Cycle Game (ZOJ 2686, UVALive 2813, Regionals 2003 >> Asia - Seoul)

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

//#include<bits/stdc++.h>
#include<iostream>
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, x, pos, arr[22];
    string s;
    cin>>tc;
    while(tc--)
    {
        int rev=0;
        cin>>n;
        for(int i=0; i<n; i++)
            cin>>arr[i];
        /*if(n%2==0)
        {
            cout<<"YES\n";
            //break;
            goto finish;
        }*/
        for(int i=0; i<n; i++)
            if(!arr[i])
            {
                if(i%2==1)
                {
                    cout<<"YES\n";
                    goto finish;
                    //else cout<<"NO\n";

                }
                break;
                //cout<<"Case "<<kk++<<": "<< <<"\n";
            }

        //if(n%2) rev=1;
        for(int i=n-1; i>=0; i--)
        {
            if(!arr[i])
            {
                if(rev%2==1)
                {
                    cout<<"YES\n";
                    goto finish;
                    //else cout<<"NO\n";

                }
                break;
                //cout<<"Case "<<kk++<<": "<< <<"\n";

            }
            rev++;
        }

        cout<<"NO\n";
        finish:
            int a=1;
    }

    return 0;
}

UVA 1566 John (POJ 3480, HDU 1907, ZOJ 3113, UVALive 3830, Regionals 2007 >> Europe - Southeastern)

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

//#include<bits/stdc++.h>
#include<iostream>
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, x;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        int res=0, chk=0;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            if(x>1) chk=1;
            res^=x;
        }

        //cout<<"Case "<<kk++<<": "<< <<"\n";
        if((res && chk) || (!res && !chk)) cout<<"John\n";
        else cout<<"Brother\n";
    }

    return 0;
}

UVA 847 A Multiplication Game (HDU 1517, POJ 2505, ZOJ 1893)

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

//#include<bits/stdc++.h>
#include<iostream>
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

long long n;

int func(long long cur)
{
    if(cur>=n) return 0;

    int ret=0;
    ret= ret | !func(cur*2);
    ret= ret | !func(cur*9);
    return ret;
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1;
    string s;
    while(cin>>n)
    {
        if(func(1))
            cout<<"Stan wins.\n";
        else cout<<"Ollie wins.\n";

    }
return 0;
}

UVA 10368 Euclid's Game (ZOJ 1913, HDU 1525, POJ 2348)

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

//#include<bits/stdc++.h>
#include<iostream>
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 func(long long a, long long b)
{
    if(b==0) return 0;
    int ret=0;
    if(a/b > 1) ret = ret | !func(b+a%b, b);
    ret = ret | !func(b, a%b);
    //ret = ret ^ 1;
return ret;
}

int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);
    long long n, tc, kk=1, a, b;
    string s;
    while(cin>>a>>b)
    {
        if(a==0 && b==0) return 0;
        if(a<b) swap(a, b);
        int res = func(a, b);
        if(res) cout<<"Stan wins\n";
        else cout<<"Ollie wins\n";

    }
return 0;
}

UVA 1557 Calendar Game (HDU 1079, ZOJ 1024, POJ 1082, UVALive 2321, Regionals 2001 >> Asia - Taejon)

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

//#include<bits/stdc++.h>
#include<iostream>
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, y, m, d;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>y>>m>>d;
        if((m+d)%2==0) cout<<"YES\n";
        else if(m==9 && d==30) cout<<"YES\n";
        else if(m==11 && d==30) cout<<"YES\n";
        else cout<<"NO\n";

        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }

    return 0;
}

Monday 16 March 2015

UVA 10507 Waking up brain

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / 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 100010

int connectionCount[30], waken[30], year, adjMat[30][30];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, tc, kk=1;
    string s;
    cin>>n>>m;
    cin>>s;
    for(int i=0; i<3; i++)
    {
        connectionCount[s[0]-'A']=connectionCount[s[1]-'A']=connectionCount[s[2]-'A']=3;
        waken[s[0]-'A']=waken[s[1]-'A']=waken[s[2]-'A']=1;
    }
    int cnt=3;
    for(int i=0; i<m; i++)
    {
        cin>>s;
        adjMat[s[0]-'A'][s[1]-'A']=1;
        adjMat[s[1]-'A'][s[0]-'A']=1;
    }
    getline(cin, s);
    while(1)
    {
        if(cnt==n) break;
        if(year==30) break;
        CLR(connectionCount);
        vector<int>v;
        for(int i=0; i<26; i++)
            for(int j=0; j<26; j++)
            {
                if(adjMat[i][j])
                    if(waken[i] && !waken[j])
                    {
                        connectionCount[j]++;
                        if(connectionCount[j]==3)
                            v.push_back(j);
                    }
            }
        for(int i=0; i<v.size(); i++)
            waken[v[i]]=1;
        cnt+=v.size();
        year++;
    }

    if(year==30) cout<<"THIS BRAIN NEVER WAKES UP\n";
    else cout<<"WAKE UP IN, "<<year<<", YEARS\n";

    while(getline(cin, s))
    {
        CLR(waken);
        year=0;
        CLR(adjMat);
        CLR(connectionCount);
        cin>>n>>m;
        cin>>s;
        for(int i=0; i<3; i++)
        {
            connectionCount[s[0]-'A']=connectionCount[s[1]-'A']=connectionCount[s[2]-'A']=3;
            waken[s[0]-'A']=waken[s[1]-'A']=waken[s[2]-'A']=1;
        }
        int cnt=3;
        for(int i=0; i<m; i++)
        {
            cin>>s;
            adjMat[s[0]-'A'][s[1]-'A']=1;
            adjMat[s[1]-'A'][s[0]-'A']=1;
        }
        getline(cin, s);
        while(1)
        {
            if(cnt==n) break;
            if(year==30) break;
            CLR(connectionCount);
            vector<int>v;
            for(int i=0; i<26; i++)
                for(int j=0; j<26; j++)
                {
                    if(adjMat[i][j])
                        if(waken[i] && !waken[j])
                        {
                            connectionCount[j]++;
                            if(connectionCount[j]==3)
                                v.push_back(j);
                        }
                }
            for(int i=0; i<v.size(); i++)
                waken[v[i]]=1;
            cnt+=v.size();
            year++;
        }

        if(year==30) cout<<"THIS BRAIN NEVER WAKES UP\n";
        else cout<<"WAKE UP IN, "<<year<<", YEARS\n";
    }
    return 0;
}