Fișierul intrare/ieșire suc1.in, suc1.out Sursă Cerc informatică Vianu
Autor din folclor Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

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

Indicii de rezolvare

Arată 2 categorii