У Луки есть массив из n целых чисел a1, a2, . . . , an. K каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций:
Выбрать некоторый элемент массива ai и заменить его на число [ai2] (данная запись обозначает число ai2, округлённое вниз). Для выполнения данной операции требуется k единиц энергии.
Выбрать некоторый элемент массива ai и заменить его на число ai−1. Для выполнения данной операции требуется одна единица энергии.
Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива были равны единице (то есть a1=a2=…=an=1).
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤5⋅104) — количество элементов массива.
Вторая строка содержит одно целое число k (1≤k≤105) — количество энергии, необходимое для выполнения операции первого типа.
Каждая из следующих n строк содержит одно целое число ai (1≤ai≤109) — элементы массива.
Обратите внимание, что ответ может быть достаточно большим, поэтому следует использовать 64-битный тип данных, например, long long в C/C++, long в Java, int64 в Pascal.
Формат выходных данных
Выведите одно целое число — минимальное количество энергии, необходимое для требуемого преобразования массива.
Система оценки
Решения, правильно работающие только для случаев, когда k=1, будут оцениваться в 25 баллов.
Решения, правильно работающие только для случаев, когда все ai не превосходят 105, будут оцениваться в 50 баллов.
Пояснение
Рассмотрим первый пример из условия.
Первый элемент массива равен 4. Использовав одну единицу энергии, применим к нему первую магическую операцию, после чего первый элемент массива станет равен [42]=2. После этого применим к нему вторую операцию, также затратив одну единицу энергии.
Второй элемент массива уже равен 1, поэтому применять к нему операции не нужно.
К третьему элементу применим первую операцию, используя одну единицу энергии. После этого третий элемент станет равен [32]=1.
Во втором примере из условия применение первой операции расходует слишком много единиц энергии, поэтому выгодно применить вторую операцию девять раз.
1 Ответ
Ответ:
#include <bits/stdc++.h>
using namespace std;
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;
}