1. Treba začať kúriť vzorové riešenie

3
3 8
2 3
123456789 109051904

0
2
123456766

Ú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:

0. Ak \(k = L\), netreba nič lámať, môže skončiť.
1. Kým nemá kus dĺžky \(1\), láme vždy najkratší kus dreva, ktorý práve má.
2. 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\) má \(\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ť.