Problem E: Bloques |
Time Limit: 10 seconds |
Little Joan has N blocks,all of them of different sizes. He is playing to build cities in the beach. A city is just a collection of buildings.
A single block over the sand can be considered as a building. Then he can construct higher buildings by putting a block above any other block. At most one block can be put immediately above any other block. However he can stack several blocks together to construct a building. However, it’s not allowed to put bigger blocks on top of smaller ones, since the stack of blocks may fall. A block can be specified by a natural number that represents its size.
It doesn’t matter the order among buildings. That is:
1 3 2 4
3 1 4 2
Your problem is to compute the number of possible different cities using N blocks. We say that #(N) gives the number of different cities of size N. If N=2, for instance, there are only two possible cities:
City #1: 1 2
In this city both blocks of size 1 and 2 are put over the sand.
City #2: 1 2
In this city block of size 1 is over block is size 2, and block of size 2 is over the sand.
So, #(2)=2.
A sequence of non-negative integer numbers, each of one in different line. All of them but the last one are natural numbers. The last one is 0 and means the end. Each natural number is less than 900.
For each natural number I in the input, you must write a line with the pair of numbers I, #(I).
Sample input |
Sample output |
---|---|
2 3 0 |
2, 2 3, 5 |