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

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

Решение

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

Считываем данные в массив/список и сортируем их по обоим полям. Создадим массив/список lockers, где будем хранить время освобождения каждой ячейки. Для каждого пассажира ищем свободную ячейку с минимальным номером. Если такая ячейка нашлась, увеличиваем счетчик count и меняем время освобождения ячейки. Значение последней ячейки last меняется только в том случае, если время сдачи багажа больше, чем у предыдущего пассажира. Таким образом, если последними будет несколько пассажиров с одинаковым временем сдачи багажа, в last будет минимальная ячейка.

Python

f = open('26-111.txt')
k = int(f.readline())
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
lockers = [0] * k
count = 0
last = 0
lasttime = 0
for i in a:
    locker = -1
    for j in range(0, k):
        if lockers[j] < i[0]:
            locker = j
            break
    if locker != -1:
        if i[0] > lasttime:
            last = locker + 1
            lasttime = i[0]
        count += 1
        lockers[locker] = i[1]
print(count, last)

PascalABC

var
    n, k, count, last, lasttime, locker, min, i, j, t: Integer;
    a: array [1..987, 1..2] of Integer;
    lockers: array [1..210] of Integer;
    f: TEXT;
begin
    Assign(f, '26-111.txt');
    Reset(f);
    Readln(f, k, n);
    for i := 1 to n do
        Readln(f, a[i, 1], a[i, 2]);
    for i := 1 to n - 1 do
    begin
        min := i;
        for j := i + 1 to n 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 k do
        lockers[i] := 0;
    count := 0;
    last := 0;
    lasttime := 0;
    for i := 1 to n do
    begin
        locker := 0;
        for j := 1 to k do
            if lockers[j] < a[i, 1] then
            begin
                locker := j;
                break;
            end;
        if locker <> 0 then
        begin
            if a[i, 1] > lasttime then
            begin
                last := locker;
                lasttime := a[i, 1];
            end;
            count := count + 1;
            lockers[locker] := a[i][2]
        end;
    end;
    Writeln(count, ' ', last);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-111.txt");
    int k, n;
    f >> k >> n;
    int a[987][2];
    for (int i = 0; i < n; i++)
        f >> a[i][0] >> a[i][1];
    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] || 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 lockers[210];
    for (int i = 0; i < k; i++)
        lockers[i] = 0;
    int count = 0, last = 0, lasttime = 0;
    for (int i = 0; i < n; i++)
    {
        int locker = -1;
        for (int j = 0; j < k; j++)
            if (lockers[j] < a[i][0])
            {
                locker = j;
                break;
            }
        if (locker != -1)
        {
            if (a[i][0] > lasttime)
            {
                last = locker + 1;
                lasttime = a[i][0];
            }
            count++;
            lockers[locker] = a[i][1];
        }
    }
    cout << count << " " << last << endl;
}

Ответ

344 53

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