스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Fall | Poängvärde | Gränser |
| 1 | 40 | Exakt a_k deltagare försvinner från den sista ön. |
| 2 | 60 | Inga ytterligare begränsningar. |
예제
예제 1
12
5
예제 2
13
6
예제 3
32
7