Problem-D this is D problem of Atcoder beginner contest 163 from last night. I'm still unable to get the logic, can anyone explain the solution?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Problem-D this is D problem of Atcoder beginner contest 163 from last night. I'm still unable to get the logic, can anyone explain the solution?
Name |
---|
Since you can take every number of elements from k to n, you can look at them seperately since $$$10^{100}$$$ is so big that the sum with less elements will always be less than the sum with more elements. Then for each number of elements (lets call it j) the minimum sum will be $$$\sum_{i=0}^{j-1} (100^{100}+i) = j \cdot 100^{100} + \sum_{i=0}^{j-1} i$$$ (the smallest j numbers added together). And the maxmimum number will be the biggest j numbers added together which is $$$j \cdot 100^{100} + \sum_{i=n-j+1}^{n} i $$$. It is obvious that you can create all numbers in between the maximum and the minimum. Repeat that for every j from k to n and add the results together.