We can first calculate the total number of pages that can be finished within one week. Then, we divide the total number of pages by this number and obtain the residual. Finally, for this residual, we find the last day on which the whole book is finished.
The description seems a little difficult to understand...
We should first rotate the wall papers with 90 degrees so that the stripes are vertical. Then, we cut it into as many pieces as possible according to the height of the room. Next, we compute the total length that these pieces can cover, and finally obtain the number of rolls that is necessary to decorate the whole room.
A straightforward implementation problem, but one needs take care of “corner” cases.
This is in fact an exhaustive search problem.
At first, we enumerate the number of 0s at the end. Then, we enumerate all the combinations of the first sum that is equal to 10, counting from right to left. Finally, we find all the digits that have sum equal to 9. This algorithm has complexity O(10N), and we only need record the maximum number of consecutive 0s among all the enumeration and the corresponding combination.
I think this is a very nice problem to practice segment tree with lazy propagation. One can find a lot of materials on the Internet about this technique, and one could also read chapter 28 in book Competitive Programmer's Handbook — a new book on competitive programming, which provides many detailed descriptions and talks about how to implement it.
Besides, there is still one important issue that should be considered. We should be very careful of precision problem. Instead of directly using probability domain, it is better to convert it into logarithm domain, since this can in general achieve a better dynamic range by replacing multiplication with addition. However, if the probability is zero, log(0) will lead to an exceptional case. To avoid this, we can aasign, for instance, - 1000 instead of log(0).
Комментарии (0)
