Mini Tetris
Time limit2sMemory limit512 MB
Choose the position and rotation of each of the three figure types as it falls so that five non-empty lines never build up before n figures land.
- Level
Medium6 of 10
- Topics
- Simulation, Dynamic programming, Game theory
- Solved
- No attempts yet
Problem
As you may know, the popular computer game Tetris was invented by Russian programmer Alexey Pajitnov. In this problem you need to write a program that plays a simplified version of this game.
The playing field is a rectangular vertical shaft called the well. Random figures made of unit square blocks appear at the top of the well. The player chooses the horizontal position and rotation of the figure, and then the figure falls down into the well. The objective of the game is to create horizontal lines filled without gaps. When such a line is created, it disappears, and any blocks above the deleted line fall down.
In this version, the well size is ___ units, and there are only three types of figures:
| Type | Figure |
|---|---|
| 1 |  |
| 2 |  |
| 3 |  |
You lose if at some point there are five non-empty lines in the well. You win if you have not lost after figures have fallen.
You need to write a program that plays the game and wins regardless of which figures appear.
Constraints
In all subtasks, .