codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1296D.md (2189B)


      1 Source: https://codeforces.com/problemset/problem/1296/D
      2 
      3 D. Fight with Monsters
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There are $n$ monsters standing in a row numbered from $1$ to $n$. The $i$-th monster has $h_i$ health points (hp). You have your attack power equal to $a$ hp and your opponent has his attack power equal to $b$ hp.
     22 
     23 You and your opponent are fighting these monsters. Firstly, you and your opponent go to the first monster and fight it till his death, then you and your opponent go the second monster and fight it till his death, and so on. A monster is considered dead if its hp is less than or equal to $0$.
     24 
     25 The fight with a monster happens in turns.
     26 
     27 1. You hit the monster by $a$ hp. If it is dead after your hit, you gain one point and you both proceed to the next monster.
     28 2. Your opponent hits the monster by $b$ hp. If it is dead after his hit, nobody gains a point and you both proceed to the next monster.
     29 
     30 You have some secret technique to force your opponent to skip his turn. You can use this technique at most $k$ times in total (for example, if there are two monsters and $k=4$, then you can use the technique $2$ times on the first monster and $1$ time on the second monster, but not $2$ times on the first monster and $3$ times on the second monster).
     31 
     32 Your task is to determine the maximum number of points you can gain if you use the secret technique optimally.
     33 
     34 Input
     35 
     36 The first line of the input contains four integers $n, a, b$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le a, b, k \le 10^9$) — the number of monsters, your attack power, the opponent's attack power and the number of times you can use the secret technique.
     37 
     38 The second line of the input contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), where $h_i$ is the health points of the $i$-th monster.
     39 
     40 Output
     41 
     42 Print one integer — the maximum number of points you can gain if you use the secret technique optimally.
     43 
     44 Examples
     45 
     46 Input
     47 
     48 ```
     49 6 2 3 3
     50 7 10 50 12 1 8
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 5
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 1 1 100 99
     63 100
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 1
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 7 4 2 1
     76 1 3 5 4 2 7 6
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 6
     83 ```