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.
Input
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.
Output
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.
Example
Input: 20 1 9747 -1 Output: 5 1 57
hide comments
|
lumaks_69:
2022-02-15 16:29:32
O(n^2) + 1 break and u get ac
|
|
Rahul Jain:
2014-09-25 22:22:56
Accepting O(n^2) :)
|
|
Dinesh:
2013-12-26 04:37:15
Double Century :) |
|
coding_express:
2013-06-25 08:03:07
is time limit very strict
|
|
aqfaridi:
2014-03-13 20:37:52
use constraint..
|
|
malioboro:
2012-11-19 23:23:57
nice problem :)
|
|
Francky:
2012-10-07 07:42:22
@Fidel : very good idea, and easier problems can land in tutorial. Also make sure, if possible, that problems are feasible in Python3 (or any slow language) without IO optimization, many of us will appreciate your effort.
|
|
Fidel Schaposnik:
2012-10-07 04:25:22
Finally, I am also planning to upload harder variations of the easier problems in the contest, so that the more experienced coders don't have to feel like a good idea/story is wasted on an "easy" problem ;-) However, they will surely *not* be as simple as reducing the admitted code length or increasing the valid range of some variables... Last edit: 2012-10-07 04:32:28 |
|
|
Fidel Schaposnik:
2012-10-07 04:22:49
Also, in the real contest we had many teams with very different coding levels, so the problemset was designed to include problems with a wide range of difficulties. I am quite sure the same is true here at SPOJ, so I expect some people will find these problems more challenging than others. I will continue to upload the rest of the problems in the contest during the next few days, so I hope you will yourselves find at least some of them more challeging... |
|
|
Fidel Schaposnik:
2012-10-07 04:16:39
I appreciate the comments and suggestions, but for educational purposes we would like to have all the problems be as close as possible to what they were in the original contest. They have been tested with this in mind, usually with > 5 solutions in at least 2 different languages, and the time limits have been set so that every solution that would have got AC during the real contest is to be accepted. No other restrictions have been imposed. |
| Added by: | Fidel Schaposnik |
| Date: | 2012-10-04 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Argentinian Programming Tournament 2012 |
RSS