あなたは高校生向けの国際的なコンテストであと一歩のところで金メダルを逃し、帰国後に自分が受験生であることを発見するに至った。しかしあなたは、受験に必要な N 種類の勉強を全くこなしていない。
集中力に定評のあるあなたは、それぞれの勉強を連続した期間に行うことで、残り W 日の受験勉強を乗り切ることにした。
あなたはこの期間中に N 個の模擬試験を受験することにしている。
各模擬試験は開催日と影響力 d が決まっており、開催日前後 d 日未満の模試をあなたは意識している。そして、その日意識している模試の数があなたのやる気の数値となる。
i 種類目の勉強は i 以上のやる気がある時でないとできない。一日にできる勉強の個数には限りはないので、全ての種類の勉強について、連続して勉強できる最大の日数を調べたい。
W 日間中に N 個の模試が行われる。模試には 0 から N-1 までの異なる整数の番号がつけられている。
それぞれの模試 i には開催日 X[i] と 影響度 D[i] が決まっている。日付 t に対して X[i]-D[i] ＜ t ＜ X[i]+D[i] が成り立つ場合に限り、あなたは日付 t のときに模試 i を意識している。
それぞれの日において、あなたの勉強のやる気はその日にあなたが意識している模試の数である。
あなたがやるべき勉強は N 種類ある。勉強には 1 から N までの異なる整数の番号がつけられている。勉強 k を行えるのはあなたのやる気が k 以上の日だけである。
次のパラメータを持つプロシージャ schedule(W, N, X, D) を実装せよ:
それぞれの勉強 k について、あなたが勉強 k を連続して行うことのできる最も長い期間を計算し answer(k, L, R) を呼び出せ。L, R はそれぞれ勉強 k を連続して行うことのできる最長の期間の最初の日と最後の日である。勉強 k を行える日が 1 日もない場合は answer(k, 0, 0) と呼び出さねばならない。最長の期間が複数ある場合は L が最も小さいものを選ばねばならない。 answer(k, L, R) はどのような k の順番で呼び出しても構わないが、すべての勉強についてちょうど 1 回ずつ呼び出される必要がある。
なお、あなたは 1 日に何種類でも勉強をすることができるのでそれぞれの勉強について独立に考えてよい。すなわち異なる k の値について、answer(k, L, R) 呼び出しの L, R が表す期間は共通部分を持っていてもよい。
W = 10, N = 3,
| X =? | 4 |
| 8 | |
| 3 |
| D =? | 2 |
| 4 | |
| 1 |
の場合を考える。schedule は次のようなパラメータで answer を呼び出す必要がある。(この順番に呼び出す必要はない。)
| パラメータ |
| answer(1, 3, 9) |
| answer(2, 3, 3) |
| answer(3, 0, 0) |