2015年4月5日 星期日

USACO 2013 November Contest, Gold Problem 1. Empty Stalls

/*
    不知道自己在幹嘛啊。。。
    
    明明不用知道每隻牛
    進到哪個位置
    
    一開始還跑去寫線段樹orz
*/
// http://www.usaco.org/index.php?page=viewproblem2&cpid=346
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

int need[4000000];

int N, K;

int main()
{
    freopen("empty.in", "r", stdin);
    freopen("empty.out", "w", stdout);

    scanf("%d %d", &N, &K);

    for(int Ki = 0; Ki < K; Ki++)
    {
        int X, Y, A, B;
        scanf("%d %d %d %d", &X, &Y, &A, &B);

        for(int Yi = 1; Yi <= Y; Yi++)
        {
            int P = ((ll)A*Yi+B )%N;
            need[P] += X;
        }
    }

    int now = 0;

    for(int i = 0; i < 2; i++)
        for(int Ni = 0; Ni < N; Ni++)
        {
            now += need[Ni];
            if( now ) now--, need[Ni] = 1;
        }

    for(int Ni = 0; Ni < N; Ni++)
        if( !need[Ni] )
        {
            printf("%d\n", Ni);
            break;
        }
}

沒有留言:

張貼留言