Problem A
Kattparadiset
Languages
en
sv
När katter vill sova förtjänar de världens mysigaste bäddar.
Yoh är volontärarbetare på katthemmet Kattparadiset som tar hand om katter innan de får ett permanent hem. Katthemmet har fått in $N$ nya kattsängar i $K$ olika färger. Yoh vill placera ut kattsängarna i en ring, så att två intilliggande kattsängar aldrig har samma färg. Yoh tänker att det kommer få varje katt att känna sig extra speciell, unik och omhändertagen.
Hjälp Yoh att placera ut kattsängarna, eller avgör att det inte är möjligt att placera ut dem som Yoh vill.
Indata
Den första raden innehåller två heltal $N$ och $K$ $(3 \le N \le 2 \cdot 10^5, 2 \le K \le N)$, antalet kattsängar och antalet färger på dem.
Sedan följer $K$ rader, en för varje färg. På vardera av de $K$ raderna kommer först en sträng $s$ som beskriver namnet på färgen, samt ett heltal $c$ ($1 \leq c \leq N$), antalet kattsängar av färg $s$.
Summan av antalet sängar av vardera färg är garanterat att vara exakt $N$. Alla färger har unika namn, och namnen består av upp till 6 bokstäver bland bokstäverna a-z.
Utdata
Om det inte är möjligt att placera kattsängarna som Yoh vill, skriv ut ”Nej”.
Annars, skriv ut en rad med ordet ”Ja”, följt av en ny rad med färgerna av de $N$ kattsängarna i samma ordning som de är utplacerade utmed ringen. Om det finns flera lösningar kan du skriva ut vilken som helst. Notera att eftersom placeringen är cirkulär så spelar det ingen roll vart du start i ringen. Detta innebär också att sängarna kan skrivas ut antingen medurs eller moturs, eftersom båda riktningarna funkar.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$20$ |
Gruppen består av ett enda testfall, det som finns på affischen (https://www.progolymp.se/2026/affisch.pdf). |
|
$2$ |
$7$ |
Det finns bara kattsängar i två färger. Med andra ord, $K = 2$. |
|
$3$ |
$9$ |
Det finns exakt lika många kattsängar i vardera av de $K$ färgerna. |
|
$4$ |
$12$ |
$N \le 8$ |
|
$5$ |
$28$ |
$N \le 2000$ |
|
$6$ |
$24$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall 1
Det finns 3 rosa sängar, 1 vit säng, 2 gula sängar och 5 orangea sängar.
En möjlig ordning av sängarna är:
orange rosa orange gul orange rosa gul vit orange rosa
En annan möjlig ordning är:
orange gul orange rosa gul rosa orange vit orange rosa
I båda dessa ordningar förekommer färgerna exakt så många gånger som angivits. Två intilliggande sängar har aldrig samma färg, inte heller mellan den sista och den första i ringen, så båda placeringarna är giltiga.
Oavsett vilken av dessa två ordningar man anger får man rätt svar på testfallet. Det finns även fler giltiga ordningar, och dessa funkar självklart också.
Förklaring av exempelfall 2
Det finns 8 svarta sängar och 2 sängar i färgen indigo.
Det finns inga möjliga ordningar av sängarna som uppfyller Yohs krav.
| 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 |
