Salta al contenuto principale

IL GIOCO DELL'ANITRA

Allena - Menti

Un gruppo di informatici appassionati del gioco dell’oca, ma poco propensi ad affidarsi ai dadi, decide di proporne una variante esclusivamente logico-matematica.

Il nuovo gioco – come da tradizione – si disputa su un tabellone diviso in N caselle.
Ad ogni turno, un giocatore può muoversi di un certo numero (non negativo) di caselle con il vincolo che in ogni mossa ci si può muovere dello stesso numero di caselle della mossa precedente oppure di 1 casella in più oppure di una casella in meno. (Cioè se nella i-esima mossa ci si è mossi di 3 caselle, nella i+1-esima ci si può muovere di 2, 3 o 4 caselle).
Inoltre nella prima e nell’ultima mossa ci si deve muovere esattamente di 1 casella.

Il vostro scopo è, dato un tabellone di N caselle, trovare il minor numero di mosse necessarie per compiere esattamente il percorso.

Input

L’input conterrà 1 intero non negativo, il numero di caselle del tabellone.

Output

L’output deve essere il numero minimo di mosse necessarie a completare il percorso.

Esempi di test

input 1

3

output 1

3

input 2

7

output 2

5

input 3

100

output 3

19

 

Codice QR pagina corrente