| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 110 | 44 | 39 | 63.934% |
ビ太郎はビリヤードで遊んでいる. JOI 国のビリヤードは台上に並べられた N 個のボール 1,2,...,N を用いる遊びであり,台にはボールを落とすための穴が設けられている. 一度穴に落ちたボールは台上には戻さず,そのボールを再び落とすことはできない.ビ太郎の目的は,なるべく大きい番号の書かれたボールを穴に落とすことである.
ボールを落とすのは集中を必要とする作業である. はじめ,ビ太郎の 集中力 は X であり,ボール i (1 ≦ i ≦ N) を落とすと集中力が Ai 減少する.集中力が Ai 未満であるとき,ボール i を落とすことはできない.
また,このビリヤードではボールを落とす順番に関するルールが存在する.具体的には, Pi = -1 (1 ≦ i ≦ N) のとき,ボール i はいつでも落とすことができ, Pi ≠ -1 のとき,ボール i を落とすためには,ボール Pi がすでに落とされている必要がある.
ビ太郎が持つ集中力と各ボールの情報が与えられたとき,ビ太郎がボールを穴に落とすことができるか判定し,ボールを落とすことができる場合は落とせるボールの番号の最大値を求めるプログラムを作成せよ.
入力は以下の形式で与えられる.
N X A1 A2 … AN P1 P2 … PN
ビ太郎が穴に落とすことのできるボールの番号の最大値を 1 行に出力せよ.
ただし,ビ太郎が 1 個もボールを落とすことができない場合は代わりに -1 と出力せよ.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | N ≦ 1000, Pi = -1 (1 ≦ i ≦ N). |
| 2 | 9 | N ≦ 1000, P1 = -1, Pi = i-1 (2 ≦ i ≦ N). |
| 3 | 16 | N ≦ 1000, Pi < i (1 ≦ i ≦ N). |
| 4 | 20 | Pi < i (1 ≦ i ≦ N). |
| 5 | 19 | N ≦ 1000. |
| 6 | 30 | 追加の制約はない. |
6 7 1 2 4 3 10 100 -1 -1 -1 -1 -1 -1
4
はじめ,ビ太郎の集中力は 7 である.
すべての i (1 ≦ i ≦ N) について Pi = -1 なので,ビ太郎は集中力が足りる限り,すべでのボールをいつでも穴に落とすことができる.
例えば,以下のようにすると,ビ太郎はボール 4 を落とすことができる.
また,ビ太郎がボール 5,6 を穴に落とすことはできない.よって,ビ太郎が穴に落とすことのできるボールの番号の最大値は 4 である.
この入力例は小課題 1,3,4,5,6 の制約を満たす.
5 12 1 2 3 5 8 -1 1 2 3 4
4
はじめ,ビ太郎の集中力は 12 である.
例えば,以下のようにすると,ビ太郎はボール 4 を落とすことができる.
また,ビ太郎がボール 5 を穴に落とすことはできない.よって,ビ太郎が穴に落とすことのできるボールの番号の最大値は 4 である.
この入力例は小課題 2,3,4,5,6 の制約を満たす.
8 10 3 1 4 1 5 9 2 6 -1 1 2 -1 4 4 5 7
7
この入力例は小課題 3,4,5,6 の制約を満たす.
2 1000000000000000 1 1 2 1
-1
P1 = 2 なので,ボール 1 を落とすためには,ボール 2 がすでに落とされている必要がある.逆に, P2 = 1 なので,ボール 2 を落とすためには,ボール 1 がすでに落とされている必要がある.このことから,ビ太郎は 1 個もボールを落とすことができない.よって, -1 を出力する.
この入力例は小課題 5,6 の制約を満たす.
9 2468024680 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 6 5 4 -1 3 2 1 9 8
6
この入力例は小課題 5,6 の制約を満たす.
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2024/2025 예선 2 2번