TAP2012B - Ball of Reconciliation
[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]
Every year the kingdoms of Cubiconia, Quadradonia and Nlogonia organize a ball to commemorate the end of the war that ravaged the region for many years. A certain number of noblemen of each kingdom is invited to participate in this event, and it is expected that every pair of guests coming from different kingdoms will dance together exactly once. That is, each of the guests from Cubiconia shall dance once with every guest from Quadradonia and Nlogonia; in turn, each of the guests from Quadradonia shall also dance once with every guest from Nlogonia. However, guests coming from the same kingdom are not allowed to dance with one another.
To help organize the ball, the total number of dances that will take place is determined beforehand, so that care must be taken when choosing the number of noblemen that shall be invited from each kingdom. For example, if it is decided that the ball must have N = 20 dances, one possibility is to invite 6 noblemen from Cubiconia, 2 from Quadradonia and 1 from Nlogonia, which can be represented by the expression (6, 2, 1). This is a valid option because the total number of dances would then be 6*2 + 6*1 + 2*1 = 20.
Traditions whose origins nobody can now remember indicate that the number of invited noblemen from Cubiconia must be greater or equal to the number of those coming from Quadradonia, and at the same time the number of invited noblemen from Quadradonia must be greater or equal to those coming from Nlogonia. Thus, for N = 20 dances there are exactly 5 possible ways to choose the number of guests from each kingdom, namely (5, 4, 0), (4, 2, 2), (10, 2, 0) and (20, 1, 0) as well as the aforementioned (6, 2, 1).
With so many restrictions, the organizing committee has problems finding the ideal way to choose the number of guests from each kingdom. Your task is to help this committee by counting the different ways in which the number of guests can be chosen for a ball with N dances. Two of these ways are considered different if they differ in the number of invited noblemen from at least on of the three kingdoms.
Each test case is described using a single line, containing an integer N representing the total number of dances that the ball must have (1 ≤ N ≤ 104). The end of the input is signalled by a line containing the number -1.
For each test case, print a single line containing the number of different ways in which the number of guests from each kingdom can be chosen in order to have a ball where there are exactly N dances, with all the restrictions mentioned in the problem statement.
Input: 20 1 9747 -1 Output: 5 1 57
Setting code limit under 1kB is already a great hint :)
If the problem had been well tested here, the constraints could have been code size under 1kB, maxN = 10⁵, time 3s.