Problem A
Öar
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 värre kvar).
![\includegraphics[width=1.0\textwidth ]{oarfig}](/problems/oar/file/statement/sv/img-0001.png)
På vilken ö försvinner den sista deltagaren?
Indata
Den första raden innehåller ett heltal $1\le N \le 10\, 000$, 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. |
| Sample Input 1 | Sample Output 1 |
|---|---|
12 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
13 |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
32 |
7 |
