NOI '17 P4 - Game - Olympiads Online Judge

NOI '17 P4 - Game

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 2.0s

Memory limit: 128M

Problem type

Background

Asphalt is Little L's favorite game. Different from other amateur players, Little L is good at studying game design while playing games, so he has a unique game strategy.

Title Description

Little L plans to play $n$ $n$ games, each game uses a map, and Little L will choose a car to complete the game on this map.

Little L has three racing cars, represented by capital letters $A$ $A$ , $B$ $B$ , and $C$ $C$ . There are four types of maps, represented by lowercase letters $x$ $x$ , $a$ $a$ , $b$ $b$ , and $c$ $c$ .

Among them, car $A$ $A$ is not suitable for use on map $a$ $a$ , car $B$ $B$ is not suitable for use on map $b$ $b$ , car $C$ $C$ is not suitable for use on map $c$ $c$ , and map $x$ $x$ is suitable for all cars to participate in.

There aren't many maps available for all racers, only $d$ $d$ maps at most.

$n$ $n$ The map of the game can be described by a string composed of lowercase letters. For example: $S=\texttt{xaabxcbc}$ $S = xaabxcbc$ means that little L plans to play $8$ $8$ games, in which the map type of the $1$ $1$ and $5$ $5$ games is $x$ $x$ , suitable for all racing cars, the $2$ $2$ and $3$ $3$ maps are $a$ $a$ , not suitable for racing cars $A$ $A$ , and the $4$ $4$ and $7$ $7$ games are $b$ $b$ , not suitable for racing cars $B$ $B$ , $6$ $6$ and $8$ $8$ maps are $c$ $c$ , not suitable for racing $C$ $C$ .

Little L has some special requirements for the game. These requirements can be described by the 4-tuple $(i, h_i, j, h_j)$ $(i, h_{i}, j, h_{j})$ , which means that if the car with the model $h_i$ $h_{i}$ is used in the $i$ $i$ game, then the car with the model $h_j$ $h_{j}$ should be used in the $j$ $j$ game.

Can you help little L choose the car to use for each game? If there are multiple schemes, output any one of them.

If there is no solution, output -1.

Input Specification

The first line of input contains two non-negative integers $n$ $n$ , $d$ $d$ .

Enter the second line as a string $S$ $S$ .

The meanings of $n$ $n$ , $d$ $d$ , $S$ $S$ are described in the title, where $S$ $S$ contains $n$ $n$ characters, and exactly $d$ $d$ of them are lowercase letters $x$ $x$ .

Enter a positive integer $m$ $m$ in the third line, indicating that there are $m$ $m$ car rules.

The next $m$ $m$ lines, each line contains a quaternion $i,h_i,j,h_j$ $i, h_{i}, j, h_{j}$ , where $i,j$ $i, j$ are integers, and $h_i,h_j$ $h_{i}, h_{j}$ are characters $A$ $A$ , $B$ $B$ or $C$ $C$ , see the title description for the meaning.

Output Specification

Output one line.

Output -1 if there is no solution.

If there is a solution, it contains a string of length $n$ $n$ containing only capital letters A, B, and C, indicating how the little L arranges the use of the car in this $n$ $n$ game. If there are multiple sets of solutions, just output any one of them.

Sample Input 1

Copy

3 1
xcc
1
1 A 2 B

Sample Output 1

Copy

ABA

Explanation for Sample Output 1

Little $L$ $L$ plans to play $3$ $3$ games, where $1$ $1$ map type is $x$ $x$ , which is suitable for all cars, and $2$ $2$ and $3$ $3$ maps are $c$ $c$ , which is not suitable for car racing $C$ $C$ .

Little $L$ $L$ Wish: If $1$ $1$ game uses car $A$ $A$ , then $2$ $2$ game uses car $B$ $B$ .

Then arranging cars $A$ $A$ , $B$ $B$ , $A$ $A$ for the $3$ $3$ games respectively would satisfy all the conditions.

All conditions are also met and considered correct if the car is assigned $BBB$ $B B B$ or $BAA$ $B A A$ for $3$ $3$ games in turn.

However, when the car is arranged sequentially as $AAB$ $A A B$ or $ABC$ $A B C$ , it is not considered the correct answer because all conditions cannot be met.

Sample Input / Output 2

See attached file for details.

Constraints

Test case	$n$ $n$	$d$ $d$	$m$ $m$	other properties
$1$ $1$	$\le 2$ $\leq 2$	$0$ $0$	$\le 4$ $\leq 4$	None
$2$ $2$	$\le 2$ $\leq 2$	$\le n$ $\leq n$	$\le 4$ $\leq 4$	None
$3$ $3$	$\le 5$ $\leq 5$	$0$ $0$	$\le 10$ $\leq 10$	None
$4$ $4$	$\le 5$ $\leq 5$	$\le n$ $\leq n$	$\le 10$ $\leq 10$	None
$5$ $5$	$\le 10$ $\leq 10$	$0$ $0$	$\le 20$ $\leq 20$	None
$6$ $6$	$\le 10$ $\leq 10$	$\le 8$ $\leq 8$	$\le 20$ $\leq 20$	None
$7$ $7$	$\le 20$ $\leq 20$	$0$ $0$	$\le 40$ $\leq 40$	$S$ $S$ contains only $c$ $c$
$8$ $8$	$\le 20$ $\leq 20$	$0$ $0$	$\le 40$ $\leq 40$	None
$9$ $9$	$\le 20$ $\leq 20$	$\le 8$ $\leq 8$	$\le 40$ $\leq 40$	$S$ $S$ contains only $x$ $x$ or $c$ $c$
$10$ $10$	$\le 20$ $\leq 20$	$\le 8$ $\leq 8$	$\le 40$ $\leq 40$	None
$11$ $11$	$\le 100$ $\leq 100$	$0$ $0$	$\le 200$ $\leq 200$	$S$ $S$ contains only $c$ $c$
$12$ $12$	$\le 100$ $\leq 100$	$0$ $0$	$\le 200$ $\leq 200$	None
$13$ $13$	$\le 100$ $\leq 100$	$\le 8$ $\leq 8$	$\le 200$ $\leq 200$	$S$ $S$ contains only $x$ $x$ or $c$ $c$
$14$ $14$	$\le 100$ $\leq 100$	$\le 8$ $\leq 8$	$\le 200$ $\leq 200$	None
$15$ $15$	$\le 5\times 10^3$ $\leq 5 \times 10^{3}$	$0$ $0$	$\le 10^4$ $\leq 10^{4}$	None
$16$ $16$	$\le 5\times 10^3$ $\leq 5 \times 10^{3}$	$\le 8$ $\leq 8$	$\le 10^4$ $\leq 10^{4}$	$S$ $S$ contains only $x$ $x$ or $c$ $c$
$17$ $17$	$\le 5\times 10^3$ $\leq 5 \times 10^{3}$	$\le 8$ $\leq 8$	$\le 10^4$ $\leq 10^{4}$	None
$18$ $18$	$\le 5\times 10^4$ $\leq 5 \times 10^{4}$	$0$ $0$	$\le 10^5$ $\leq 10^{5}$	None
$19$ $19$	$\le 5\times 10^4$ $\leq 5 \times 10^{4}$	$\le 8$ $\leq 8$	$\le 10^5$ $\leq 10^{5}$	$S$ $S$ contains only $x$ $x$ or $c$ $c$
$20$ $20$	$\le 5\times 10^4$ $\leq 5 \times 10^{4}$	$\le 8$ $\leq 8$	$\le 10^5$ $\leq 10^{5}$	None

Comments

-2

LeoLiυ commented on Nov. 19, 2024, 9:32 p.m.

Do it yourself then

-4

LeoLiυ commented on Oct. 18, 2023, 8:24 p.m.

Bad wording

-2

neodymiumIronBoron commented on Oct. 21, 2023, 5:11 a.m.

skill issue