Fişierul intrare/ieşire:suc1.in, suc1.outSursăCerc informatică Vianu
AutorDin FolclorAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Suc1 (clasa a 8-a)

Notă: această problemă este problema suc cu limitele lui N mărite.

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 suc1.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 suc1.out veţi afişa pe prima linie un număr întreg reprezentând răspunsul problemei.

Restricţii

  • 1 ≤ N ≤ 261+1
  • 1 ≤ K ≤ 1000

Exemplu

suc1.insuc1.outExplicaţii
13 2
3
Dacă avem 13, 14, 15 sticle nu putem obţine in final una sau două sticle.
Cu 16 sticle putem obţine o singură sticlă în final.
Trebuie sa te autentifici pentru a trimite solutii. Click aici