Страница: 1 2 >> Отображать по:

#3688

Мостостроение

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

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

Все оставшиеся бревна имеют одинаковую толщину. При этом есть $x$ бревен длины $a$ и $y$ бревен длины $b$

Построенный мост должен состоять из $l$ рядов, каждый из которых составлен из одного или нескольких бревен. Пилить бревна нельзя, так как последняя пила утонула при разливе Вонючки. Главный инженер хочет построить мост максимальной возможной ширины, при этом ширина моста определяется по минимальной ширине ряда бревен.

Например, если нужно построить мост из семи рядов, и при этом есть шесть бревен длины 3 и десять бревен длины 2, то можно построить мост ширины 5.

$\text{[math]}$

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

Входной файл содержит пять натуральных чисел: $x$, $a$, $y$, $b$ и $l$. Все числа не превышают 150. Общее количество бревен не меньше $l$.

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

Выведите в выходной файл одно число — максимальную возможную ширину моста

Примеры

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

6 3 10 2 7

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

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

10 7 20 9 25

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

#3689

Кафе

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

Летнее кафе имеет форму прямоугольника размером $n$ × $m$ клеток, в каждой из которых может находиться стол или стул

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

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

Входной файл содержит три числа $n$, $m$ и $k$ (1 ≤ $n$, $m$ ≤ 50, 1 ≤ $k$ ≤ 10000).

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

Выходной файл должен содержать n строк по m символов — план размещения столов и стульев для банкета. Символ «h» обозначает стул, символ «T» — стол, символ «.» — пустую клетку. Если решения нет, выведите строку «Impossible».

Примеры

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

3 4 8

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

hhhh
hThT
hh..

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

2 2 4

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

Impossible

#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

Страница: 1 2 >> Отображать по:

Выбрано

Отменить

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