Задача 6611. Источник: Поляков. Задание КИМ 26
(Д. Козлов) В одной волшебной местности живут гномы, которые любят варить зелья в магических котлах. Всего есть P котлов, они пронумерованы, в начальный момент все они свободны. Гномы варят зелья в порядке общей очереди. Первый в очереди гном, желающий сварить зелье, подходит к свободному котлу с наименьшим номером. Если котел ранее не использовался, гном может начать варить зелье сразу, а если уже использовался – только через две минуты после того, как он подошел к такому котлу. Одна порция зелья варится 1 минуту.
На заварку одной порции зелья гном тратит две единицы маны (магической энергии для заварки зелий). Если в один момент подошли несколько гномов, то варить зелье идёт тот, у кого запас маны меньше. Гном будет варить зелья, пока у него достаточно маны для их заварки. Гном, у которого осталось меньше двух единиц маны, не может сварить зелье и уходит.
Известно время в минутах от начала суток, когда каждый гном подошёл к котлам, и количество маны у гнома. Определите, сколько порций зелья сварят гномы за сутки, и какое наибольшее количество порция зелья смог сварить один гном.
Входные данные представлены в файле 26-125.txt следующим образом. Первая строка входного файла содержит два натуральных числа: D – количество гномов (1 ≤ D ≤ 100000) и P – количество котлов (1 ≤ P ≤ 1000). В каждой из последующих D строк содержится информация по одному гному: время подхода гнома к котлам (в минутах с начала суток) и количество имеющейся у него маны.
В ответе запишите два числа: количество порций зелья, сваренных гномами за сутки, и наибольшее количество порций зелья, которое смог сварить один гном.
Пример входного файла:
5 2
1 6
4 9
3 1
4 5
9 11
При таких исходных данных за сутки было сварено 14 порций зелья. Наибольшее количество порций (5) было сварено гномом с количеством маны 11. Гном с количеством маны 1 сразу же уходит, т. к. у него недостаточно маны для заварки хотя бы одной порции зелья. Ответ: 14 5.
Решение
Вероятно, в данной задаче не совсем корректно сформулировано условие, т.к. приведенный ответ получается, если предположить, что при отсутствии свободного котла гном уходит, а не стоит в очереди. Решение основано на имеющемся ответе и данном предположении.
Сортируем исходные данные по возрастанию времени подхода, а при равенстве времени, по количеству маны. Создаем массив/список pots, где будет содержаться информация о времени освобождения каждого котла. Последовательно обрабатываем гномов и ищем котел с наименьшим временем освобождения. Если у гнома нет маны или нет свободного котла, пропускаем его. Определяем количество зелий, которые может приготовить робот. Обязательно учитываем, что гном не может приготовить больше зелий, чем осталось времени до конца суток (1440 минут). В соответствии с полученными данными, меняем время освобождения котла, общее количество сваренных зелий total и максимального количества зелий, сваренных одним гномом max (mx).
Python
f = open('26-125.txt')
d, p = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
pots = [0] * p
total = 0
mx = 0
for i in a:
k = i[1] // 2
if k > 0:
pot = 0
for j in range(1, p):
if pots[j] < pots[pot]:
pot = j
if pots[pot] > i[0]:
continue
if pots[pot] == 0:
pots[pot] = i[0] + k
else:
k = min(k, 1440 - 2 - i[0])
pots[pot] = i[0] + k + 2
total += k
mx = max(mx, k)
print(total, mx)
PascalABC
var
d, p, total, max, pot, k, i, j, min, t: Integer;
a: array [1..1700, 1..2] of Integer;
pots: array [1..20] of Integer;
f: TEXT;
begin
Assign(f, '26-125.txt');
Reset(f);
Readln(f, d, p);
for i := 1 to d do
Readln(f, a[i, 1], a[i, 2]);
for i := 1 to d - 1 do
begin
min := i;
for j := i + 1 to d do
if (a[j, 1] < a[min, 1]) or (a[j, 1] = a[min, 1]) and (a[j, 2] < a[min, 2]) then
min := j;
if min <> i then
begin
t := a[i, 1];
a[i, 1] := a[min, 1];
a[min, 1] := t;
t := a[i, 2];
a[i, 2] := a[min, 2];
a[min, 2] := t;
end;
end;
for i := 1 to p do
pots[i] := 0;
total := 0;
max := 0;
for i := 1 to d do
begin
k := a[i, 2] div 2;
if k > 0 then
begin
pot := 1;
for j := 2 to p do
if pots[j] < pots[pot] then
pot := j;
if pots[pot] > a[i, 1] then
continue;
if pots[pot] = 0 then
pots[pot] := a[i, 1] + k
else
begin
if k > 1440 - 2 - a[i, 1] then
k := 1440 - 2 - a[i, 1];
pots[pot] := a[i, 1] + k + 2;
end;
total := total + k;
if k > max then
max := k;
end;
end;
Writeln(total, ' ', max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-125.txt");
int d, p;
f >> d >> p;
int a[1700][2];
for (int i = 0; i < d; i++)
f >> a[i][0] >> a[i][1];
for (int i = 0; i < d - 1; i++)
{
int min = i;
for (int j = i + 1; j < d; j++)
if (a[j][0] < a[min][0] || a[j][0] == a[min][0] && a[j][1] < a[min][1])
min = j;
if (min != i)
{
int t = a[i][0];
a[i][0] = a[min][0];
a[min][0] = t;
t = a[i][1];
a[i][1] = a[min][1];
a[min][1] = t;
}
}
int pots[20];
for (int i = 0; i < p; i++)
pots[i] = 0;
int total = 0, max = 0;
for (int i = 0; i < d; i++)
{
int k = a[i][1] / 2;
if (k > 0)
{
int pot = 0;
for (int j = 1; j < p; j++)
if (pots[j] < pots[pot])
pot = j;
if (pots[pot] > a[i][0])
continue;
if (pots[pot] == 0)
pots[pot] = a[i][0] + k;
else
{
if (k > 1440 - 2 - a[i][0])
k = 1440 - 2 - a[i][0];
pots[pot] = a[i][0] + k + 2;
}
total += k;
if (k > max)
max = k;
}
}
cout << total << " " << max << endl;
}
Ответ
27994 245