2015年2月3日 星期二

2015/02/03 2014-2015 ACM-ICPC, Central Europe Regional Contest (CERC 14), problem: (I) Bricks

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

int T, N;
vector<int> v;

int gcd(int a, int b)
{
    while( a && b )
    {
        if( a < b ) swap(a, b);
        a %= b;
    }

    return a+b;
}

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d", &N);

        int B = 0, W = 0, L = 0;
        v.clear();

        for(int Ni = 0; Ni < N; Ni++)
        {
            int k; char c;
            scanf("%d %c", &k, &c);

            if( c == 'B' ) B += k, v.push_back(k);
            else W += k, v.push_back(-k);

            L += k;
        }

        if( B == 0 || W == 0 )
        {
            printf("%d\n", L);
            continue;
        }

        int GCD = gcd(B, W);
        B /= GCD;
        W /= GCD;

        int Ans = 0;
        ll now = 0;

        for(int Ni = 0; Ni < N; Ni++)
        {
            ll t = ( v[Ni ] > 0 ? W : B ) ;
            ll x = (ll)v[Ni] * t;

            if( now >= 0 && x >= 0 || now <= 0 && x <= 0 );
            else
            {
                if( x < 0 )
                {
                    if( -x-now >= 0 && (-x-now)%t == 0 )
                        Ans++;
                }
                else
                {
                    if( x+now >= 0 && (x+now)%t == 0 )
                        Ans++;
                }
            }

            now += x;
        }

        printf("%d\n", Ans);
    }
}

沒有留言:

張貼留言