Problem A
The Cat Paradise
Languages
en
sv
When cats want to sleep, they deserve the coziest beds in the world.
Yoh is a volunteer at the cat shelter The Cat Paradise, which takes care of cats before they get a permanent home. The shelter has received $N$ new cat beds in $K$ different colors. Yoh wants to arrange the cat beds in a circle so that no two adjacent cat beds have the same color. Yoh thinks this will make every cat feel extra special, unique, and cared for.
Help Yoh arrange the cat beds, or determine that it is not possible to arrange them as Yoh wants.
Input
The first line contains two integers $N$ and $K$ ($3 \le N \le 2 \cdot 10^5, 2 \le K \le N$), the number of cat beds and the number of colors.
Then follow $K$ lines, one for each color. On each of these $K$ lines, there is first a string $s$ that is the name of the color, and an integer $c$ ($1 \leq c \leq N$), the number of cat beds of color $s$.
The sum of the numbers over all colors is guaranteed to be exactly $N$. All colors have unique names, and the names consist of up to 6 letters among a-z.
Output
If it is not possible to arrange the cat beds as Yoh wants, print “No”.
Otherwise, print a line with the word “Yes”, followed by a new line with the colors of the $N$ cat beds in the same order as they are placed around the circle. If there are multiple solutions, you may output any of them. Note that because the placement is circular, the starting point does not matter. This also means that the beds can be output in either clockwise or counter-clockwise order, as both directions work.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$20$ |
The subtask has a single testcase, the one on the poster (https://www.progolymp.se/2026/affisch.pdf). |
|
$2$ |
$7$ |
There are cat beds in only two colors. In other words, $K = 2$. |
|
$3$ |
$9$ |
There are exactly the same number of cat beds in each of the $K$ colors. |
|
$4$ |
$12$ |
$N \le 8$ |
|
$5$ |
$28$ |
$N \le 2000$ |
|
$6$ |
$24$ |
No additional constraints. |
Explanation of Sample 1
There are 3 pink (rosa) beds, 1 white (vit) bed, 2 yellow (gul) beds, and 4 orange beds.
One possible ordering of the beds is:
orange rosa orange gul orange rosa gul vit orange rosa
Another possible ordering is:
orange gul orange rosa gul rosa orange vit orange rosa
In both of these orders, the colors occur exactly as specified. No two adjacent beds share the same color, including the last and the first in the ring, so both placements are valid.
Outputting any of these two orders will solve the test case. There also exist other valid answers.
Explanation of Sample 2
There are 8 black (svart) beds and 2 beds in the color indigo.
There is no possible ordering of the beds that satisfies Yoh’s requirement.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 4 rosa 3 vit 1 gul 2 orange 4 |
Ja orange rosa orange gul orange rosa gul vit orange rosa |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 2 svart 8 indigo 2 |
Nej |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 5 m 2 a 2 t 1 i 1 g 1 |
Ja m a t a m i g |
