Editorial for COCI '16 Contest 7 #2 Uzastopni


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Trying out every possibility is too slow because of the size of the number N. It is important to notice that the number of possible summands cannot be very large. More precisely, the number of summands will not be greater than \sqrt{2N}, because otherwise their sum would exceed N (see this for yourself). Therefore, we have enough time to iterate over all possible K (where K is the number of consecutive summands), and for each of them search for the corresponding summands, i.e., the first and the last number – we can do this either mathematically (the formula is easily derived), or by binary search.


Comments

There are no comments at the moment.