Road to top 50 V-N-U-S-E-R-S


2022-01-01 02:00 AKST

Road to top 50 V-N-U-S-E-R-S


2022-01-05 06:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -141 days 15:47:45

Time elapsed


Time remaining


Problem J

A new type of chocolate arrived in the local shop. The chocolate comes in bars, each bar consisting of $N$ squares. Bars are factory made and only come in sizes which are full powers of two. In other words a single bar has $1, 2, 4, 8, 16, \dots $ squares.

To fully asses the quality of chocolate Mirko must sample at least $K$ squares. His friend Slavko would also like to try some of the chocolate. Since Mirko is in a hurry to try the chocolate himself, he decides to break the bar he bought in pieces, such that he has exactly $K$ squares, and leaves the rest (if any) to Slavko. The bars are a bit brittle, so Mirko can break them only on their exact center. In other words, from one bar with $D$ squares, he can get two bars with $D/2$ squares.

Write a program that will determine the minimal number of breaks Mirko must perform in order to obtain exactly $K$ squares (not necessarily in one piece). Also, determine the smallest bar size Mirko must buy in order to have at least $K$ squares.


The first and only line of input will contain one integer $K$ $(1 \leq K \leq 1\, 000\, 000)$, number of squares Mirko must sample.


The first and only line of output should contain two integers, separated by a single space. The first integer is the smallest bar size Mirko must buy. The second the smallest number of breaks.

Sample Input 1 Sample Output 1
8 2
Sample Input 2 Sample Output 2
8 3
Sample Input 3 Sample Output 3
8 3