P135SUMD - SUM5 D - Thanh socola

Người Gửi: Sai

  • Problem:

Tí và Tèo thèm ăn socola, vì vậy hai bạn cùng rủ nhau ra tiệm để mua. Các thanh socola gồm N miếng socola nhỏ. Tuy nhiên, ở cửa hàng chỉ còn lại các thanh có số lượng miếng socola nhỏ là bội số của 2, tức là số lượng miếng socola nhỏ sẽ là 1, 2, 4, 8, 16, ...  
Trong hai người thì Tí là thằng tham ăn, vì vậy Tí góp nhiều tiền hơn và cũng muốn ăn nhiều hơn. Tí muốn ăn K miếng socola, còn Tèo thì thế nào cũng được. Vì vậy Tèo tính toán mua một thanh socola kích thước nhỏ nhất có thể, sau đó bẻ lần lượt nó ra làm hai để có thể đưa cho Tí K miếng socola, còn phần còn lại sẽ là của mình.  
Các bạn hãy giúp Tèo tính toán xem cần mua thanh socola có kích thước bao nhiêu, và số lần bẻ các thanh socola là bao nhiêu? Biết rằng một thanh socola có D miếng sẽ được bẻ thành 2 thanh có số lượng D/2 miếng.

Input

Số nguyên K duy nhất (1 ≤ K ≤ 1 000 000) là số lượng socola mà Tí muốn có.
Output
In ra 2 số nguyên. Số thứ nhất là kích thước thanh socola nhỏ nhất mà hai người cần mua. Số thứ hai là số tối thiểu cần bẻ thanh socola đó.
Example:
Input
6
Output:
8 2

Input
7
Output:
8 3
Input
5
Output:
8 3
  • Solution:

- Phải tính được số socola tối thiểu: bằng cách tính s là lũy thừa của 2, sao cho s nhỏ nhất >=k; - Trường hợp mà s==k thì tèo cho tí hết luôn. - Trường hợp s>k thì sẽ bắt đầu chia theo đề bài: + Lặp cho đến khi số thanh socola == k (slt), mỗi lần bẻ là ++ (slb++) + Nếu phần còn lại (D) ==1 mà vẫn chưa đủ số thanh socola thì sẽ tiếp tục tăng s*=2 và lặp lại như trường hợp s>k;

  • Code:

C++:



JAVA:


Share this

Related Posts

Previous
Next Post »