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

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

(А. Рогов) В отделении банка используется система распознавания лиц, с помощью которой фиксируется время, когда посетитель пришел в отделение и время, когда он вышел. Для удобства время хранится как целое число, показывающее, сколько секунд прошло от начала суток до события. Посетителей банка обслуживают операторы, которые пронумерованы, начиная с 1. Посетитель обслуживается свободным оператором с минимальным номером. Оператор может принять следующего посетителя в ту же секунду, как обслуживаемый им посетитель покидает здание. На обслуживание требуется, как минимум, одна секунда. Если свободных операторов нет, посетитель становится в очередь. Посетитель может не дождаться своей очереди и уйти.

Определите, сколько посетителей было обслужено операторами и номер оператора, обслужившего последнего посетителя.

Входные данные представлены в файле 26-132.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) – количество посетителей, и натуральное число K (1 ≤ K ≤ 1000) – количество операторов в отделении. В каждой из последующих N строк записаны через пробел в возрастающем порядке по два целых неотрицательных числа: T₁ (0 ≤ T₁ ≤ 86399) – время, в которое посетитель зашел в отделение и T₂ (T₁ ≤ T₂ ≤ 86399) – время, когда он вышел. Считается, что до начала суток и после их окончания в помещении посетителей не было. Все, кто зашел в отделение, успел выйти до закрытия.

Запишите в ответе два числа: количество посетителей, обслуженных операторами, и номер оператора, обслужившего последнего посетителя.

Пример входного файла:
6 2
1 50
2 40
5 100
50 86000
60 70
70 100

При таких исходных данных были успешно обслужены 4 посетителя, пятый и шестой ушли раньше, чем подошла их очередь. Последнего посетителя обслуживал оператор 1. Ответ: 4 1.

Решение

Сортируем исходные данные в массиве a по времени прибытия посетителей и последовательно обрабатываем список. В массиве m будем хранить время, когда освобождаются операторы. Обрабатывая каждого посетителя, ищем оператора с минимальным номером, который освободился до прибытия посетителя. Если такового не нашлось, ищем оператора с минимальным номером и временем освобождения, которое меньше времени ухода посетителя. Если свободный оператор нашелся, увеличиваем счетчик обслуженных посетителей, фиксируем номер оператора в переменной last и обновляем время освобождения данного оператора.

Python

f = open('26-132.txt')
n, k = map(int, f.readline().split())
m = [0] * (k + 1)
a = [[int(y) for y in x.split()] for x in f]
a.sort(key = lambda x:x[0])
count = 0
last = 0
for i in a:
    z = -1
    for j in range(1, k + 1):
        if m[j] <= i[0]:
            z = j
            break
    if z == -1:
        for j in range(1, k + 1):
            if m[j] < i[1] and (z == -1 or m[j] < m[z]):
                z = j
    if z != -1:
        count += 1
        last = z
        m[z] = i[1]
print(count, last)

PascalABC

var
    n, k, i, j, t, z, min, count, last: Integer;
    a: array [1..3200, 1..2] of Integer;
    m: array [1..500] of Integer;
    f: TEXT;
begin
    Assign(f, '26-132.txt');
    Reset(f);
    Readln(f, n, k);
    for i := 1 to n do
        Readln(f, a[i, 1], a[i, 2]);
    for i := 1 to k do
        m[i] := 0;
    for i := 1 to n - 1 do
    begin
        min := i;
        for j := i + 1 to n do
            if a[j, 1] < a[min, 1] 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;
    count := 0;
    last := 0;
    for i := 1 to n do
    begin
        z := 0;
        for j := 1 to k do
            if m[j] < a[i][1] then
            begin
                z := j;
                break;
            end;
        if z = 0 then
            for j := 1 to k do
                if (m[j] < a[i][2]) and ((z = 0) or (m[j] < m[z])) then
                    z := j;
        if z <> 0 then
        begin
            count := count + 1;
            last := z;
            m[z] := a[i][2]
        end;
    end;
    Writeln(count, ' ', last);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-132.txt");
    int n, k;
    f >> n >> k;
    int a[3200][2], m[501];
    for (int i = 0; i < n; i++)
        f >> a[i][0] >> a[i][1];
    for (int i = 0; i < k; i++)
        m[i] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j][0] < a[min][0])
                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 count = 0, last = 0;
    for (int i = 0; i < n; i++)
    {
        int z = -1;
        for (int j = 1; j <= k; j++)
            if (m[j] < a[i][0])
            {
                z = j;
                break;
            }
        if (z == -1)
            for (int j = 1; j <= k; j++)
                if (m[j] < a[i][1] && (z == -1 || m[j] < m[z]))
                    z = j;
        if (z != -1)
        {
            count++;
            last = z;
            m[z] = a[i][1];
        }
    }
    cout << count << " " << last << endl;
}

Ответ

2108 9

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

Решение

Python

PascalABC

C++

Ответ

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