P8369 [POI 2000 R1] Stripes

The Stripes game is a two-player game. The required items are a board and rectangular stripes in three colors: red, green, and blue. All red stripes have size $c \times 1$, all green stripes have size $z \times 1$, and all blue stripes have size $n \times 1$, where $c, z, n$ are positive integers. Each player has an unlimited number of stripes of each color. A board is a rectangle of size $p \times 1$, consisting of $p$ cells of size $1 \times 1$. Players move alternately. In each move, a player chooses one rectangular stripe and places it on the board, following these rules: 1. The stripe must not extend outside the board. 2. It must not overlap any already placed stripe (not even partially). 3. The edges of the stripe must coincide with the edges of the board cells. Whoever cannot make a move loses. The first player is the one who moves first in the game. Determine whether the first player has a winning strategy no matter how the second player plays. Write a program that: 1. Reads the stripe sizes and the sizes of at least one board. 2. For each given board, determines whether the first player has a winning strategy. 3. Outputs the results.

The first line contains three integers $c, z, n$, representing the lengths of the three stripes, in order: red, green, and blue. The numbers are separated by spaces. The second line contains an integer $m$, the number of different boards to consider. The following lines $3$ to $m + 2$ each contain one integer $p$. Line $i + 2$ gives the length of the $i$-th board.

Output $m$ lines. Exactly one number should be written on the $i$-th line: If the first player has a winning strategy for the $i$-th board, output $1$; otherwise output $2$.

For $100\%$ of the data: $1 \le c, z, n, m, p \le 1000$. Translated by ChatGPT 5