Đánh Nhau Với Quái Vật

Điểm: 4,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

Có $n$ con quái vật xếp thành hàng, đánh số từ $1$ đến $n$ . Quái vật thứ $i$ có $h_{i}$ điểm máu (HP). Bạn có sức tấn công bằng $a$ HP, đối thủ có sức tấn công bằng $b$ HP.

Bạn và đối thủ lần lượt đánh từng con quái vật cho tới khi nó chết, rồi mới chuyển sang con tiếp theo. Một con quái vật được coi là chết khi HP của nó nhỏ hơn hoặc bằng $0$ .

Trận đánh với mỗi con quái vật diễn ra theo lượt:

Bạn đánh quái vật, làm mất $a$ HP. Nếu nó chết sau cú đánh của bạn, bạn được $1$ điểm và cả hai cùng chuyển sang con tiếp theo.
Đối thủ đánh quái vật, làm mất $b$ HP. Nếu nó chết sau cú đánh của đối thủ, không ai được điểm và cả hai cùng chuyển sang con tiếp theo.

Bạn có một kỹ thuật bí mật cho phép ép đối thủ bỏ qua lượt đánh của họ. Bạn có thể sử dụng kỹ thuật này không quá $k$ lần tổng cộng (có thể chia tuỳ ý giữa các con quái vật).

Hãy xác định số điểm tối đa bạn có thể đạt được nếu sử dụng kỹ thuật bí mật một cách tối ưu.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên $n$ , $a$ , $b$ , $k$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ; $1 \leq a, b, k \leq 10^{9}$ ).
Dòng thứ hai chứa $n$ số nguyên $h_{1}, h_{2}, \dots, h_{n}$ ( $1 \leq h_{i} \leq 10^{9}$ ).

Dữ liệu ra

In ra một số nguyên — số điểm tối đa bạn có thể đạt được.

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq a, b, k \leq 10^{9}$
$1 \leq h_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
6 2 3 3 7 10 50 12 1 8	5	Có thể dành kỹ thuật bí mật để giành thêm điểm cho các con quái vật mà bình thường đối thủ sẽ kết liễu. Số điểm tối đa đạt được là $5$ .
1 1 100 99 100	1	Quái vật có $100$ HP. Bạn dùng kỹ thuật $99$ lần liên tiếp để chỉ bạn đánh, kết liễu nó sau $100$ đòn.
7 4 2 1 1 3 5 4 2 7 6	6	Chỉ cần $1$ lần dùng kỹ thuật là đủ để bạn giành $6$ điểm trong $7$ con quái vật.

Bình luận

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