Решение задачи Джонни и древний компьютер с Codeforces

Без пояснения   Просмотров: 1061

Недавно Джонни обнаружил древний сломанный компьютер. У него есть только один регистр, в который можно записать некоторое значение. После чего, за одну операцию вы можете применить к значению битовый сдвиг влево или вправо на не более чем три позиции. Сдвиг вправо запрещен, если в результате будут потеряны единичные биты. Так что, на самом деле, за одну операцию вы можете умножить или разделить значение на 2, 4 или 8, и деление разрешено только если значение делится нацело на выбранный делитель.

Формально, если регистр содержит целое положительное число x, за одну операцию оно может быть заменено одним из следующих:

x⋅2
x⋅4
x⋅8
x/2, если x делится на 2
x/4, если x делится на 4
x/8, если x делится на 8
Например, если x=6, за одну операцию оно может быть заменено на 12, 24, 48 или 3. Значение 6 не делится на 4 или 8, поэтому существуют только четыре варианта замены.

Теперь Джонни интересуется, какое минимальное количество операций необходимо, если он запишет в регистр значение a и в конце хочет получить там значение b.

Код 

#include <bits/stdc++.h>

using namespace std;
void solve()
{
    long long n, m, k = 0;
    cin >> n >> m;
    if(n == m){
        cout << 0 << endl;
        return;
    }

    if(n < m)
        swap(n, m);
    if(m == 1 && n % 2){
        cout << -1 << endl;
        return;
    }
    while(n > m && n % 2 == 0){
        n /= 2;
        ++k;
    }
    if(n == m){
        long long res = k / 3; k %= 3;
        res += k / 2; k %= 2;
        res += k;
        cout << res << endl;
    }
    else
        cout << -1 << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp