Painting a paper sheetProblem code: F3 |
All submissions for this problem are available.
The Chef has a huge square napkin of size 2n X 2n. He folds the napkin n-3 times. Each time he folds its bottom side over its top side, and then its right side over its left side. After each fold, the side length of the napkin is reduced by half. The Chef continues folding until there remains a 8x8 sheet, lying flat on a table.
Oh, did I forget to mention that the Chef was cooking a new brown colored curry while folding the napkin. He drops some brown colored gravy onto some cells in the folded 8x8 napkin. When he drops the gravy, it soaks through all the cells below it.
Now the Chef unfolds the napkin to its original size. There are now many curry stained brown colored cells in the napkin. They form several separate regions, each of which is connected. Could you help the Chef count how many regions of brown cells are there in the napkin?
Note that two cells are adjacent if they share a common edge (they are not considered adjacent if they only share a corner). Two cells are connected if we can go from one cell to the other via adjacent cells. A region is a maximal set of cells such that every two of its cells are connected.
Please see the example test case and the figures below for more details.
Input
The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case has the following form:
- The first line contains N (3 N 109)
- Then, 8 lines follow. Each line contains 8 numbers, 0 or 1, where 1 denotes a stained brown cell in the folded napkin.
Output
For each test case, print a single number that is the number of disconnected brown regions in the unfolded napkin. Since the result may be a very large number, you only need to print its remainder when dividing by 21945.
Example
Input: 3 3 01000010 11000001 00000000 00011000 00011000 00010100 00001000 00000000 4 01000010 11000001 00000000 00011000 00011000 00010100 00001000 00000000 1000000000 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 Output: 6 22 1
Output details
Case 1 and 2: There are 6 brown regions in the 8x8 napkin. If we unfold it once, it has 22 brown regions: 11 regions in the top half and 11 regions in the bottom half (as shown in the figure above).
Case 3: All cells of the napkin are stained, so there is always one brown region, no matter how many times the Chef unfolds the napkin.
| Author: | admin |
| Date Added: | 10-07-2009 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
I think that last example has wrong output. It can't be 1. Can you please verify?
sorry, ignore my last comment, I misread it
The figure is not visible
There is no figure
@admin please look at this problem...the figure is not visible
There is no figure, the problem statement has been updated.
@Admin: Which side are we supposed to unfold the napkin?
The unfolding should be done in a way opposite to the folding process.
@Admin: Can you explain how will the unfolding of the first test case yield 6 stains?
In the first case, the napkin is not folded at all. The dimensions of the napkin are 8X8 to start off with and 6 is the total number of connected stains in the napkin.
why no option is coming for