Painting Wall Painting Wall
Simple
EN Japanese RU

ニコラは壁を塗るための簡単なロボットを作りました。 壁は1メートルごとにしるしが付いていて、ロボットは塗る操作のリストを記憶しています。 それぞれの操作は壁のどの部分を塗るかを開始する場所と終了する場所(端を含みます)で示しています。 例として、[1, 5]という操作は1番目から5番目を、1番目と5番目を含めて塗ることを意味しています。 操作はリストに書かれた順番で行われます。 異なる操作の範囲が重なっていた場合、それらは1回のみ数えます

ステファンは操作のリストを作りましたが、ロボットに実行させる前に、我々はそれをチェックしなければなりません。 塗るべき壁の長さ(塗る場所は連続していなくても構いません)とステファンが用意したリストが与えられるので、 ...

painting-wall painting-wall

2つの引数

必要な操作の回数。もし与えられたリストで与えられた長さを塗ることができない場合は-1を返して下さい。

checkio(5, [[1,5], [11,15], [2,14], [21,25]]) == 1 # 1回目の操作では5メートル塗られます。
checkio(6, [[1,5], [11,15], [2,14], [21,25]]) == 2 # 2回目の操作では5メートル塗られます。和は10になります。
checkio(11, [[1,5], [11,15], [2,14], [21,25]]) == 3 # 3回目の操作では合計で15メートル塗られることになります。
checkio(16, [[1,5], [11,15], [2,14], [21,25]]) == 4 # 重なった範囲は1回しか数えないことに注意して下さい。
checkio(21, [[1,5], [11,15], [2,14], [21,25]]) == -1 # このリストからは21メートルを塗ることはできません。

checkio(1000000011,[[1,1000000000],[11,1000000010]]) == -1 # 巨大なテストケースの1つです。
    

開始-終了リストを取り扱うには、二分探索が有効です。Pythonではbisectモジュールが使えます。

このスキルはコンピュータシミュレーションにしばしば使われます。

:
0 < len() ≤ 30 (注:問題フォームの仕様上、上限が少ないですが、想定解法では上限数百万まで対応できます)
all(0 < x < 2 * 10 ** 18 and 0 < y < 2 * 10 ** 18 for x, y in )
0 < required < 2 * 10 ** 18
※ 塗る範囲がとても長い入力が一部あります。塗った場所を全て記憶するのは効率的ではありません。

You should be an authorized user in order to see the full description and start solving this mission.