Fișierul intrare/ieșire | suc1.in, suc1.out | Sursă | Cerc informatică Vianu |
---|---|---|---|
Autor | din folclor | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.in | suc1.out | Explicaț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. |