Tuesday 22 December 2015

Mobile Casanova (UVA 12085, UVALive 2189, Regionals 2006 >> Asia - Dhaka)

///     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 100000


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n;
    long long arr[100000+2];
    string s;
    char ch;
    while(cin>>n && n)
    {
        for(int i=0;i<n;i++)
            cin>>arr[i];
        cout<<"Case "<<kk++<<":\n";
        for(int i=0;i<n;i++)
        {
            int st=i;
            while(i+1<n && arr[i+1]==arr[i]+1)
                i++;
            int ed=i;
            if(st==ed) cout<<"0"<<arr[i]<<"\n";
            else
            {
                cout<<"0"<<arr[st]<<"-";
                string s1 = "0"+to_string(arr[st]);
                string s2 = "0"+to_string(arr[ed]);
                int pos=0;
                while(s1[pos]==s2[pos])
                    pos++;
                for(int j=pos;j<s2.size();j++)
                    cout<<s2[j];
                cout<<"\n";
            }
        }
        cout<<"\n";
    }
return 0;
}

Monday 21 December 2015

Voting (UVALive 4921, Regionals 2010 >> North America - Mid-Central USA)

///     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 100000


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n;
    string s;
    char ch;
    while(cin>>s && s!="#")
    {
        int y=0, n=0, a=0, sl=s.size();
        for(int i=0;i<sl;i++)
            if(s[i]=='Y') y++;
            else if(s[i]=='N') n++;
            else if(s[i]=='A') a++;
        if(a*2>=sl) cout<<"need quorum";
        else if(y>n) cout<<"yes";
        else if(n>y) cout<<"no";
        else cout<<"tie";
        cout<<"\n";
    }
return 0;
}

The Next Permutation (UVALive 4556, HDU 3283, POJ 3785, SCU 3485, Regionals 2009 >> North America - Greater NY)

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


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, m, x, y, a, b, c, digit[10];
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        cin>>s;
        int sl=s.size(), index=-1;

        for(int i=sl-1;i>=0;i--)
        {
            for(int j=sl-1;j>i;j--)
                if(s[j]>s[i])
                {
                    swap(s[i], s[j]);
                    index=i+1;
                    break;
                }
            if(index!=-1) break;
        }
        if(index==-1)    cout<<kk++ <<" BIGGEST\n";
        else
        {
            cout<<kk++<<" ";
            CLR(digit);
            for(int i=index;i<sl;i++)
                digit[s[i]-'0']++;
            for(int i=0;i<index;i++)
                cout<<s[i];
            for(int i=0;i<10;i++)
                while(digit[i]--)
                    cout<<i;
            cout<<"\n";
        }
    }
return 0;
}

Wednesday 16 December 2015

Sharing Chocolate (UVA 1099, UVALive 4794, World Finals >> 2010 - Harbin)

///     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 100000

bool dp[(1<<15) + 2][100+2];
bool vis[(1<<15) + 2][100+2];
int arr[15+2], n, sum[(1<<15)+2];

void maskSum()
{
    int limit = (1<<n);
    for(int mask=0; mask<limit; mask++)
    {
        int tot = 0;
        for(int i=0; i<n; i++)
            if((mask & (1<<i)))
                tot+=arr[i];
        sum[mask]=tot;
    }
return;
}

bool func(int mask, int row)
{
    int inverse = ((1<<n)-1)^mask;
    if(__builtin_popcount(inverse)==1) return true;

    bool &ret = dp[mask][row];
    if(vis[mask][row]) return ret;

    vis[mask][row]=true;
    ret = false;

    int col = sum[inverse]/row;

    for(int split = inverse & (inverse-1); split; split = (split-1) & inverse) //find all subsets of the mask
    {
        int split2 = inverse^split;
        if(split2>split) break;

        if(sum[split]%row==0 && sum[split2]%row==0)
            ret = ret | (func(mask | split, row) & func(mask | split2, row));
         if(sum[split]%col==0 && sum[split2]%col==0)
            ret = ret | (func(mask | split, sum[split2]/col) & func(mask | split2, sum[split]/col));
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc, kk=1, tot, row, col;
    string s;
    char ch;
    while(cin>>n && n)
    {
        cin>>row>>col;
        tot=0;
        for(int i=0; i<n; i++)
        {
            cin>>arr[i];
            tot+=arr[i];
        }
        if(tot!=row*col)
        {
            cout<<"Case "<<kk++<<": No\n";
            continue;
        }

        maskSum();
        CLR(vis);

        if(func(0, row))    cout<<"Case "<<kk++<<": Yes\n";
        else    cout<<"Case "<<kk++<<": No\n";
    }
    return 0;
}