![]()
|
||||||||||
Входные данные. Выходные данные. Примеры. Примечание ⇐ ПредыдущаяСтр 3 из 3 Входные данные В первой строке содержится целое число n ( 1 ≤ n ≤ 2·10 9 ) — количество копий документа в папке у Тани. Во второй строке содержится целое число k ( 1 ≤ k ≤ 2·10 9 ) — количество раз, в которое уменьшает количество файлов вторая команда. В третьей строке содержится целое число A ( 1 ≤ A ≤ 2·10 9 ) — количество секунд, которое Миша тратит на выполнение первой команды. В четвёртой строке содержится целое число B ( 1 ≤ B ≤ 2·10 9 ) — количество секунд, которое Миша тратит на выполнение второй команды. Выходные данные Выведите единственное число — минимальное количество секунд, которое придётся потратить Мише на решение проблемы. Примеры
Примечание В первом тестовом примере оптимальная стратегия Миши такова: ● За 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; }
|
||||||||||
|