hotpepsiの練習帳

SRM 690

22:03

https://competitiveprogramming.info/topcoder/srm/round/16729/div/1

Div1 Easy (250) WolfCardGame

問題

• 1から100までの100毎のカードのうち、K枚(15以下)選ぶ
• K枚のカードのうち任意の枚数を捨て、値に正負どちらかの符号をつけて合計する
• どういう組み合わせでも総和がNにならないようなK枚を構築する

方針

• Nが奇数のときを考えると、全てのカードが偶数ならNになることはない
• 一般化すると、Nの約数でない倍数で構築すればいい
• コーナーケースはNが30か60か90のとき
• 2・3・5で割り切れるので、7の倍数で構築することになるが、最後の数が100を超えてしまうので、適当な数を使う(100でも良い)
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_690/WolfCardGame.cpp

結果

o-- -1 104.72-25 = 79.72pt 103rd/258 rating 1343 -> 1410 (+67)

randome_shuffleしているコードをchallengeしたけど失敗。

http://togetter.com/li/970758