Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Patyczek (patyczek) Memory limit: 32 MB Time limit: 1.00 s Jasio ma patyczek długości 2N. Chciałby uzyskać patyczek długości K. Może w tym celu wykonywać następujące operacje: podzielić patyczek na dwie równe części (o ile wybrany patyczek jest parzystej długości), skleić dwa patyczki w jeden (o długości będącej sumą długości sklejanych patyczków). Napisz program, który: wczyta wartości N oraz K, wyznaczy minimalną liczbę operacji, które należy wykonać, żeby uzyskać patyczek długości K z patyczka długości 2N i wypisze wynik na standardowe wyjście. Wejście W pierwszym (jedynym) wierszu wejścia znajdują się dwie nieujemne liczby całkowite: N oraz K, oddzielone pojedynczym odstępem. Wyjście W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalną liczbę operacji niezbędnych do uzyskania patyczka długości K z patyczka długości 2N. Ograniczenia 0 ≤ N ≤ 60, 1 ≤ K ≤ min (2N,1018). Przykład Input Output Explanation 3 3 4 Patyczek Jasia ma długość 23 = 8. Najpierw Jasio dzieli patyczek długości 8 na dwa patyczki długości 4. Potem dzieli jeden z uzyskanych patyczków na dwa o długości 2. Potem dzieli jeden z uzyskanych patyczków długości 2 na dwa patyczki długości 1. Na końcu wystarczy skleić patyczek długości 2 z patyczkiem długości 1.

Input	Output	Explanation
`3 3`	`4`	Patyczek Jasia ma długość 2³ = 8. Najpierw Jasio dzieli patyczek długości 8 na dwa patyczki długości 4. Potem dzieli jeden z uzyskanych patyczków na dwa o długości 2. Potem dzieli jeden z uzyskanych patyczków długości 2 na dwa patyczki długości 1. Na końcu wystarczy skleić patyczek długości 2 z patyczkiem długości 1.