How Can I solve this problem ! https://vjudge.net/problem/UVA-11904 Will be grateful if anyone can help. Thank You.
№ | Пользователь | Рейтинг |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
How Can I solve this problem ! https://vjudge.net/problem/UVA-11904 Will be grateful if anyone can help. Thank You.
Название |
---|
You can solve this problem by changing the perspective to solve it from the back, imagine you have $$$k_1+k_2+\cdots+k_n$$$ time slots. Notice that, because every $$$job_i$$$ must be finished before finishing $$$job_{i+1}$$$, then the last time slot must be taken with the last job ($$$job_n$$$). So you must put one $$$job_n$$$ in the last time slot, and then, just fill the remaining time slots with $$$k_n-1$$$ of the last job. So we will have $$$C(k_1+k_2+\cdots+k_n-1,k_n-1)$$$ ways of filling this time slots. You can then just imagine throwing out away the time slots taken by $$$job_n$$$, then this problem goes out the same for the second last job, and then for the third last job and so on.
You can solve this problem by using a simple $$$\text{prefix sum}$$$ ($$$pre[x]=\sum_{i=1}^{x}k_i$$$), and also $$$\text{precompute factorials}$$$ and $$$\text{inverse modulo factorials}$$$ to easily compute $$$\text{combinations}$$$. With all that in place, we will have the final answer, which is:
For reference, you can see my $$$\text{Accepted}$$$ code for this problem.