Question

Вася учится в 10 классе тридевятой школы и мечтает победить в турнире <Экспонента>. Этот турнир проводится ежегодно в апреле. Участвовать в нём могут школьники и студенты. Вася понимает, что пока ещё недостаточно подготовлен для победы, но готов упорно тренироваться. Он нашёл в Интернете N задач, для каждой из которых известна её полезность. Полезность задачи равна количеству наномитричей, на которое её решение увеличивает силу программиста. К сожалению, Вася не может всё своё время посвятить тренировкам (причины этого вам хорошо известны), так что за оставшиеся до турнира дни он успеет решить только K задач. Напишите программу, которая по заданным N, K и полезностям задач в наномитричах Mi, i = 1, ..., N вычисляет силу, которую успеет набрать Вася к турниру <Экспонента>. Исходная сила Васи равна одному наномитричу. Вход В первой строке входного файла записаны два целых числа N и K (0 <= N, K <= 10^5). Во второй строке файла записаны N целых чисел - полезности задач M(1), ..., M(N) (0 <= M(i) <= 10^8). Выход Запишите в выходной файл наибольшую силу в наномитричах, которую Вася успеет набрать до турнира <Экспонента>. Гарантируется, что результат не превысит 1 митрича. Замечание Единица программистской силы наномитрич равна 10^-9 митрича. Один митрич равен силе знаменитого программиста Петра Митричева.

Answer 1

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 3;

int m[N];

int main()
{
    int n, k;
    cin >> n >> k;
   
    k = min(k, n);
   
     for (int i = 0; i < n; ++i)
        cin >> m[i];
       
    sort(m, m + n);
    reverse(m, m + n);
   
    int ans = 1;
    for (int i = 0; i < k; ++i)
        ans += m[i];
       
    cout << ans << endl;
   
    return 0;
}

Answer 2

Для решения этой задачи, вы можете воспользоваться жадным методом. Начнем сортировать задачи по убыванию полезности и будем решать их по порядку, выбирая задачи с наибольшей полезностью до тех пор, пока у Васи не закончатся попытки (K задач). После каждого решения задачи добавим её полезность к силе Васи. В конце, умножим силу на 10^-9, чтобы получить результат в наномитричах.

Вот пример программы на Python, решающей эту задачу:

pythonCopy code
# Считываем входные данные
N, K = map(int, input().split())
usefulness = list(map(int, input().split()))

# Сортируем задачи по убыванию полезности
usefulness.sort(reverse=True)

# Начальная сила Васи
vasya_power = 1  # 1 наномитрич

# Решаем задачи
for i in range(K):
    vasya_power += usefulness[i]

# Преобразуем силу в результат в наномитричах
result = vasya_power * 10**-9

# Выводим результат
print(result)

Вы можете использовать этот код, чтобы решить задачу. Просто скопируйте его в файл и запустите, предоставив необходимые входные данные. Результат будет выведен на экран.