루미 알고리즘

#1651골드The Cat Paradise

PO 2026 온라인 예선코딩출제 Erik Hedin영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
120The group has a single testcase, the one on the poster (https://www.progolymp.se/2026/affisch.pdf).
27There are cat beds in only two colors. In other words, K = 2.
39There are exactly the same number of cat beds in each of the K colors.
412N ≤ 8
528N ≤ 2000
624No 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.

예제

예제 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

출처 표기

출처: Programmeringsolympiaden 2026년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.