Monopol6

Cerință

O tablă de Monopol de latură $n$ este formată din căsuțele de pe marginea unui pătrat de latură $n$:

Pe căsuța din colțul din stânga-sus a tablei de Monopol se află un robot care are inițial $b$ unități de curent în bateria sa.

În fiecare secundă, robotul poate face una dintre următoarele două acțiuni:

1. Robotul va sta pe loc, iar bateria sa se va încărca cu o unitate de curent.
2. Dacă bateria robotului are $x \ge 1$ unități de curent, atunci robotul va avansa pe tablă cu $x$ căsuțe, iar bateria lui se va descărca cu o unitate.

Dacă $c=1$, afișați numărul de ture complete pe care le va face robotul dacă nu își poate încarca bateria.

Dacă $c=2$, afișați numărul minim de secunde de care are nevoie robotul pentru a face o tură completă.

Robotul efectuează o tură completă de fiecare dată când vizitează (inclusiv în trecere) căsuța din colțul din stânga-sus a tablei.

Date de intrare

Pe prima linie a fișierului de intrare monopol.in se va afla numărul cerinței $c$.

Pe a doua linie se vor afla două numere $n$ și $b$ - dimensiunea tablei de Monopol, respectiv numărul de unități de curent aflate inițial în bateria robotului.

Date de ieșire

Dacă $c=1$, atunci fișierul de ieșire monopol.out va conține numărul de ture complete pe care le va face robotul dacă nu își poate încarca bateria.

Dacă $c=2$, atunci fișierul de ieșire monopol.out va conține numărul minim de secunde de care are nevoie robotul pentru a face o tură completă.

Restricții și precizări

• $1 \le c \le 2$;
• $2 \le n \le 10^{12}$;
• $0 \le b \le 10^9$;
• Pentru $15$ puncte, $c=1$ și $b \le 10^6$;
• Pentru încă $15$ puncte, $c=1$;
• Pentru $15$ puncte, $c=2$ și $n \le 1 \ 000$;
• Pentru încă $20$ de puncte, $c=2$ și $n \le 10 \ 000$;
• Pentru încă $20$ de puncte, $c=2$ și $n \le 10^6$;
• Pentru încă $15$ puncte, $c=2$.

Exemplul 1

monopol.in

1
2 2

monopol.out

0

Explicație

Robotul nu va face nicio tură completă:

Exemplul 2

monopol.in

1
4 5

monopol.out

1

Explicație

Robotul va face o singură tură completă:

Exemplul 3

monopol.in

1
4 8

monopol.out

3

Explicație

Robotul se va mișca în față cu $8+7+\ldots+1=36$ căsuțe.

Deoarece o tablă de latură $n=4$ are $12$ căsuțe, robotul va face $\frac{36}{12}=3$ ture complete.

Exemplul 4

monopol.in

2
5 6

monopol.out

4

Explicație

În prima secundă, robotul va înainta cu $6$ căsuțe, iar bateria sa se va descărca cu o unitate.

În a doua secundă, robotul își va încărca bateria.

În a treia secundă, robotul va înainta cu $6$ căsuțe, iar bateria sa se va descărca cu o unitate.

În a patra secundă, robotul va înainta cu $5$ căsuțe, iar bateria sa se va descărca cu o unitate.

Exemplul 5

monopol.in

2
2 2

monopol.out

3

Explicație

În prima secundă, robotul își va încărca bateria cu o unitate.

În a doua secundă, robotul va înainta cu $3$ căsuțe, iar bateria sa se va descărca cu o unitate.

În a treia secundă, robotul va înainta cu $2$ căsuțe, iar bateria sa se va descărca cu o unitate.

Exemplul 6

monopol.in

2
7 0

monopol.out

12

Exemplul 7

monopol.in

2
1000000 0

monopol.out

4899

Exemplul 8

monopol.in

2
1000000000000 0

monopol.out

4898979