TopCoder SRM 504.5 Div1
勝ち負けがどうであれ、復習をしっかりすることを目標にしたい。
Easy TheNumbersWithLuckyLastDigit
問題
luckyな数とは下一桁が4または7の数のことを言う。
数nが与えられたとき、nが最小でいくつのluckyな数の和として表せるかを答えよ。
n≦10^9
試行錯誤
ある程度大きな数に対しては下一桁だけで使う数の個数が決まる。
（最後の数で10以上の部分を全部まとめれて足せばいいから）
なので下一桁の各数字ごとで、作れる最小の数を考えればよい。
1 は 4+7 の 11が作れる最小の下一桁1の数
2 は 4+4+4 の 12が（以下略）
……
で、下一桁を見て、その数が作れる最小の数以上ならば作れる。
そうでなければ作れない。
テーブル埋め込みして10回くらい確認してSubmit.
Medium TheJackpotDivOne
問題
n人がそれぞれmoney[i]を持っている。
jackpotの金額を次のようにn人に配分する。
jackpotがなくなるまで以下の操作を繰り返す。
金額がもっとも少ない人を選ぶ。この人の所持金をPとする。
moenyの平均-Pより真に大きい最小の整数をXとする。
Xがjackpot以下ならXをこの人に配分する。
Xがjackpotより大きければこの人にjackpotの残りを全て配分する。
このとき、各人の所持金を求め、昇順で出力せよ。
n≦47,
money[i],jakcpot≦10^18
試行錯誤
jackpotがでかすぎてシミュレーションは無理だ。。。
実はこれあんまり大きいとほぼ等分になるのでは……
もっとも貧しい人が次に受け取るまでに金がどうなるか実はきれいに定まったりする？
しないっぽい。
最大値って全員の所持金が横並びにならないと変わらない。
逆に横並びになったら最終の配分結果はすぐにわかる。
しかし横並びになるまでシミュレーションしてもTLEすんじゃないかなあ……
2番目が変わるときっていつだろう。これも簡単には定まらない気がする。
全然わからない。
終了直前に嘘解法（全員の所持金が横並びになるかを最初に判定、そうでないならシミュレーション）をSubmit.
Hard
Unopened.
明日以降に復習。
Challenge Phase
250でn%100みたいなことをしている人を二人落とす。
自分の500は即座に落とされた。
てかみんなシミュレーションしてるぞ？
なんでこれで落とされてる人とそうでない人いるんだろう。
System Test
250通った。
500はlong longのオーバーフローだった（！）
intだけでなくlong longもオーバーフローするんだなあ。。。orz
doubleやlong doubleでも精度が足りないようで、Failed祭りになっていた。
PracticeでMediumだけ通した。
Hardはまた後日。
