Monthly Archives: February 2013

(UVa) 12462 – Rectangle

0
Posted on by 
/*
user: php
time: 0.112 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3905
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf

using namespace std;

#define MAXX 100003
#define XOR(a, b) ((a) | (b) )


int histogram, totalcolors;
int colors[MAXX], heights[MAXX];
ll area[MAXX];

void leftToRight()
{
    stack<int>sk;
    sk.push(0);
    for(int i=1; i<= histogram; i++)
    {

        while( heights[sk.top()] >= heights[i] )
        {
            colors[i] = XOR(colors[i], colors[sk.top()]);
            sk.pop();
        }
        area[i] = ((ll)(i - sk.top())) * (ll)(heights[i]);
        sk.push(i);
    }
}

void rightToLeft()
{
    stack<int>sk;
    sk.push(histogram+1);
    for(int i=histogram; i > 0; i--)
    {

        while( heights[sk.top()] >= heights[i] )
        {
            colors[i] = XOR(colors[i], colors[sk.top()]);
            sk.pop();
        }
        area[i] += ((ll)(sk.top() - i)) * (ll)(heights[i]);
        sk.push(i);
    }
}








int main()
{
    ll maxarea;
    int tocolor;
    while(true)
    {
        getint(histogram); getint(totalcolors);
        if(histogram == 0 && totalcolors == 0) break;

        heights[0] = 0;
        colors[0] = 0;

        for(int i=1; i <= histogram; i++)
        {
            getint(heights[i]);
        }

        for(int i=1; i <= histogram; i++)
        {
            getint(colors[i]);
            colors[i] = (1<<colors[i]);
        }

        heights[histogram + 1] = 0;
        colors[histogram + 1] = 0;


        leftToRight();
        rightToLeft();


        for(int i=1; i<=histogram; i++)
            area[i] -= heights[i];

        maxarea = 0;
        tocolor = (1<<totalcolors) - 1;



        for(int i=1; i<=histogram; i++)
        {
            if(colors[i] == tocolor )
                maxarea = max(maxarea, area[i]);
        }

        pf("%lld\n", maxarea);
    }


    return 0;
}

(CodeForces) C. k-Multiple Free Set

0
Posted on by 
/*
user: hasib
link: http://codeforces.com/contest/275/problem/C
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

#define MAXX 100002

using namespace std;

int number_of_elements;
ll nums[MAXX];
ll k;

int low, high, mid;

bool search(ll n)
{
    low = 0;
    high = number_of_elements - 1;
    while(low <= high)
    {
        mid = (low+high)/2;
        if(nums[mid] == n)
        {
            break;
        }
        else if(n < nums[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }

    if(low <= high)
        return true;
    else return false;
}


int main()
{

    getint(number_of_elements);
    cin>>k;

    loop(i, number_of_elements)
    {
        getint(nums[i]);
    }

    sort(nums, nums + number_of_elements);

    int taken = 0;
    ll a;
    map<int, bool>visited;

    loop(i, number_of_elements)
    {


        if( visited[nums[i]] == 0 )
        {
            a = nums[i];
            if(search(a*k))
            {
                if(search(a*k*k))
                {
                    visited[a*k] = 1; //nished
                    taken++;
                }
                else
                {
                    visited[a*k] = 1;
                    taken++;
                }
            }
            else
            {
                taken++;
            }

        }



    }

    cout<<taken<<endl;





    return 0;
}

(CodeForces) A. Lights Out

0
Posted on by 
/*
user: hasib
link: http://codeforces.com/problemset/problem/275/A
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;

int xmove[] = {0, 0, 0, -1, 1};
int ymove[] = {0,-1, 1, 0, 0};


int main()
{
    int press[3][3];
    bool result[3][3];
    loop(i, 3)
    {
        loop(j, 3)
        {
            cin>>press[i][j];
        }
    }

    int x, y;



    mem(result, 1);

    loop(i, 3)
    {
        loop(j,  3)
        {
            if(press[i][j] % 2 == 1)
            {
                loop(k, 5)
                {
                    x = i + xmove[k];
                    y = j + ymove[k];
                    if(-1 < x && x ❤ && -1 < y && y <3)
                    {
                        result[x][y] = !result[x][y];
                    }
                }
            }

        }
    }

    loop(i, 3)
    {
        loop(j, 3)
        {
            cout<<result[i][j];
        }
        cout<<endl;
    }

    return 0;
}

(USACO) Sum the Numbers

0
Posted on by 

/*
ID: hasib
PROG: test
LANG: C++
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read(filename) freopen(filename, "r", stdin)
#define write(filename) freopen(filename, "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf

using namespace std;


int main()
{
    read("test.in");
    write("test.out");
    int a, b;
    getint(a); getint(b);
    pf("%d\n", a+b);
    return 0;
}

(UVa) 10074 – Take the Land

0
Posted on by 
/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1015
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;
#define MAXX 101




bool graph[MAXX][MAXX];
int presum[MAXX+1][MAXX+1];

int columns, rows;


int MIS()
{
    loop(i, columns)
    {
        loop(j, rows)
        {
            if(graph[j][i] == 1)
            {
                presum[j][i] = j;
            }
            else
            {
                if(j == 0) presum[j][i] = -1;
                else presum[j][i] = presum[j-1][i];
            }
        }
    }

    int longest_sum = 0;
    int sum;

    loop(i, rows)
    {
        FOR(j,i, rows)
        {
            sum = 0;

            loop(k, columns)
            {
                if(presum[i][k] < i && presum[j][k] < i)
                {
                    sum = sum + (j - i + 1);
                    if(longest_sum < sum)
                    {
                        longest_sum = sum;
                    }
                }
                else
                {
                    sum = 0;
                }


            }
        }
    }
    return longest_sum;
}








int main()
{
    while(true)
    {
        getint(rows); getint(columns);
        if(rows == 0  && columns == 0) break;

        loop(i, rows)
        {
            loop(j, columns)
            {
                getint(graph[i][j]);
            }
        }

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

    }

    return 0;
}

(lightOj) 1027 – A Dangerous Maze

0
Posted on by 
/*
user:php
link: http://www.lightoj.com/volume_showproblem.php?problem=1027
time: 0.008 sec
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;

int num[101];



int main()
{
    int kases, kaseno = 0, items, negetive_items, total_sum;

    cin>>kases;

    while(kases--)
    {
        cin>>items;
        negetive_items = 0;
        total_sum = 0;

        loop(i, items)
        {
            cin>>num[i];
            if(num[i] < 0) negetive_items++;
            total_sum += abs(num[i]);
        }

        if(items == negetive_items)
        {
            printf("Case %d: inf\n", ++kaseno);
        }
        else
        {
            items -= negetive_items;
            for(int i=min(items, total_sum); i>0; i--)
            {
                if(items%i == 0 && total_sum % i == 0 )
                {
                    items /= i;
                    total_sum /= i;
                    break;
                }
            }

            printf("Case %d: %d/%d\n", ++kaseno, total_sum, items);
        }






    }

    return 0;
}

(LightOj) 1030 – Discovering Gold

0
Posted on by 
/*
user: php
time: 0.000 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1030
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

#define MAXX 101


using namespace std;

double result[MAXX];
int input[MAXX];
int number_of_integers;
bool visited[MAXX];

double rec(int pos)
{
    if(pos >= number_of_integers)
    {
        return 0;
    }

    if(pos + 1 == number_of_integers)
    {
        return input[pos];
    }

    if( visited[pos] ) return result[pos];

    visited[pos] = true;

    double &ret = result[pos];

    double by;
    if(number_of_integers - pos - 1 >= 6)
    {
        by = 6;
    }
    else
    {
        by = number_of_integers - pos - 1;
    }


    ret = input[pos];

    FOR(i, 1, 7)
    {
        ret = ret + rec(pos + i)/by;
    }

    return ret;
}





int main()
{
    int kases, kaseno = 0;

    getint(kases);
    while(kases--)
    {
        getint(number_of_integers);

        loop(i, MAXX) visited[i] = false;

        loop(i, number_of_integers)
        {
            getint(input[i]);
        }



        printf("Case %d: %.6lf\n", ++kaseno, rec(0));
    }

    return 0;
}

(UVa) 108 – Maximum Sum

0
Posted on by 
/*
user: php
time: 0.012 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=44
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int( a.size() )
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;
#define MAXX 102



int array[MAXX][MAXX];
ll prefixsum[MAXX][MAXX];
int N;

ll MIS()
{

    loop(i, N)
    {
        prefixsum[0][i] = 0;
        for(int j=1; j <= N; j++)
        {
            prefixsum[j][i] = prefixsum[j-1][i] + array[j-1][i];
        }
    }


    ll maxsum = 0;
    ll sum = 0;

    for(int i=0; i <= N; i++)
    {
        for(int j=i+1; j <= N; j++)
        {
            sum = 0;

            loop(k, N)
            {
                sum += prefixsum[j][k] - prefixsum[i][k];

                if(sum > maxsum)
                {
                    maxsum = sum;
                }
                else if(sum < 0)
                {
                    sum = 0;
                }

            }
        }
    }

    return maxsum;



}



int main()
{
    getint(N);
    loop(i, N)
    {
        loop(j, N)
        {
            getint(array[i][j]);
        }
    }

    ll result = MIS();

    printf("%lld\n", result);






    return 0;
}

(UVa) 10684 – The jackpot

0
Posted on by 
/*
user: php
time: 0.084 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1625
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;

#define MAXX 10001

int main()
{
    int N;
    int num;
    ll maxbet;
    ll sum;
    while(getint(N) && N != 0)
    {
        sum = 0;
        maxbet = 0;
        loop(i, N)
        {
            getint(num);
            sum += num;
            if(sum > maxbet)
            {
                maxbet = sum;
            }
            else if( sum < 0 )
            {
                sum = 0;
            }
        }

        if(maxbet > 0)
        {
            printf("The maximum winning streak is %lld.\n", maxbet);
        }
        else
        {
            printf("Losing streak.\n");
        }
    }


    return 0;
}

(UVa) 507 – Jill Rides Again

0
Posted on by 
/*
user: php
time: 0.132 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=448
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;

#define MAXX 20001

int ara[MAXX];

int paths;
int start, end;
int maxcycleride;


struct DATA{
    int start, end, cycleride;
    int maxsum;
};

DATA result;



void MIS()
{
    result.maxsum = -INF;
    result.cycleride = -INF;

    int sum = 0;
    int current_ride = 0;
    end = paths;

    for(int i=paths-1; i>-1; i--)
    {
        sum  += ara[i];
        if(ara[i] > 0 ) current_ride++;
        if( sum < 0 )
        {
            sum = 0;
            end = i;
            current_ride = 0;
        }
        else if( sum == result.maxsum)
        {
            if(current_ride >= result.cycleride )
            {
                start = i;
                result.start = start;
                result.cycleride = current_ride;
                result.end = end;
            }
        }
        else if(sum > result.maxsum)
        {
            start = i;
            result.maxsum = sum;
            result.cycleride = current_ride;
            result.end = end;
            result.start = start;
        }


    }
}




int main()
{


    int kases;
    int kaseno = 0;
    getint(kases);

    while(kases--)
    {
        getint(paths);
        paths--;

        loop(i, paths)
        {
            getint(ara[i]);
        }

        MIS();

        if(result.maxsum != -INF)
            printf("The nicest part of route %d is between stops %d and %d\n", ++kaseno, result.start+1, result.end+1);
        else
            printf("Route %d has no nice parts\n", ++kaseno);



    }


    return 0;
}