Problem A
Thinking Backward
Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
Plane division by a common
shape is a very well known topic of computer science. The pictures below
shows some such diagrams. In figure 1 we find
that four circles divide a plane in maximum 14
zones, four ellipses divide a plane in maximum 26
zones and three triangles divide a plane in maximum 20
zones. It is a common practice to find out the maximum number of regions when
m shapes of same type intersects. For
example the general formula for circles is m2-m+2.
When the situation is hybrid (More than one type of shapes intersect) the
maximum possible number of regions is also not very difficult to find out.
In figure 2 we can see that eight regions
are created when one ellipse and one triangle intersect. In this problem you
will have to think in the reverse direction. You will be given the maximum
number of regions created and you will have to find how many ellipses, circles
and triangles were involved.
Input
Output
For each line of input you have to produce
two or more lines of output. The description of output for each line is given
below:
The first line is the serial number of
output. Each of the next lines contains three integers. These three integers
are possible values of m ,n and p for which maximum N
regions is created. When there is more than one solution then the solutions
should be sorted in ascending of m and then by ascending order of n.
If there is no valid solution output a line “Impossible.” instead. Look
at the output for sample input for details. Please note that for a valid
solution 0<=m<100, 0<=n<20000 and 0<=p<100.
20 10 -1 |
Case
1: 0
0 3 0
1 2 1
0 2 1
3 0 Case
2: Impossible. |
Problemsetter: Shahriar Manzoor, Member of Elite Problemsetters' Panel
Special Thanks to Derek Kisman (Alternate solution and eliminating confusions)