루미 알고리즘

#1281실버Ramsan

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

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

Problem

Ole Dole Doff Kinke Lane Koff Koffe Lane, Binke Bane Ole Dole Doff Ärtan Pärtan Piff Ärtan Pärtan Paff Similimaka, Kuckelikaka Ärtan Pärtan Poff

Ramsor av detta slag har under alla tider använts av barn för att välja ut någon slumpvis, till exempel vem som ska stå då man leker kurragömma. Barnen bildar en ring, där den som “räknar” för varje ord i ramsan flyttar fingret, från ett barn till nästa, runt ringen. När ramsan tar slut får det utpekade barnet lämna ringen. Ramsan läses på nytt med början på det barn som står omedelbart efter det uträknade. Denna procedur fortsätter tills endast ett barn återstår, det utvalda.

Indata

Den första raden av innehåller de två heltalen k och n (2 ≤ k,n ≤ 100), antalet ord i ramsan och antalet barn i ringen. Barnen är numrerade från 1 till n åt samma håll som räkningen sker. Nummer 1 är det barn man börjar räkna på.

Utdata

Skriv ut ett heltal: numret på det barn som blir sist kvar.

Förklaring av exempelfall

I exempelfall 1 pekar barn 1 på följande barn i ordning: 1, 2, 3, 1. Barn 1 åker därmed ut. Eftersom barn 2 är näst på led räknar den upp 2, 3, 2, 3. Då lämnar barn 3 och barn 2 är det sista barnet kvar.

I exempelfall 2 är det första barnet som åker ut nummer 7 och därefter nummer 15, 8 och 2.

예제

예제 1

입력
4 3
출력
2

예제 2

입력
24 17
출력
3

출처 표기

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