問題
台のプリンターがあり、 から までの番号がつけられています。
プリンター は 秒ごとに1枚印刷できます。
つまりスイッチを入れてから 秒後に1枚、 秒後にもう1枚・・・と印刷可能です。
全てのプリンターのスイッチを同時に入れたとき、 枚目が印刷されるのは何秒後でしょうか。
[制約]
🔹
🔹
🔹
🔹答えは 以下
解き方・ソースコード
この問題では、答えに対して二分探索を行うと効率的に解くことができます。
答えが1秒後から8秒後までのいずれかであると仮定してみます。
答えの候補の中央は4秒後ですので、答えが4秒以下かどうか?を考えます。
下記ソースの入力例を考えると、4秒後までに印刷される枚数は8枚であり 枚未満なので質問の答えはNoとなります。
この時点で、答えの候補が5秒後から8秒後までの範囲に絞られます。
この処理を探索範囲の左端(Left)と右端(Right)が同じになるまで繰り返します。
[Google Colaboratory]
1 | #--------- 入力例 ---------- |
[実行結果]
500秒後に印刷できる枚数は1041 250秒後に印刷できる枚数は520 125秒後に印刷できる枚数は259 63秒後に印刷できる枚数は130 32秒後に印刷できる枚数は66 16秒後に印刷できる枚数は33 8秒後に印刷できる枚数は16 4秒後に印刷できる枚数は8 6秒後に印刷できる枚数は12 5秒後に印刷できる枚数は9 解: 6
この処理を繰り返すと6秒後に印刷される枚数が12枚となり、6秒後が正解となります。