루미 알고리즘

#1356플래티넘Tågstationer

PO 2015 결선코딩출제 Simon Lindholm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Zohan och Jimón är på väg till träningsläger i programmering. Det episka träningslägret äger rum i staden Petrozavodsk, och de har beslutat sig för att resa med tåg.

Under resans gång så sitter Jimón av någon anledning och räknar antalet personer som går av och på vid varje station som tåget stannar vid. Dessa antal skriver han upp i sin anteckningsbok – en stations data antecknas per sida.

När Jimón ska kliva av tåget så ramlar han och hans anteckningsbok slits i bitar – allt han har kvar är en hög med anteckningar huller om buller. Zohan utmanar nu Jimón att återställa ordningen i vilken stationerna uppträdde, givet siffrorna som står på sidorna som ligger på marken. Kan du hjälpa honom, eller kan du bevisa att Jimón måste ha räknat fel?

Input

På första rader står ett heltal N, antalet sidor i anteckningsblocket.

Efter det följer N rader (en per papperssida), vardera med två icke-negativa heltal: antalet personer som stiger på vid stationen, och antalet som stiger av.

En person går aldrig av på samma plats som hen går på. Det garanteras att det totala antalet påstigande och det totala antalet avstigande är samma, och att detta antal är högst 10^9. Tåget är alltid tomt när Jimón börjar räkna och tåget är alltid tomt när han har räknat klart. För enkelhets skull så antar vi att Jimón inte räknar med sig själv eller Zohan – och det är garanterat att de går på först och stiger av sist (de missar alltså inte att räkna någon).

Output

Om det är möjligt för stationerna att ordnas på så sätt att det aldrig är fler personer som stiger av än som finns på tåget, skriv ut först en rad "JA", och sedan en rad med en möjlig ordning, där varje tal 1 till N förekommer exakt en gång. I annat fall, d.v.s. om Jimón gjort något fel, skriv ut "NEJ".

Förklaring av exempel

I det första exemplet så är det totalt 12 personer som åker med tåget. Vid första stationen går det på fyra personer och går inte av någon, sedan åker tåget vidare till nästa station. Där går ytterligare 8 ombord och 2 av, nu har alltså tåget 10 personer ombord. Vid sista stationen går de sista 10 av. Detta beskrivs av ordningen 2 3 1.

I det andra exemplet så vet vi att första stationen måste antingen vara den där 2 går på eller där 3 går på. Funderar vi vidare så inser vi att dessa två måste vara först om det ska finnas någon gilting lösning, något som senare leder oss till insikten att det inte kommer att gå att skapa någon lösning utan att för många går av tåget. Notera att 2 3 4 1 inte är en giltig lösning eftersom vi då vid station fyra måste ha en person som går av vid samma station som hen går på – vilket inte är tillåtet.

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.

GruppPoängvärdeGränserÖvrigt
1202 ≤ N ≤ 8
2202 ≤ N ≤ 1000, det kommer bara finnas en station där fler går av än som går på
3302 ≤ N ≤ 1000
4302 ≤ N ≤ 60000

예제

예제 1

입력
3
0 10
4 0
8 2
출력
JA
2 3 1

예제 2

입력
4
0 10
2 0
3 0
11 6
출력
NEJ

출처 표기

출처: Programmeringsolympiaden 2015년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.