Задача 6667. Источник: Поляков. Задание КИМ 26

Страница задачи 6667

Решение

Считываем данные в массив/список и сортируем в порядке возрастания. Создадим массив/список/вектор 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

Отправить замечание по решению