Trò chơi máy tính

Điểm: 6,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Trong trò chơi máy tính yêu thích của Petya, anh đến vòng cuối phải đánh trùm. Petya tìm được một số bùa chú để hỗ trợ.

Trận đấu diễn ra như sau:

Trùm có hai tham số: $m a x$ — máu khởi điểm (cũng là máu tối đa), và $r e g$ — lượng máu hồi mỗi giây.
Mỗi bùa chú có hai tham số: $p o w_{i}$ — sức mạnh tính theo phần trăm máu của trùm (chỉ được dùng bùa khi máu hiện tại của trùm $\leq p o w_{i} %$ của $m a x$ ), và $d m g_{i}$ — sát thương mỗi giây mà bùa gây ra cho trùm kể từ khi được kích hoạt cho đến hết trận.

Mỗi giây, các hành động diễn ra theo đúng thứ tự:

Trùm nhận sát thương từ tất cả các bùa đã được kích hoạt.
Trùm hồi $r e g$ máu (nhưng không vượt quá $m a x$ ).
Người chơi có thể dùng tối đa một bùa mới (nếu điều kiện $p o w_{i}$ thỏa).

Trùm bị đánh bại nếu cuối một giây nào đó máu của trùm $\leq 0$ . Bùa được đánh số từ $1$ , và giây $0$ là giây đầu tiên người chơi được phép dùng bùa. Không được dùng bùa sau khi trùm đã bị đánh bại.

Hãy xác định liệu Petya có thể đánh bại trùm với bộ bùa hiện có hay không, và nếu được thì thời gian tối thiểu là bao nhiêu.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N$ , $m a x$ , $r e g$ .
$N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $p o w_{i}$ và $d m g_{i}$ — tham số của bùa thứ $i$ .

Dữ liệu ra

Nếu không thể đánh bại trùm, in ra duy nhất một dòng NO.
Ngược lại, dòng đầu in YES. Dòng thứ hai in hai số: thời gian tối thiểu để đánh bại trùm và số bùa đã dùng. Mỗi dòng tiếp theo in hai số: thời điểm dùng bùa và chỉ số của bùa đó, in theo đúng thứ tự dùng.

Nếu có nhiều lịch trình tối ưu, in ra một lịch trình bất kỳ.

Ràng buộc

$1 \leq N, m a x, r e g \leq 1000$
$0 \leq p o w_{i} \leq 100$
$1 \leq d m g_{i} \leq 2000$

Ví dụ

Input	Output	Giải thích
2 100 10 100 11 90 9	YES 19 2 0 1 10 2	Tại giây 0 dùng bùa 1 (sát thương $11$ /giây). Mỗi giây trùm mất $11 - 10 = 1$ máu, nên sau $10$ giây máu còn $90$ , dùng được bùa 2. Từ đó mất $20 - 10 = 10$ máu/giây, đến giây $19$ thì máu $\leq 0$ .
2 10 3 100 3 99 1	NO	Sau khi dùng bùa 1 ở giây 0, máu trùm luôn quay về $10$ ( $100 %$ ) sau bước hồi, nên không bao giờ dùng được bùa 2 (yêu cầu $\leq 99 %$ ).
3 200 10 100 3 100 8 50 1000	YES 102 3 0 2 1 1 101 3	Dùng bùa 2 rồi bùa 1 trong hai giây đầu. Sát thương tổng cộng $11$ /giây, máu giảm dần $1$ /giây từ $200$ . Đến giây $101$ máu còn $100 = 50 %$ thì dùng được bùa 3 (sát thương cực lớn) và kết liễu vào giây $102$ .

Bình luận

Không có bình luận tại thời điểm này.