実行時間制限: 2 sec / メモリ制限: 512 MB
配点 : 500 点
問題文
ゲームは K ラウンドからなり、ラウンド i では司会が次のように言います。
- A_i 人組を作って！
すると、まだ脱落していない子供たちは A_i 人からなるグループをできるだけ多く組みます。
一人につき一つのグループにしか入れません。
グループに入れなかった子供たちは脱落し、その他は次のラウンドに進みます。
ラウンドで誰も脱落しないこともありえます。
最後まで、つまりラウンド K のあとまで残ったのは 2 人で、彼らが勝者となりました。
あなたは A_1, A_2, …, A_K の値を聞き、N の値は知りませんが、推定してみたくなりました。
ゲームの開始前にいた子供たちの人数として考えられる最小の値と、最大の値を求めてください。もしくは、考えられる N の値は存在しないと判定してください。
制約
- 1 <= K <= 10^5
- 2 <= A_i <= 10^9
- 入力値はすべて整数である。
考えたこと
素直にAを逆から見て行って、Nの値の最小値と最大値を更新していけばいいのではと考えました。
もし考えられるNの最小値と最大値の中にA_iの倍数がなかったら実現値なしということで-1を返せばよく、それ以外なら最小値は[最小の倍数]、最大値は[最大の倍数 + A_i – 1]となります。
この更新を繰り返して行ってやれば答えが求まります。
このアルゴリズムはO(K)で済みます。無事ACでした。
振り返り
僕の方法は線形走査というらしく、別解として二分探索があるみたいです（確かに単調性がある！）。
