Question

На вход программе подаются сведения о посетителях кафе. В первой строке указаны число посетителей N (от 10 до 1000) и количество столиков K (от 10 до 1000). Каждая из следующих N строк содержит:

<Фамилия> <время_прихода> <время_ухода>

где <Фамилия> — строка до 20 символов; <время_прихода> и <время_ухода> — время в формате ЧЧ:МММ (часы от 00 до 23, минуты от 00 до 59). Данные отсортированы по времени прихода.

Каждому посетителю выделяется свободный столик с минимальным номером. Столик считается свободным, если его время освобождения не превышает время прихода посетителя. Если свободных столиков нет, посетитель уходит без обслуживания.

Требуется вывести для каждого обслуженного посетителя его фамилию и номер выделенного столика.

Пример входных данных:

3 10
Иванов 09:45 12:00
Петров 10:00 11:00
Сидоров 12:00 13:12

Ожидаемый вывод:

Иванов 1
Петров 2
Сидоров 1

Accepted Answer

Программа выводит для каждого обслуженного посетителя его фамилию и номер выделенного столика в порядке прихода

Answer

Идея решения: для каждого столика хранить время его освобождения; при приходе посетителя найти первый столик, который освободился не позже времени его прихода, и обновить время его освобождения.

Алгоритм:
1. Инициализировать массив времён освобождения столиков нулями (все столики свободны).
2. Для каждого посетителя:
   - Прочитать фамилию и оба времени, перевести их в минуты от начала суток.
   - Пройти по столикам в порядке возрастания номеров.
   - Найти первый столик, у которого время освобождения ≤ времени прихода.
   - Если найден — обновить его время освобождения и вывести результат.
   - Если не найден — посетитель не обслужен.

**Решение на Python:**

```python
n, k = map(int, input().split())
p = [0] * (k + 1)  # p[i] — время освобождения столика i

for _ in range(n):
    line = input().split()
    name = line[0]
    arrival = line[1]
    departure = line[2]
    
    # Преобразование времени в минуты
    h1, m1 = map(int, arrival.split(':'))
    time1 = h1 * 60 + m1
    
    h2, m2 = map(int, departure.split(':'))
    time2 = h2 * 60 + m2
    
    # Поиск свободного столика
    for j in range(1, k + 1):
        if p[j] <= time1:
            p[j] = time2
            print(name, j)
            break
```

**Решение на Паскале:**

```pascal
var
  p: array[1..1000] of integer;
  c, c1: char;
  i, j, n, k: integer;
  name: string;
  time1, time2: integer;
begin
  readln(n, k);
  for i := 1 to k do
    p[i] := 0;
  
  for i := 1 to n do
  begin
    name := '';
    repeat
      read(c);
      name := name + c;
    until c = ' ';
    
    read(c, c1);
    time1 := 60 * ((ord(c) - ord('0')) * 10 +
                    ord(c1) - ord('0'));
    read(c, c, c1);
    time1 := time1 + (ord(c) - ord('0')) * 10 +
                     ord(c1) - ord('0');
    
    read(c, c, c1);
    time2 := 60 * ((ord(c) - ord('0')) * 10 +
                    ord(c1) - ord('0'));
    readln(c, c, c1);
    time2 := time2 + (ord(c) - ord('0')) * 10 +
                     ord(c1) - ord('0');
    
    for j := 1 to k do
      if p[j] <= time1 then
      begin
        p[j] := time2;
        writeln(name, ' ', j);
        break;
      end;
  end;
end.
```

Сложность: $O(n \cdot k)$ — для каждого из n посетителей проверяются до k столиков.

Задание №19Алгоритмы и исполнителиЕГЭ по информатике