codeforces-scrape

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

1902B.md (3469B)


      1 Source: https://codeforces.com/problemset/problem/1902/B
      2 
      3 B. Getting Points
      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 Monocarp is a student at Berland State University. Due to recent changes in the Berland education system, Monocarp has to study only one subject — programming.
     22 
     23 The academic term consists of $n$ days, and in order not to get expelled, Monocarp has to earn at least $P$ points during those $n$ days. There are two ways to earn points — completing practical tasks and attending lessons. For each practical task Monocarp fulfills, he earns $t$ points, and for each lesson he attends, he earns $l$ points.
     24 
     25 Practical tasks are unlocked "each week" as the term goes on: the first task is unlocked on day $1$ (and can be completed on any day from $1$ to $n$), the second task is unlocked on day $8$ (and can be completed on any day from $8$ to $n$), the third task is unlocked on day $15$, and so on.
     26 
     27 Every day from $1$ to $n$, there is a lesson which can be attended by Monocarp. And every day, Monocarp chooses whether to study or to rest the whole day. When Monocarp decides to study, he attends a lesson and can complete no more than $2$ tasks, which are already unlocked and not completed yet. If Monocarp rests the whole day, he skips a lesson and ignores tasks.
     28 
     29 Monocarp wants to have as many days off as possible, i. e. he wants to maximize the number of days he rests. Help him calculate the maximum number of days he can rest!
     30 
     31 Input
     32 
     33 The first line contains a single integer $tc$ ($1 \le tc \le 10^4$) — the number of test cases. The description of the test cases follows.
     34 
     35 The only line of each test case contains four integers $n$, $P$, $l$ and $t$ ($1 \le n, l, t \le 10^9$; $1 \le P \le 10^{18}$) — the number of days, the minimum total points Monocarp has to earn, the points for attending one lesson and points for completing one task.
     36 
     37 It's guaranteed for each test case that it's possible not to be expelled if Monocarp will attend all lessons and will complete all tasks.
     38 
     39 Output
     40 
     41 For each test, print one integer — the maximum number of days Monocarp can rest without being expelled from University.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 1 5 5 2
     51 
     52 14 3000000000 1000000000 500000000
     53 
     54 100 20 1 10
     55 
     56 8 120 10 20
     57 
     58 42 280 13 37
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 12
     66 99
     67 0
     68 37
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, the term lasts for $1$ day, so Monocarp should attend at day $1$. Since attending one lesson already gives $5$ points ($5 \ge P$), so it doesn't matter, will Monocarp complete the task or not.
     74 
     75 In the second test case, Monocarp can, for example, study at days $8$ and $9$: at day $8$ he will attend a lesson for $10^9$ points and complete two tasks for another $5 \cdot 10^8 + 5 \cdot 10^8$ points. And at day $9$ he only attends a lesson for another $10^9$ points.
     76 
     77 In the third test case, Monocarp can, for example, study at day $42$: attending a lesson gives him $1$ point and solving $2$ out of $6$ available tasks gives him another $2 \cdot 10$ points.
     78 
     79 In the fourth test case, Monocarp has to attend all lessons and complete all tasks to get $8 \cdot 10 + 2 \cdot 20 = 120$ points.
     80 
     81 In the fifth test case, Monocarp can, for example, study at days: $8$ — one lesson and first and second tasks; $15$ — one lesson and the third task; $22$ — one lesson and the fourth task; $29$ — one lesson and the fifth task; $36$ — one lesson and the sixth task.