Олимпиадная задача по программированию с решением – #4

Разберем решение олимпиадной задачи по программированию про парикмахерскую. В статье представлен алгоритм решения в текстовом виде и исходной код программы на языке C# с комментариями.

Условие задачи

В парикмахерской работает один мастер. Он тратит на одного клиента ровно 20 минут, а затем сразу переходит к следующему, если в очереди кто-то есть, либо ожидает, когда придет следующий клиент.

Даны времена прихода клиентов в парикмахерскую (в том порядке, в котором они при-ходили).

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

Требуется для каждого клиента указать время его выхода из парикмахерской.

Формат входного файла

В первой строке вводится натуральное число N, не превышающее 100 — количество клиентов.

В следующих N строках вводятся времена прихода клиентов — по два числа, обозначающие часы и минуты (часы — от 0 до 23, минуты — от 0 до 59) и степень его нетерпения (неотрицательное целое число не большее 100) — максимальное количество человек, которое он готов ждать впереди себя в очереди. Времена указаны в порядке возрастания (все времена различны).

Гарантируется, что всех клиентов успеют обслужить до полуночи.

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

Формат выходного файла

В выходной файл выведите N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-гo клиента (часы и минуты). Если на момент прихода клиента человек в очереди больше, чем степень его нетерпения, то можно считать, что время его ухода равно времени прихода.

Примеры

Примеры данных для олимпиадной задачи по программированию про парикмахерскую

Алгоритм решения

Примем, что нумерация элементов в массиве начинается с нуля.

  1. Прочитать из входного файла первую строку (это число N).
  2. Создать массив длиной N для хранения времени входа клиентов в парикмахерскую (массив элементов типа Time, DateTime или что-то в этом роде). Назовем его input.
  3. Создать массив целых чисел длиной N для хранения степени нетерпения каждого клиента. Назовем его impatience.
  4. Прочитать из входного файла N строк и заполнить прочитанными данными массивы input и impatience.
  5. Создать массив длиной N для хранения времени выхода клиентов из парикмахерской (массив элементов типа Time, DateTime или что-то в этом роде). Назовем его output.
  6. В ЦИКЛЕ for от 0 до N – 1 (по i):
    1. Объявим переменную целого типа k = 0. Это количество людей в очереди перед i-м клиентом.
    2. Объявим переменную целого типа kN = 0. Это расстояние в рамках массива от i-го клиента до первого в очереди перед ним.
    3. Найдем эти значения путем перебора элементов массива output от i – 1 до 0 (переменная цикла j) и сравнивая значения времени с input[i]. (ЕСЛИ output[j] > input[i], ТО k = k + 1 и kN = i – j).
    4. ЕСЛИ степень нетерпения i-го клиента меньше k, ТО output[i] = input[i] (значит он не будет ждать и уходит); ИНАЧЕ output[i] = input[i] + 20 минут (в начале примем, что ему возможно не нужно будет ждать очереди), далее в цикле от i – 1 до i – kN по j: ЕСЛИ output[j] > input[i] (значит i-й клиент сразу после j-го), ТО output[i] = output[j] + 20 минут и выходим из цикла по j.
  7. Вывести значения массива output в выходной файл.

Решение задачи на языке C#

Оцените статью

Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">