Страница: << 77 78 79 80 81 82 83 >> Отображать по:

#3690

Кот

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача C ]

Антон завел себе кота. Кот очень любит спать. Если он засыпает, он спит непрерывно не менее a часов. Более того, долго не спать кот просто не может. Кот не может бодрствовать больше b часов подряд.

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

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

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

Первая строка входного файла содержит два целых числа $a$ и $b$ (1 ≤ $a$, $b$ ≤ 24). Вторая строка входного файла содержит число $n$ — количество интересных событий (1 ≤ $n$ ≤ 20). Следующие n строк содержат описание интересных событий. Каждое событие описывается строкой вида «hh:mm-hh:mm», которая задает период времени, в течение которого оно происходит. Время изменяется от 00:00 до 23:59. Никакие два интересных события не пересекаются. Если событие завершается раньше, чем началось, это означает, что оно захватывает полночь.

Событие считается занимающим целиком минуту, когда оно начинается и минуту, когда оно заканчивается (например, событие «12:00-13:59» продолжается ровно 120 минут). Время начала и время конца события различны.

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

Если кот может организовать свои сутки так, чтобы во время всех интересных событий не спать, выведите в выходной файл «Yes». На второй строке выведите $k$ — сколько раз в сутки кот должен ложиться спать. На следующих $k$ строках выведите интервалы, в которые кот спит в том же фор- мате, в котором интересные события заданы во входном файле. Если решений несколько, выведите любое.

Если кот не может организовать свои сутки искомым образом, выведите в выходной файл «No».

Примеры

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

3 4
2
07:00-07:15
19:00-19:59

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

Yes
2
07:16-18:59
20:00-06:59

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

3 4
3
07:00-08:00
11:00-11:09
19:00-19:59

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

No

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

12 12
1
23:00-01:00

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

Yes
1
01:01-22:59

#3691

Сборка компьютеров

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача D ]

В рамках национальной программы «Электронная Россия» одно государственное учреждение заказало несколько системных блоков и столько же мониторов. При составлении заказа, однако, никто не учел, что существует два типа интерфейсов для соединения системных блоков и мониторов: VGA и DVI. При этом существуют системные блоки и мониторы, которые поддерживают как только один из этих интерфейсов, так и оба.

Поставщик техники оказался не очень добросовестным — в поставке оказалось $a_1$ системных блоков, которые поддерживают только VGA, $a_2$ системных блоков, которые поддерживают толь- ко DVI, и $a_3$ системных блоков, которые поддерживают оба интерфейса. С мониторами ситуация аналогична: $b_1$ мониторов поддерживают только VGA, $b_2$ — только DVI, $b_3$ — поддерживают оба интерфейса.

Необходимо выяснить, сколько комплектов из монитора и системного блока можно собрать. При этом соединить монитор и системный блок можно только если у них есть общий интерфейс.

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

Первая строка входного файла содержит три числа $a_1$, $a_2$ и $a_3$ (0 ≤ $a_1$, $a_2$, $a_3$ ≤ 100). Вторая строка входного файла содержит три числа $b_1$, $b_2$ и $b_3$ (0 ≤ $b_1$, $b_2$, $b_3$ ≤ 100). При этом выполняется равенство $a_1$ + $a_2$ + $a_3$ = $b_1$ + $b_2$ + $b_3$.

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

В выходной файл выведите максимальное число комплектов из монитора и системного блока, которые можно собрать.

Примеры

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

3 4 6
2 3 8

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

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

3 4 6
2 11 0

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

#3692

Куб

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача E ]

Сегодня на уроке геометрии Маша и Паша изучали геометрические тела. Одним из самых простых геометрических тел является куб. Обозначим четыре вершины нижней грани куба в порядке обхода как $A$, $B$, $C$ и $D$, а четыре вершины верхней грани куба, находящиеся над ними, как $A_1$, $B_1$, $C_1$ и $D_1$, соответственно.

$\text{[math]}$

Машу с Пашей заинтересовал вопрос: при каких условиях отрезки, концы которых находятся в вершинах куба, пересекаются. Помогите им это выяснить.

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

Входной файл содержит две строки. Первая строка содержит названия вершин, которые являются концами первого отрезка, а вторая — названия вершин, которые являются концами второго отрезка. Названия не разделены пробелом, вершины $A_1$, $B_1$, $C_1$ и $D_1$ задаются как «$A_1$», «$B_1$», «$C_1$» и «D1» соответственно.

Отрезки, заданные во входном файле не совпадают. Начало и конец у каждого отрезка не совпадают.

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

Выведите в выходной файл «Yes», если отрезки пересекаются, или «No», если нет.

Примеры

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

AA1
A1C

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

Yes

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

AD
A1C1

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

No

#3693

Домашнее задание

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача F ]

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

Для каждого задания Сережа оценил, сколько минут потребуется для его выполнения. После этого Сережа понял, что сделать все задания он точно не успеет. Тогда он решил сделать все задания кроме одного — за одно несделанное задание учитель, наверное, не будет слишком сильно ругаться. Теперь Сереже надо выбрать, какое задание не сделать.

Помогите Сереже выбрать задание, которое можно не делать, чтобы закончить все остальные задания как можно быстрее.

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

Первая строка входного файла содержит целые числа n и m — количество заданий и количество зависимостей между заданиями (1 ≤ $n$ ≤ 100, 0 ≤ $m$ ≤ 1000). Вторая строка содержит n целых чисел: $t_1$, $t_2$, ... , $t_n$. Число $t_i$ означает количество минут, необходимое Сереже для выполнения $i$-го задания (1 ≤ $t_i$ ≤ 1000).

Затем следует m строк, каждая строка содержит два целых числа. Числа $a$ и $b$ означают, что задание $a$ должно быть выполнено до задания $b$. Гарантируется, что все задания можно выполнить.

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

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

Пояснение к примеру

В приведенном примере Сережа может не выполнять четвертое задание. Остальные задания суммарно требуют 11 минут.

Примеры

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

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

#3694

Москва 2042

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2009, Задача G ]

К 2042 году правительство Москвы завершило очередной масштабный проект, доведя количество кольцевых автодорог до $n$. Теперь у автомобилиста еще больше способов постоять в пробке в попытке добраться от одной точки города до другой

Компания «Giggle» планирует в своем новом продукте «Giggle Maps» реализовать возможность проложить оптимальный маршрут от одного перекрестка до другого. Карта Москвы во внутреннем формате программы представляет собой набор из $m$ радиальных и $n$ кольцевых магистралей, при этом некоторые из кольцевых магистралей являются односторонними.

В математической модели «Giggle» все кольцевые магистрали представляют собой концентрические окружности с центром на Красной площади и радиусами $r_1$, $r_2$, ..., $r_n$. Радиальные магистрали представляют собой отрезки, один из концов каждого отрезка лежит на Красной площади, а другой — на кольцевой магистрали с максимальным радиусом. Если встать на Красной площади и смотреть на восток, то, чтобы посмотреть в направлении j-ой радиальной магистрали, нужно повернуться против часовой стрелки на $a_j$ градусов. По каждой из радиальных магистралей можно ехать в любом направлении. Кольцевые магистрали, в свою очередь, бывают как двусторонними, так и односторонними.

Помогите компании «Giggle» найти кратчайший путь от перекрестка где пересекаются $i_s$-я кольцевая и $j_s$-я радиальная магистраль до перекрестка, где пересекаются $i_t$-я кольцевая и $j_t$-я радиальная магистраль. При этом проезжать через Красную площадь не разрешается

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

Первая строка входного файла содержит целые числа $n$ и $m$ (1 ≤ $n$, $m$ ≤ 100 000).

Следующие n строк описывают кольцевые магистрали. Каждая магистраль описывается целым числом $r_i$ (1 ≤ $r_i$ ≤ $10^6$) и числом 0, если магистраль является двусторонней, 1, если по ней разрешено движение только против часовой стрелки (в сторону увеличения углов радиальных магистралей) или −1, если по ней разрешено движение только по часовой стрелке.

Следующие m строк описывают радиальные магистрали. Каждая магистраль описывается одним целым числом $A_j$ , причем $a_j$ = $A_j$/$10^6$ (0 ≤ $A_j$ < 360 · $10^6$).

Затем следует две строки: первая из них содержит числа $i_s$ и $j_s$, а вторая — числа $i_t$ и $j_t$

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

Выведите в выходной файл одно вещественное число: минимальное расстояние, которое придется проехать, чтобы попасть с перекрестка где пересекаются $i_s$-я кольцевая и $j_s$-я радиальная магистраль на перекресток, где пересекаются $i_t$-я кольцевая и $j_t$-я радиальная магистраль. Ваш ответ должен отличаться от правильного не больше чем на 10⁻⁴.

Пояснение к примеру

$\text{[math]}$

Примеры

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

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

12.99557428756427600000

Страница: << 77 78 79 80 81 82 83 >> Отображать по:

Выбрано

Отменить

Добавить в контест