WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #173 Div2 B "Painting Eggs"

問題

Jおじさんは、来たるお祭りのために、
N個の卵をペイントしたいと思っている。
そこで、甥であるAとGにこの事を頼みたいと思ったのだが、
彼らは卵一個につきお金を払えと要求してくるのだ。

Jおじさんは妙な事に気付いた。
それぞれの卵で、Aの要求額と、Gの要求額を足すと、
ぴったり1000になる事だ。

Jおじさんは、N個の卵を全てこの子達にペイントさせ、
なおかつ、AとGへの払ったお金の総額の差が
500を超えないようにしたいと思った。

上記のようなことを実行できるのであれば、
それぞれの卵をAとGのどちらに頼むのかを出力せよ。
不可能であれば、-1を出力せよ。

制約

1 <= N <= 10^6
0 <= AとGの要求額 <= 1000
ある卵のAとGの要求額の和 == 1000

考えた事

Sampleで-1のパターンないのかよw
CodeforcesのSampleって不親切だよなぁ

分からんぞ・・・
10^6か・・・100万だろ?
貪欲にできるような方法があるってことか?

・・・
Ai + Gi == 1000 ってゆうのが匂うな
あれ?そもそも-1にならないんじゃないか?
Sampleにもないし

いままでの差額が+500いっぱいいっぱいとして、
ここで-1000しても-500になって大丈夫だし

つまり差額が-500~+500の間に常に収まるのか!
だからそのようにAとGに頼んでいけばいい

事後

100万回いちいちprintfすると時間がかかるから、
いったん配列に収めるほうがよかった。
(今回は時間が5秒あったからセーフだった・・・)

ソースコード
int main() {
    int n;
    cin >> n;
    int dif = 0; // Aから見た差
    for( int i = 0; i < n; i++ ){
        int a, g;
        cin >> a >> g;
        
        if( abs( dif + a ) <= 500 ){
            // Aに任せる
            dif += a;
            printf( "A" );
        }else{
            // Gに任せる
            dif -= g;
            printf( "G" );
        }
    }
    printf( "\n" );
}