2038A.md (3651B)
1 Source: https://codeforces.com/problemset/problem/2038/A 2 3 A. Bonus Project 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a team of $n$ software engineers numbered from $1$ to $n$. Their boss promises to give them a bonus if they complete an additional project. The project requires $k$ units of work in total. The bonus promised to the $i$-th engineer is $a_i$ burles. The boss doesn't assign specific tasks to engineers; it is expected that every engineer will voluntarily complete some integer amount of work units. The bonus will be paid to the entire team only if the project is completed; in other words, if the total amount of voluntary work units on the project is greater than or equal to $k$. 22 23 The amount of work that can be performed by each engineer is not limited. However, all engineers value their labour. The $i$-th engineer estimates one unit of their work as $b_i$ burles. If the bonus is paid, the benefit $s_i$ of the $i$-th engineer for completing $c$ units of work is defined as $s_i = a_i - c \cdot b_i$. If the bonus is not paid, the engineer will not volunteer to do any work. 24 25 Engineers work together for many years, so they know how the bonus is going to be distributed and how much their colleagues value the labour. That is, all $a_i$ and all $b_i$ are known to every engineer in the team. 26 27 Engineers are eager to get the bonus, so they agreed on the following process of work distribution between them: 28 29 * the first engineer says: "I will complete $c_1$ units of work", where $c_1$ is a non-negative integer; 30 * then, the second engineer says: "I will complete $c_2$ units of work", where $c_2$ is a non-negative integer; 31 * ... and so on; 32 * finally, the $n$-th engineer says: "I will complete $c_n$ units of work", where $c_n$ is a non-negative integer. 33 34 Every engineer voices $c_i$ in a way to maximize their own benefit $s_i$. If the expected benefit is going to be zero, an engineer will still agree to work to get the experience and to help their colleagues obtain the bonus. However, if the benefit is expected to be negative for some reason (an engineer needs to perform an excessive amount of work or the project is not going to be completed), that engineer will not work at all (completes zero amount of work units). 35 36 Given that every engineer acts perfectly, your task is to find out the numbers $c_i$ voiced by every engineer. 37 38 Input 39 40 The first line contains two integers $n$ and $k$ ($1 \le n \le 1000$; $1 \le k \le 10^6$) — the number of engineers in the company and the number of work units the project requires, respectively. 41 42 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the bonus which will be paid to the $i$-th engineer if the project is completed. 43 44 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 1000$), where $b_i$ is the work unit cost for the $i$-th engineer. 45 46 Output 47 48 Print $n$ integers $c_1, c_2, \dots, c_n$ ($0 \le c_i \le k$) — the amount of work completed by each engineer given that every engineer behaves optimally. Note that the answer is unique. 49 50 Examples 51 52 Input 53 54 ``` 55 3 6 56 57 4 7 6 58 59 1 2 3 60 ``` 61 62 Output 63 64 ``` 65 1 3 2 66 ``` 67 68 Input 69 70 ``` 71 3 12 72 73 4 7 6 74 75 1 2 3 76 ``` 77 78 Output 79 80 ``` 81 0 0 0 82 ``` 83 84 Input 85 86 ``` 87 3 11 88 89 6 7 8 90 91 1 2 3 92 ``` 93 94 Output 95 96 ``` 97 6 3 2 98 ``` 99 100 Note 101 102 In the first example, engineers distributed the work across them and got the bonus, even though the benefit for the third engineer is zero. 103 104 In the second example, the bonus project requires too many work units to complete, so it's more beneficial for engineers not to work at all.