| Submit | All submissions | Best solutions | Back to list |
ADV04I1 - Boards (Hard) |
Super Board Games Inc. is a big company producing board games. A new game was invented within it which may become very popular. A board divided into square cells is required for this game. Left and lower borders of the board should be level and the height of columns of cells should not increase from left to right. Also the board must be entirely paveable with dominoes. After it was found out that the game is the most interesting when played on the board consisting of n cells, it has been decided to release as many versions of the game using different n-cell boards as possible. Help the company count the number of different boards that can be released.
Input
The first line of input is number T - the amount of test cases. Each test is a single integer n - the number of cells.
Constraints
1 <= T <= 100
1 <= n <= 100
Output
For each test case output the answer to the problem in the statement.
Example
Input: 3 2 3 4 Output: 2 0 5
| Added by: | Spooky |
| Date: | 2010-11-14 |
| Time limit: | 1s |
| Source limit: | 1000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Advancement Autumn 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin |
hide comments
|
2013-05-02 04:44:37 Ashish Lavania
for 3 why is ### or # # # not possible?....plz define paveable! --ans(francky)--> paveable is meant with 1×2 rectangles. Re: thanks!! btw,one of the toughest problems I ever came across! Last edit: 2013-05-14 00:12:13 |
|
|
2013-02-10 01:00:36 Alex Anderson
For the problem, we're using lots of 1xk rectangles, where k will change a lot. "Left and lower borders of the board should be level" means that you are placing your 1xk rectangles all on a flat surface, and they always touch the bottom: Ex of a board with N = 10 cells. ## ### ##### "height of columns of cells should not increase from left to right" means that the height should be equal or lesser when you go to the right. Here is goes 3 3 2 1 1. " paveable with dominoes." means that if you looked at your board, you should be able to cover it with dominoes: Ex: N = 6, can pave ## ## ## Ex: N = 6, can't pave # ## ### So it is asking how many arrangements are there such that it uses N cells, the heights do not increase from left to right, and you can pave it with dominoes. |
|
|
2012-12-13 02:46:45 Alex Anderson
On the contrary, it is easy to understand what it is asking. Solving it is another matter. |
|
|
2012-12-11 19:09:18 Ashish Lavania
Boards(hard) : hard to understand? @Alex Please help me then in understanding it Last edit: 2012-12-20 15:39:03 |
|
|
2010-12-15 10:20:58 .:: Pratik ::.
Can the statement be explained more clearly? What is "paveable"? Can there be explanation for the sample IO? |
RSS