Zadanie

Prichádza zima a každý chce byť pekne v teplúčku. Lomižaba sa pripravil: dal si na intráku namontovať zbrusu nové kachle. Teraz, spokojný sám so sebou, aké dobré kachle kúpil, si hovie v postielke, no nejako mu je stále bez periny zima.

“Ja ťuťmák!”, vyskočil Lomižaba z postele, “Zabudol som dreva nakúpiť!” Rýchlo schytil nejakého FKS-áka a dal mu vyrátať, koľko dreva potrebuje na vykúrenie svojej útulnej izbietky. “Potrebuješ \(k\) metrov.” oznámil FKS-ák po vypísaní troch traktorákov.

Kde ale teraz zoženie drevo? Lomižaba prebehol všetky obchody, no dobré drevo už bolo vykúpené! Posledný predajca si ale všimol, že Lomižaba je zo svojej situácie veľmi smutný. “Počkaj chlapče! Vidím, že junák si mi statný. Mal by som pre teba sáhovicu, no nemám žiadnu pílu.” ponúkol mu predajca. “Jasné, pílu nepotrebujem ujo, nevolám sa predsa Lomižaba len tak pre nič za nič. Mojim učiteľom Kálania Smrekových Pňov bol sám slávny Lomidrevo.” Pomôžte Lomižabovi nalámať sáhovicu.

Úloha

Dĺžka sáhovice v metroch je mocnina dvojky. Lomižaba vie ľubovoľný kus dreva zlomiť na polovicu. Lomižaba potrebuje nalámať sáhovicu na niekoľko kusov tak, aby sa spomedzi nich dali vybrať nejaké s celkovou dĺžkou presne \(k\).

Vašou úlohou je zistiť najmenší možný počet lámaní, ktoré na to potrebuje.

Formát vstupu

Na prvom riadku vstupu bude číslo \(t ~ (1 \leq t \leq 3000)\), ktoré označuje počet otázok, na ktoré máte odpovedať.

Každá otázka je zadaná na jednom riadku vstupu. Tento riadok obsahuje dve celé čísla \(n, k ~ (0 \leq n \leq 10^{18}\) a \(1 \leq k \leq 10^{18})\) oddelené medzerou. Sáhovica má \(2^n\) metrov a Lomižaba ju chce nalámať na kusy, z ktorých sa dá vyskladať sáhovica dĺžky \(k\) metrov. Vždy bude platiť \(2^n \geq k\) (sáhovica je teda dostatočne dlhá).

Formát výstupu

Pre každú otázku vypíšte na samostatný riadok jedno číslo, a to najmenší možný počet lámaní, ktorým vieme z našej sáhovice spraviť kusy také, že sa z nich dá poskladať sáhovica dĺžky \(k\).

Môžete predpokladať, že sa to vždy bude dať.

Hodnotenie

Vaše riešenia budú testované na štyroch sadách testovacích vstupov, pre ktoré platí:

Sada 1 2 3 4
Maximálne \(n\) \(3\) \(6\) \(1000\) \(10^{18}\)
Maximálne \(k\) \(8\) \(16\) \(10^6\) \(10^{18}\)

Všimnite si, že čísla \(n\) a \(k\) v \(4.\) sade presiahnu \(2^{31} - 1\), čo je najväčšie číslo, ktoré sa dá uložiť v \(32\)-bitovej premennej so znamienkom. Použite preto \(64\)-bitové premenné typu long long v C++ a Int64 v Pascale.

Príklad

Input:

3
3 8
2 3
123456789 109051904

Output:

0
2
123456766

V prvej otázke dostaneme sáhovicu rovno s dĺžkou \(8\), preto ju lámať nemusíme.

V druhej otázke už musíme lámať aspoň \(2\)-krát. Po prvom rozlomení máme \(2\) kusy po \(2 \textrm{m}\). Teraz stačí rozlomiť ešte jeden \(2\)-metrový kus. Z kusov s veľkosťami \(2, 1, 1\) môžeme vybrať \(2\)-metrový a jeden \(1\)-metrový, s celkovou dĺžkou \(3\) metre.

Úlohou bolo zo sáhovice dĺžky \(L = 2^n\) nalámať také kusy, aby sme si vedeli vyskladať kôpku, resp. sáhovicu dĺžky \(k\).

Najdôležitejším pozorovaním je fakt, že lámaním sáhovice na polovice vieme postupne dostať sáhovice všetkých dĺžok mocniny dvojky (\(1, 2, 4, 8, \ldots\)).

Potrebujeme teda číslo \(k\) vyskladať iba z mocnín dvojky. Jeden z takýchto rozkladov dostaneme, ak sa pozrieme na zápis čísla \(k\) v dvojkovej sústave. Za každú jednotku v tomto zápise vezmeme mocninu dvojky prislúchajúcu danému rádu. Napríklad ak \(k = 22\), dostaneme:

\[k = 22 = 10110_2 = 2^4 + 2^2 + 2^1 = 16 + 4 + 2 \text{.}\]

Takýto rozklad čísla na súčet mocnín dvojky má jednu peknú vlastnosť: každá mocnina dvojky sa v ňom vyskytuje nanajvýš raz. Ak by teda chcel Lomižaba nalámať sáhovicu na takéto kusy, mohol by to robiť nasledujúcim algoritmom:

  1. Ak \(k = L\), netreba nič lámať, môže skončiť.
  2. Kým nemá kus dĺžky \(1\), láme vždy najkratší kus dreva, ktorý práve má.
  3. Po skončení kroku \(1\) má po jednom kuse dreva dĺžok \(\frac{L}{2}, \frac{L}{4}, \frac{L}{8}, \dots, 8, 4, 2\) a dva kusy dĺžky \(1\). Keďže z každej mocniny dvojky má aspoň jeden kus, môže spomedzi nich vybrať tie, ktoré potrebuje.

Keďže na začiatku má najkratší (a jediný) kus dreva dĺžku \(L = 2^n\) a každým zlomením sa najkratší kus skráti na polovicu, v kroku 1. tohto algoritmu potrebuje Lomižaba \(n\) lámaní. Ak však binárny zápis čísla \(k\) končí nulami (ich počet označme \(x\)), nepotrebujeme \(x\) najmenších mocnín dvojky. V kroku 1. nášho algoritmu teda môže Lomižaba prestať lámať už v momente, keď má najkratší kus dreva dĺžku \(2^x\) (najmenšia mocnina dvojky, ktorú potrebujeme), čím ušetrí posledných \(x\) lámaní. Stačí mu teda \(n-x\) lámaní.

Nedá sa to však nejakým iným spôsobom na menej? Ukážeme, že nie. Z toho, že binárny zápis čísla \(k\) končí \(x\) nulami, vyplýva, že číslo \(k\) je deliteľné \(2^x\). Z toho, že pred týmito \(x\) nulami je už jednotka, vyplýva, že \(k\) nie je deliteľné \(2^{x+1}\). Z mocnín dvojky (ostro) väčších ako \(2^x\) sa dajú vyskladať iba násobky čísla \(2^{x+1}\), keďže všetky tieto mocininy sú násobkami \(2^{x+1}\). Na vyskladanie sáhovice dĺžky \(k\) teda nutne potrebujeme aspoň jeden kus dreva dlhý \(2^x\), alebo kratší. A na to, aby sme z kusu dĺžky \(L = 2^n\) získali kus dĺžky \(2^x\) (alebo kratší) potrebujeme aspoň \(n-x\) lámaní.

Na vyriešenie našej úlohy nám teda stačí zistiť, koľkými nulami končí binárny zápis čísla \(k\) a vypísať \(n\) mínus tento počet. Ako tento počet núl zistíme? Keď je na konci čísla v binárnom zápise nula, znemaná to, že je deliteľné \(2\). Ak sú tamm dve nuly, tak je deliteľné \(4\). Vo všeobecnosti ak je tam \(x\) núl, tak dané číslo je deliteľné \(2^x\). Stačí nám teda zistiť, koľkokrát sa dá \(k\) bezo zvyšku vydeliť dvomi.

#!/usr/bin/env python3

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    # počet nepotrebných lámaní
    nelam = 0

    # kontrolujeme, či sa na poslednej pozícií binárnej
    # reprezentácie k nachádza 0
    while k % 2 == 0:
        nelam += 1
        k //= 2
    print(n - nelam)
#include<cstdio>

int main(){
    int t;
    scanf("%d ",&t);
    for(int i=0; i<t; i++){
        long long n, k;
        scanf("%lld %lld ", &n, &k);
        long long nelam = 0;
        while(k%2==0){
            nelam ++;
            k/=2;
        }
        printf("%lld\n", n-nelam);
    }
}

Keďže binárny zápis čísla \(k\)\(\lfloor \log_2(k) \rfloor + 1\) cifier (bitov), časová zložitosť jednej otázky je \(O(\log(k))\) - pretože v najhoršom prípade musíme skontrolovať \(\log_2(k)\) bitov. Pamäťová zložitosť je \(O(1)\).

Bonus pre fajnšmekrov: Existuje aj nasledujúce riešenie v \(O(1)\):

#include <bits/stdc++.h>

using namespace std;

long long n, k;
int t;

int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%lld %lld", &n, &k);
    long long mnau = k-1;
    long long ans = __lg( k ^ (k & mnau) );

    printf("%lld\n", n - ans);
  }
  return 0;
}

Toto riešenie by bolo tiež logaritmické, no procesory majú inštrukciu pre funkciu __lg (dvojkový logaritmus – konkrétne pozícia najvyššej jednotky), ktorá umožnuje vypočítať túto hodnotu v \(O(1)\). Upozornenie: funkcie s __ pred menom sú interné funkcie kompilátora, to znamená, že ich implementácia sa môže líšiť od kompilátora ku kompilátoru, a teda nie je ju moc dobré používať v kóde, ktorý bude reálne niekde bežať.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.