Задача 6667. Источник: Поляков. Задание КИМ 26
(Е. Джобс) В волшебной стране живут гномы, которые любят варить зелья в магических котлах. Они имеют очень тонкую душевную организацию и стесняются стоять рядом с кем-то за соседним котлом. Гном всегда выбирает свободный котел с наименьшим номером, рядом с которым никто не стоит. Если это невозможно, но свободные котлы есть, гном выбирает свободный котел с наименьшим номером. Гном варит свою порцию зелья 6 минут, после чего уходит с поляны. В котле, который он освободил, другой гном сразу же может варить своё зелье.
Определите минимальное количество котлов, которых достаточно для того, чтобы каждый желающий гном сварил зелье, и количество гномов, которые не испытают неудобств, связанных с близким соседством при найденном количестве котлов. Считается, что гном испытывает неудобства, если при варке зелья стоит плечом к плечу с соседом хотя бы 1 минуту.
Входные данные представлены в файле 26-127.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) – количество гномов, желающих сварить зелье. В каждой из следующих N строк записано время в минутах от начала суток, когда гном подошел к поляне с котлами – натуральное число, не превышающее 1433. Строки в файле (кроме первой) расположены в случайном порядке.
В ответе запишите два числа: минимальное количество котлов, которых достаточно для того, чтобы каждый желающий гном сварил зелье, и количество гномов, которые не испытают неудобств, связанных с близким соседством при найденном количестве котлов.
Пример входного файла:
6
6
8
10
14
20
22
При таких исходных данных необходимо 3 котла. Зелье без неудобств смогут сварить два гнома, пришедших через 20 и 22 минуты после полуночи. Распределение котлов: 1 котёл: 6-12, 14-20, 20-26; 2 котёл: 10-16; 3 котёл: 8-14, 22-28. Ответ: 3 2.
Решение
Считываем данные в массив/список и сортируем в порядке возрастания. Создадим массив/список/вектор busy, где будем хранить информацию о времени освобождения занятых котлов. Перед обработкой информации об очередном гноме удаляем из этого списка все записи об освободившихся котлах, т.е. время освобождения которых меньше или равно времени визита обрабатываемого гнома. После этого добавляем информацию о времени освобождения очередного котла. Максимальный размер busy будет минимальным количеством необходимых котлов.
Для получения числа гномов, сваривших зелье в комфорте, создадим массив/список pots с количеством элементов на два больше, чем найденное минимальное количество (слева первого котла и справа последнего будут "виртуальные" котлы для упрощения кода). Каждая запись будет содержать время освобождения данного котла и флаговое значение, варил ли гном это зелье в комфорте. Организуем цикл по количеству минут, когда варились все зелья. В этом цикле находим котлы, которые освободились в данную минуту и, если флаг комфорта сохранился, увеличиваем счетчик. После этого для каждого гнома, начавшего варить зелье в эту минуту ищем подходящий котел. Сначала ищем котел, у которого соседи свободны и прописываем для этого котла время освобождения и устанавливаем флаг комфорта. Если комфортного котла не нашлось, ищем первый свободный котел, прописываем ему время освобождения, а флаг комфорта сбрасываем не только у данного котла, но и у соседних котлов.
Python
f = open('26-127.txt')
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
a.sort()
maxk = 0;
busy = []
for i in a:
j = 0
while j < len(busy):
if busy[j] <= i:
del busy[j]
else:
j += 1
busy.append(i + 6)
maxk = max(maxk, len(busy))
pots = [[-1, True] for i in range(maxk + 2)]
j = 0
k = 0
for i in range(a[n - 1] + 7):
for m in range(1, maxk + 1):
if pots[m][0] == i and pots[m][1]:
k += 1
while j < n and a[j] == i:
pot = 0
for m in range(1, maxk + 1):
if pots[m - 1][0] <= i and pots[m][0] <= i and pots[m + 1][0] <= i:
pots[m][0] = i + 6
pots[m][1] = True
pot = m
break
if pot == 0:
for m in range(1, maxk + 1):
if pots[m][0] <= i:
pots[m][0] = i + 6
pots[m][1] = False
pots[m - 1][1] = False
pots[m + 1][1] = False
break
j += 1
print(maxk, k)
PascalABC
var
n, min, maxk, k, i, j, m, pot, t: Integer;
a: array [1..5000] of Integer;
busy: array of Integer = new integer[0];
pots: array [0..100, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-127.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
Readln(f, a[i]);
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if a[j] < a[min] then
min := j;
if min <> i then
begin
t := a[i];
a[i] := a[min];
a[min] := t;
end;
end;
maxk := 0;
for i := 1 to n do
begin
j := 0;
while j < busy.Length do
if busy[j] <= a[i] then
busy := busy[:j] + busy[j + 1:]
else
j := j + 1;
busy := busy + Arr(a[i] + 6);
if busy.Length > maxk then
maxk := busy.Length;
end;
for i := 0 to maxk + 1 do
begin
pots[i, 1] := -1;
pots[i, 2] := 1;
end;
j := 1;
k := 0;
for i := 0 to a[n] + 6 do
begin
for m := 1 to maxk do
if (pots[m][1] = i) and (pots[m][2] = 1) then
k := k + 1;
while (j <= n) and (a[j] = i) do
begin
pot := 0;
for m := 1 to maxk do
if (pots[m - 1][1] <= i) and (pots[m][1] <= i) and (pots[m + 1][1] <= i) then
begin
pots[m][1] := i + 6;
pots[m][2] := 1;
pot := m;
break;
end;
if pot = 0 then
for m := 1 to maxk do
if (pots[m][1] <= i) then
begin
pots[m][1] := i + 6;
pots[m][2] := 0;
pots[m - 1][2] := 0;
pots[m + 1][2] := 0;
break;
end;
j := j + 1
end;
end;
Writeln(maxk, ' ', k);
end.
C++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-127.txt");
int n;
f >> n;
int a[5000];
for (int i = 0; i < n; i++)
f >> a[i];
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
if (min != i)
{
int t = a[i];
a[i] = a[min];
a[min] = t;
}
}
int maxk = 0;
vector<int> busy;
for (int i = 0; i < n; i++)
{
int j = 0;
while (j < busy.size())
if (busy[j] <= a[i])
busy.erase(busy.begin() + j);
else
j++;
busy.push_back(a[i] + 6);
if (busy.size() > maxk)
maxk = busy.size();
}
int pots[100][2];
for (int i = 0; i <= maxk + 1; i++)
{
pots[i][0] = -1;
pots[i][1] = 1;
}
int j = 0;
int k = 0;
for (int i = 0; i <= a[n - 1] + 6; i++)
{
for (int m = 1; m <= maxk; m++)
if (pots[m][0] == i && pots[m][1] == 1)
k++;
while (j < n && a[j] == i)
{
int pot = 0;
for (int m = 1; m <= maxk; m++)
if (pots[m - 1][0] <= i && pots[m][0] <= i && pots[m + 1][0] <= i)
{
pots[m][0] = i + 6;
pots[m][1] = 1;
pot = m;
break;
}
if (pot == 0)
for (int m = 1; m <= maxk; m++)
if (pots[m][0] <= i)
{
pots[m][0] = i + 6;
pots[m][1] = 0;
pots[m - 1][1] = 0;
pots[m + 1][1] = 0;
break;
}
j++;
}
}
cout << maxk << " " << k << endl;
}
Ответ
38 2460