Fișierul intrare/ieșire suc.in, suc.out Sursă ad-hoc
Autor din folclor Adăugată de avatar mathboy Dragos Alin Rotaru mathboy
Timp de execuție pe test 0.3 sec Limită de memorie 8096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Suc

Gigel are N sticle cu capacitate nelimitată. Inițial toate sticlele conțin 1 litru de suc. El dorește să transporte toate sticlele acasă pentru a da o petrecere. Din păcate, el nu poate căra mai mult de K sticle așa că se hotărăște să redistribuie conținutul sticlelor până când rămâne cu cel mult K sticle nevide (care conțin cel puțin 1 litru de suc).

Gigel nu poate să redistribuie conținutul sticlelor decât în felul următor:
Pasul 1: Alege 2 sticle care conțin aceeași cantitate de suc.
Pasul 2: Toarnă tot sucul dintr-o sticlă în cealaltă sticlă.

Din cauza restricției următoare poate fi uneori imposibil să ajungă la K sticle nevide. Din fericire, el poate cumpăra mai multe sticle. Fiecare sticlă pe care o cumpără Gigel conține 1 litru de suc și capacitate nelimitată. Spre exemplu, să luăm cazul când N = 3, K = 1. E imposibil să reducem 3 sticle la 1 sticlă. Dacă turnăm o sticlă în alta, vom ajunge cu 2 sticle, una de 2 litri și una de 1 litru. În acest moment ne-am blocat. Însă dacă Gigel cumpără încă o sticlă, putem răsturna sticla de 1 litru în cea cumpărată și obținem 2 sticle de 2 litri ca mai apoi să avem doar una care conține 4 litri.

Gigel vrea să își cumpere bomboane și vă întreabă pe voi care este numărul minim de sticle cumpărate pentru a obține în final cel mult K sticle de suc nevide.

Date de intrare

Fișierul de intrare suc.in conține pe prima linie 2 numere naturale N, K separate printr-un spațiu.

Date de ieșire

În fișierul de ieșire suc.out veți afișa pe prima linie un număr întreg reprezentând răspunsul problemei.

Restricții

  • 1 ≤ N ≤ 107
  • 1 ≤ K ≤ 1000

Exemplu

suc.in suc.out
13 2
3

Explicație

Daca avem 13, 14, 15 sticle nu putem obtine in final una sau doua sticle. Cu 16 sticle putem obtine o singura sticla in final.

Trebuie să te autentifici pentru a trimite soluții. Click aici