E-Olymp 7029. Поликлиника

Задача

На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени $t_1$ минут и заканчивает прием в момент времени $t_2$ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты $t_1, t_1 + 1, …, t_2 − 1$. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент $t$, он ожидает первый момент времени $s ≥ t$ такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента $t$. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

Зная, в какой момент доктор начинает и заканчивает прием, те, кто и когда придут на прием в конкретный день, а также сколько времени будет осматривать доктор каждого пациента, определите момент времени, в который необходимо прийти на прием Пете Пяточкину, чтобы гарантированно попасть в этот день к доктору, и при этом ожидать приема как можно меньше. В случае, если имеется несколько альтернативных вариантов такого момента времени, Вам необходимо определить наименьший (наиболее ранний) из них.

Входные данные

В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема $t_1$ и время завершения приема $t_2$, больший чем $t_1$.

Во второй строке перечислены $n$ чисел $a_1, a_2, …, a_n$ — время, когда в поликлинику зашли соответственно первый, второй, $…, n$-ый желающий попасть к доктору. Числа $a_1, a_2, …, a_n$ попарно различны и расположены в порядке возрастания.

В третьей строке перечислены n чисел $b_1, b_2, …, b_n$ — время, необходимое доктору на осмотр соответственно первого, второго, $…, n$-го пациента.

Все входные числа натуральные. Количество пациентов $n$ не больше $10^5$, остальные числа не превосходят $10^9$.

Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема $t_1$, время завершения приема $t_2$, а также числа $a_1, a_2, …, a_n$ и $b_1, b_2, …, b_n$ могут быть большими чем 1440 — количество минут в земных сутках.

Выходные данные

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

Тесты

Входные данные Выходные данные
1 3 10 20
7 14 18
5 2 1
17
2 5 10 20
4 9 12 16 22
4 10 10 9 2
9
3 1 10 20
5
15
5

Код

Решение

Создаём два массива, удовлетворяющих условия, a — время прихода пациентов и b — время на их приём. Инициализируем все необходимые переменные: t_1 и t_2 — время приёма, t — время в которое Петя должен прийти, n- кол-во пациентов, i и j — счётчики, l — время между приходом пациента и началом его приёма.

Проверяем приходит ли первый пациент в самое начало приёма или после начала приёма, если в начало приёма — то приходим тогда.

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

В конце проверяем, если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось — приходим сразу в конце приёма последнего.

5 thoughts on “E-Olymp 7029. Поликлиника

  1. — Настройте, пожалуйста корректное отображение своего имени и фамилии. Сейчас это просто «EVCHUK». Посмотрите справа от этого комментария, как сделали другие.
    — Все формулы должны набираться в laTeX. Пожалуйста, посмотрите правила оформления работ. Или откройте для примера любую работу на этом сайте.
    — Посмотрите статью «Отступ (программирование)» на Википедии. Или любые другие правила оформления кода.
    — «приёма/после» — это что?
    — Если в объяснении встречаются формулы, то их нужно тоже оформлять в laTeX. Если там есть фрагмента кода, например, while, то их нужно оформлять как код. Иногда бывает сложно разобраться как разметить $t_1$ или t1. Но есть простое правило. Если вы говорите об условии задачи или алгоритме (формуле) ее решения, то $t_1$. Но если Вы описываете, что происходит в какой-то строчке Вашей программы, то t1.
    — Пожалуйста, уберите все эти & nbsp; и пустые строки. Зачем вы их столько навставляли? Вы же не работаете в визуальном режиме?
    — «В цикле while пошагово проверяем минимальное время» — точно просто проверяете? И что значит проверить время? Можно проверить выполнение условия, но не время. Уточните, пожалуйста. Вообще этот абзац довольно нескладный вышел.
    — Вообще идея описывать программу вместо алгоритма решения не очень хорошая, но у Вас почти получилось. Поработайте, пожалуйста, еще немного над текстом.
    — Это задача не на спортивное программирование. Вы ведь не на какой-то олимпиаде ее решали, а получл бычное учебное задание от преподавателяю Посмотрите, пожалуйста, какие бывают категории.

    • Добрый день, всё исправила, жду проверки.

  2. — Как Вы думаете после этого текста «Инициализируем все необходимые переменные:» дальше будет идти формула или переменная программы? Судя по тексту должна идти переменная. А разметка как формула.
    — «зафиксированная разницы»? Что-то тут не согласовано.
    — Я уже писал замечание по абзацу о цикле. Вы несколько раз пишите «Проверяем…» Ну, вот мы проверили некоторое условие. И что? Важно ведь то, что мы делаем если условие истинно или ложно. Сама проверка без последствий смысла не имеет. Попробуйте найти что-то характерное для вашего алгоритма. Вполне достаточно одной или двух слов.
    — Формула, это не только буква с индексом. Весь текст с запятыми и многоточиями, различными знаками, все это одна формула. Посмотрите как кодируют многоточие и знак больше либо равно в laTeX.
    — «выводим результат из цикла»? Что это означает?
    — у вас нет ни одной разумной метки. Похоже вы не совсем поняли, что это. Ближе всего по смыслу к меткам хештэги. Не может быть хештег названием или номером задачи. Нет смысла дублировать название категории. Метка, это что-то характерное из вашего подхода к решению задачи.

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