NAC | NAPC 2021 Practice Contest (July 10th)


2021-07-10 06:00 AKDT

NAC | NAPC 2021 Practice Contest (July 10th)


2021-07-10 11:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -74 days 12:00:47

Time elapsed


Time remaining


Problem H
Brick Wall

Pat and Mat are trying to build a brick wall. They have three types of bricks—all have the same depth and height but they are of three different widths: 1, 2, and 3. As every builder knows (and Pat and Mat learned after watching their walls fall down quite a few times), a wall is built by layering rows of bricks, with the added requirement that for any two neighboring bricks there has to be a brick above that covers the connection of the two bricks (unless the bricks are in the top-most row). Pat and Mat somehow managed to build quite a few rows and now they are about to do the last row. But they are having troubles figuring out whether it is possible to build the last row so that all connections in the row below are covered. Of course, all the rows have to be of the same length and aligned on the sides. Help!

\includegraphics[width=0.5\textwidth ]{brickwall}
Figure 1: A possible solution for the first sample input, with one brick of length 2 unused.


The wall is described on two lines. The first of these lines contains four numbers $N$, $c_1$, $c_2$, $c_3$, separated by spaces, where $N$ is the number of bricks in the (currently) top-most row and $c_ i$ describes the number of bricks of width $i$ for $i = 1, 2, 3$ that are available for the last row. The second line describes the currently top-most row—it contains a sequence $b_1, b_2, \ldots , b_ N$ of brick lengths for the bricks that form the row, in the order given by the sequence. You may assume that $N$ is at most $100$ and each of $c_1$, $c_2$, and $c_3$ is at most $300$.


The output contains one line with the string “YES” if it is possible to build the last row for the $i$-th brick wall, and “NO” otherwise.

Sample Input 1 Sample Output 1
5 2 1 3
2 3 1 3 2
Sample Input 2 Sample Output 2
5 1 2 3
2 3 1 3 2
Sample Input 3 Sample Output 3
5 6 1 1
2 3 1 2 3