루미 알고리즘

#1411실버Kulramen

PO 2016 학교 예선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Så här kunde Simons kulram (med R=4) se ut innan han började äta upp kulorna. Då var det lätt att översätta ställningen till ett decimaltal.

Lille Simon har fått en kulram i present. Kulramen har R rader och i varje rad fanns från början 9 kulor, så att man kunde representera R-siffriga decimaltal – en siffra på varje rad. Om en rad hade X kulor på vänstra sidan, sedan ett mellanrum och övriga kulor på höger sida representerade raden siffran X.

Tyvärr tyckte Simon att kulorna på ramen såg väldigt smaskiga ut, och åt helt enkelt upp några kulor. Det finns dock minst en kula kvar på varje rad.

Simon lärde sig snabbt att räkna på sin nya kulram. Han representerar talet där alla kulor är på högersidan som talet 0, och adderar sedan 1 precis som han hade gjort på en vanlig kulram, genom att flytta en kula från höger till vänster på den nedersta raden som har någon kula kvar på höger sida (låt oss kalla den flyttningsraden) samt flytta alla kulor på raderna nedanför flyttningsraden till höger sida (om inte flyttningsraden är den nedersta raden). Om 1 adderas när alla kulorna på alla rader redan är på vänster sida (så att det inte finns någon flyttningsrad) blir resultatet 0.

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 2: Några exempel på hur Simon adderar 1 på den kulram som återfinns i de två första exemplen. Dubbelpilen markerar “flyttningsraden” vid de olika additionerna.

Simon håller på att räkna sandkornen i sin sandlåda och skulle behöva hjälp att skriva ett program som, givet ett visst utgångsläge på kulramen, räknar ut hur kulramen ser ut när han N gånger har adderat 1.

Indata

På första raden står antalet rader R. Därefter följer R rader med vardera två heltal, antalet kulor till vänster respektive höger på varje rad (uppifrån och ned). Slutligen finns en rad med det positiva heltalet N.

Utdata

Programmet ska skriva ut R rader med två tal på varje rad: antalet kulor till vänster respektive höger på varje rad efter additionerna.

Poängsättning

För testfall värda 20 poäng gäller att R=4, N ≤ 100, och det finns 2 kulor på varje rad. För testfall värda ytterligare 40 poäng gäller att R=4 och N ≤ 10,000. För testfall värda 40 poäng gäller att R ≤ 12 och N ≤ 10^12.

예제

예제 1

입력
4
0 4
0 2
1 2
0 1
6
출력
0 4
1 1
0 3
0 1

예제 2

입력
4
2 2
2 0
2 1
1 0
85
출력
1 3
1 1
1 2
0 1

예제 3

입력
4
1 1
0 2
2 0
1 1
37
출력
2 0
1 1
2 0
2 0

예제 4

입력
10
4 5
7 2
8 0
6 3
3 5
4 4
1 8
0 9
7 1
2 6
9876543210
출력
1 8
5 4
1 7
9 0
7 1
1 7
4 5
3 6
0 8
2 6

출처 표기

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