Editorial for COCI '06 Regional #2 Tetris
Submitting an official solution before solving the problem yourself is a bannable offence.
Imagine that a piece is at the bottom of an empty field. The piece can then be encoded as a sequence of numbers if we write down the lowest occupied row for each column the piece occupies.
For example, piece number in its four rotations gives following four sequences:
, , and .
We say that sequence corresponds to sequence if adding some constant to all elements of gives sequence .
For example, sequence corresponds to , but not to or .
Observe that a piece can be inserted at a given position only if the sequence of heights at that position corresponds to the encoding of the piece. Therefore in order to obtain the solution we simply need to check all possible positions of all rotations for the given piece and field. Note that not all pieces have possible rotations. Piece is the same regardless of the rotation and pieces , and have only two possible rotations.
Comments