DMOPC '21 Contest 3 P6 - Good Grids

View as PDF

Points: 30 (partial)
Time limit: 1.5s
Memory limit: 256M

Author:
Problem types

An by grid of characters is called good if it satisfies these three conditions:

• Each character is either A, B, or C.
• Every by subgrid contains all three different letters.
• Any two cells that share exactly one corner contain different letters.

Let denote the cell in the -th row from the top and -th column from the left.

You want to construct a good grid that satisfies some of constraints. Each constraint consists of a positive integer value and two cells and that share an edge. You will get points if your good grid has the same letter in cells and .

Find a good grid that gets the most total number of points.

For all :

Input Specification

The first line contains three space-separated integers: , , and .

The next lines contain five space-separated integers: , , , , and .

Output Specification

On the first line, output the maximum total number of points obtainable by a good grid.

On the next lines, output a good grid that obtains this total number of points. If there are many possible good grids, output any of them.

Scoring

For each test case:

• You will receive of the points if your first line of output contains the correct answer and the remaining lines contain a correctly formatted good grid that obtains this total number of points.
• Otherwise, you will receive of the points if your first line of output contains the correct answer. You do not need to print anything after the first line if you are aiming for these partial points, as long as you ensure that the first line is terminated by a \n character. You will still receive these partial points if you output a malformatted or incorrect grid.
• Otherwise, you will receive points.

Your final score is the minimum score over all test cases.

Sample Input

3 4 6
3 1 2 1 3
1 2 3 1 3
4 3 4 2 4
1 2 2 3 2
5 2 1 2 2
9 2 1 2 2

Sample Output

21
BAAA
CCBC
BAAC

Explanation

This grid is good and satisfies the st, rd, th, and th constraints, for a total of points. It can be proven that it is impossible to obtain more than points.