영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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 ≤ N ≤ 2 · 10^5, 2 ≤ K ≤ 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 ≤ c ≤ 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 “Nej”.
Otherwise, print a line with the word “Ja”, 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. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | The group 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 ≤ 8 |
| 5 | 28 | N ≤ 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 rosaAnother possible ordering is:
orange gul orange rosa gul rosa orange vit orange rosaIn 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.
예제
예제 1
10 4 rosa 3 vit 1 gul 2 orange 4
Ja orange rosa orange gul orange rosa gul vit orange rosa
예제 2
10 2 svart 8 indigo 2
Nej
예제 3
7 5 m 2 a 2 t 1 i 1 g 1
Ja m a t a m i g