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" ); }