루미 알고리즘

#1502실버Öar

PO 2020 학교 예선코딩출제 Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

2020 års International Olympiad in Informatics (IOI) kommer att avgöras i Singapore, ett till ytan litet land som består av massor av öar. På en av utflykterna på IOI ska de N deltagarna besöka dessa öar. Men deltagarna går och tänker på hur de ska implementera Fibonacci-heapar, så en efter en går vilse och hittar inte tillbaka.

På första ön försvinner en deltagare, på andra ön försvinner ytterligare en deltagare. Om a_i är antalet deltagare som försvinner på ö i, så försvinner a_{k-2} + a_{k-1} från ö k (eller antalet kvarvarande deltagare, om det är färre kvar).

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

Figur 1: Figuren visar situationen i det första exemplet när den sista (tolfte) deltagaren försvunnit på ö nummer 5.

På vilken ö försvinner den sista deltagaren?

Indata

Den första raden innehåller ett heltal 1 ≤ N ≤ 10000, antalet deltagare.

Utdata

Ett heltal A, numret på ön där den N:te deltagaren försvinner.

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.

FallPoängvärdeGränser
140Exakt a_k deltagare försvinner från den sista ön.
260Inga ytterligare begränsningar.

예제

예제 1

입력
12
출력
5

예제 2

입력
13
출력
6

예제 3

입력
32
출력
7

출처 표기

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