Входные данные. Выходные данные. Примеры. Примечание

Входные данные

В первой строке содержится целое число n ( 1 ≤ n ≤ 2·10 ⁹) — количество копий документа в папке у Тани.

Во второй строке содержится целое число k ( 1 ≤ k ≤ 2·10 ⁹) — количество раз, в которое уменьшает количество файлов вторая команда.

В третьей строке содержится целое число A ( 1 ≤ A ≤ 2·10 ⁹) — количество секунд, которое Миша тратит на выполнение первой команды.

В четвёртой строке содержится целое число B ( 1 ≤ B ≤ 2·10 ⁹) — количество секунд, которое Миша тратит на выполнение второй команды.

Выходные данные

Выведите единственное число — минимальное количество секунд, которое придётся потратить Мише на решение проблемы.

Примеры

входные данные	выходные данные

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

● За 3 секунды удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .

● За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.

● За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.

● За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.

Решение:Задача на динамическое программирование.

Программа на Python:

n=int(input())

k=int(input())

A=int(input())

B=int(input())

ans=0

while n>1:

if n<k or k==1:

ans=ans+(n-1)*A

n=1

elif n%k!=0:

ans=ans+(n%k)*A

n=n-n%k

else:

ans=ans+min(B, (n-n//k)*A)

n=n//k

print(ans)

Программа на С++:

#include <iostream>

#include <iomanip>

#include <string>

#include <cmath>

using namespace std;

int main () {

long long n, k, a, b;

long double sum = 0;

cin >> n >> k >> a >> b;

while (n > 1) {

if (n < k || k == 1) {

sum = sum + (a * (n - 1));

n = 1;

} else if (n % k != 0) {

sum = sum + (a * (n % k));

n = n - (n % k);

} else {

sum = sum + min(b, (n - n / k) * a);

n /= k;

}

cout << setprecision(0) << fixed << sum;

}

⇐ Предыдущая 1 23