У Луки есть массив из n целых чисел a1, a2, . . . , an. K каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций:

Выбрать некоторый элемент массива ai и заменить его на число [ai2] (данная запись обозначает число ai2, округлённое вниз). Для выполнения данной операции требуется k единиц энергии.

Выбрать некоторый элемент массива ai и заменить его на число ai−1. Для выполнения данной операции требуется одна единица энергии.

Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива были равны единице (то есть a1=a2=...=an=1).

Ввод

Вывод

3

1

4

1

3

3

1

100

10

9

#include <bits/stdc++.h>   using namespace std;   #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") #pragma GCC optimize("fast-math") #pragma GCC optimize "-O3"     typedef long long ll;   #define pb push_back   ll k;   ll func(ll num){     return (num<<1); }   ll SumBit(ll num1, ll num2) {     ll res = 0, carry = 0;     res = num1^num2;     carry = (num1&num2) << 1;     while (carry) {         ll tmp = res;         res = res^carry;         carry = (tmp&carry) << 1;     }     return res; }   ll RevNum(ll n) {     return SumBit(~n, 1LL); }   ll SubNum(ll a, ll b) {     return SumBit(a, RevNum(b)); }     ll FindNeedStep(ll x){     ll l = 0, r = 1e9;     while(l + 1 < r){         ll m = (r + l) >> 1;           if(func(m) > x)             r = m;         else             l = m;     }     return l; }   ll GetCost(ll x) {     if (x == 1) {         return 0;     }     int sqr = FindNeedStep(x);       return SumBit(min(SubNum(x, sqr), k), GetCost(sqr)); }   ll CalcAns(ll n){     ll x;     cin >> x;     if(n == 1)         return GetCost(x);       return SumBit(CalcAns(n-1), GetCost(x));     }   void solve(){     ll n;     cin >> n >> k;     cout << CalcAns(n);     return; } int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);     ll t = 1;     // cin >> t;     while(t--)         solve();     return 0; }