Polish Flag
Time limit2sMemory limit128 MB
Three children grow regions of blocks from three fixed edges with priority rules and simultaneous expansion each turn; count each child's white (top) and red (bottom) cells.
- Level
Hard8 of 10
- Topics
- Simulation, Geometry, Math, Implementation
- Solved
- No attempts yet
Problem
Three children -- Lucy, Bob, and Roy -- are building a Polish flag out of unit square blocks. The flag is a rectangle blocks wide and blocks high, where is a positive integer. It consists of white blocks and red blocks, and the board has slots in total. The white blocks must fill the top rows and the red blocks must fill the bottom rows. Rows are numbered from to from top to bottom, and columns from to from left to right. A slot's position is written as (column, row).
The children lay blocks in turns (all three act during each turn). In the first turn Lucy puts a block on the left edge at , Bob puts a block on the bottom edge at , and Roy puts a block on the right edge at , where and .
In every later turn a child may put a block into a slot only if that slot is empty and would be adjacent to one of the blocks that same child placed in the immediately preceding turn. (Two blocks are adjacent if they share a side.) In each turn every child places as many blocks as possible. Only one block may go into a slot. If two or more children want to place a block into the same slot in the same turn, Lucy has the highest priority, then Bob, and Roy has the lowest.
For each child, compute how many blocks of each color they end up placing. A block's color is fixed by the slot it occupies: cells in the top rows are white and cells in the bottom rows are red.
Input
The first and only line contains four integers , , , separated by single spaces, with , , and . In 50% of the test cases does not exceed .
Output
Print a single line with six integers separated by single spaces. The first and second are the numbers of white and red blocks that Lucy needs; the third and fourth are the numbers of white and red blocks that Bob needs; the fifth and sixth are the numbers of white and red blocks that Roy needs.
Hint
