LQDOJ Cup 2024 - Round #6 - HERO
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
hero.inp
Output:
hero.out
Công chúa vương quốc LQDOJ đã bị bắt bởi \(1\) con rồng đáng sợ, vì vậy, quốc vương quyết định nhờ bạn (một người giỏi võ nghệ) lên đường giải cứu công chúa.
Hang ổ của con rồng này nằm cách vương quốc \(n\) đơn vị khoảng cách, đường đi từ vương quốc đến hang ổ có thể coi như một trục số nằm ngang, mỗi vị trí \(i\) \((1 \le i \le n)\) nguyên trên đường đi lại có \(1\) trong \(4\) tính chất sau:
- Không gây ảnh hưởng gì đến bạn.
- Tăng cho bạn \(1\) thể lực.
- Tăng cho bạn \(1\) máu.
- Có \(1\) con quái vật là tay sai của con rồng, bạn có \(2\) lựa chọn: lẩn trốn và bị mất \(1\) máu, đánh bại con quái vật này và bị mất \(1\) thể lực.
Ban đầu, bạn có \(p\) thể lực và \(h\) máu.
Hãy giải cứu công chúa bằng cách tiêu diệt ít quái vật nhất mà luôn giữ cho máu và thể lực dương. Trong trường hợp bạn không thể giải cứu nàng, hãy in ra \(-1\).
Input
- Dòng đầu tiên chứa \(3\) số nguyên dương \(n\), \(p\), \(h\) \((1 \le n, p, h \le 200)\).
- Dòng thứ hai chứa \(n\) số \(a_i\) \((0 \le a_i \le 3)\) với \(0\) là sẽ không gây ảnh hưởng đến bạn, \(1\) là tăng thể lực, \(2\) là tăng máu, và \(3\) là có quái vật.
Output
- Dòng đầu tiên chứa số nguyên \(x\) là số quái vật ít nhất cần tiêu diệt.
- Dòng thứ hai chứa \(x\) số nguyên dương \(t_i\) \((1 \le t_i \le n)\) là các vị trí của quái vật bạn sẽ tiêu diệt in theo thứ tự bất kì, nếu có nhiều phương án, in \(1\) phương án bất kì.
Scoring
- Subtask \(1\) (\(35\%\) số điểm): \(n \le 20\).
- Subtask \(2\) (\(25\%\) số điểm): Không có vị trí loại \(1\) và \(2\).
- Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
5 1 1
0 0 2 3 1
Output
0
Note
Ở test ví dụ, bạn đi đến vị trí số \(3\) và được tăng \(1\) máu, do đó bạn hoàn toàn có thể đi tiếp mà không cần đánh bại con quái vật ở ô số \(4\).
Kỳ thi:
- LQDOJ Cup 2024 - Round #6 (19 Tháng 10., 2024)
Bình luận