--->
164 задач
<---
Источники
#428
Темы:
[Условный оператор (if)]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Год назад Флатландию потряс серьезный экономический кризис, после которого, с целью снижения издержек, фермер Джон и фермер Билл решили объединить свои фермы. За год совместной продуктивной работы на объединенной территории было построено четыре сарая.
Однако последствия кризиса в последнее время ощущаются все меньше, да и совместное ведение хозяйства – дело непростое. Поэтому фермеры решили снова разделить свои фермы.
Для раздела ферм решено было построить забор. Разумеется, прежде чем приступить к строительству, фермеры взяли карту совместного хозяйства и стали обсуждать возможное положение забора. Забор должен представлять собой прямую линию. Поскольку по закону границы участков должны быть направлены либо с севера на юг, либо с запада на восток, забор на карте должен представлять собой прямую, параллельную краю карты – вертикальную либо горизонтальную.
Единственная проблема – четыре построенных за год совместной работы сарая. Разумеется, каждому фермеру в результате раздела должно достаться по два сарая. Поэтому после постройки забора два сарая должны оказаться с одной стороны от него, а два других – с другой.
Помогите фермерам найти такое положение для забора. Забор может проходить непосредственно вдоль стены сарая.
Входные данные
На вход программы поступают четыре четверки целых чисел. Каждая четверка описывает один сарай. Первые два числа в описании сарая – это координаты на карте его левого нижнего угла, следующие два числа – координаты правого верхнего угла.
Система координат размещена таким образом, что ось OX направлена слева направо, а ось OY – снизу вверх. Оси координат параллельны краям карты. Стороны сараев также параллельны краям карты. Сараи не имеют общих точек. Каждый сарай имеет ненулевую площадь. Все координаты неотрицательны и не превышают 109.
Выходные данные
Если построить забор, удовлетворяющий всем условиям, невозможно, выведите слово «Impossible».
В противном случае в первой строке выведите слово «Vertical», если забор следует построить параллельно вертикальному краю карты, или слово «Horizontal», если забор следует построить параллельно горизонтальному краю карты.
В следующей строке выведите координату x всех точек забора, если он должен быть вертикальным, либо координату y всех точек забора, если он должен быть горизонтальным. Выведенная координата должна быть целым числом (несложно показать, что если забор можно построить, то его можно построить так, чтобы искомая координата была целой).
Приведенные ниже рисунки соответствуют примерам входных данных.
Примеры
Входные данные
0 0 1 1 1 2 3 3 4 0 5 3 3 4 6 7
Выходные данные
Vertical 3
Входные данные
0 0 1 1 1 2 3 3 4 0 5 2 2 4 6 7
Выходные данные
Horizontal 2
Входные данные
0 0 1 1 1 2 3 3 4 0 5 3 2 4 6 7
Выходные данные
Impossible
#431
Темы:
[Условный оператор (if)]
[Эвристические методы]
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2004,
Задача M
]
[
Командные олимпиады,
ВКОШП,
2004,
Задача I
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Выполняя очередное задание Министерства образования и сельского хозяйства, программисты Флатландского государственного университета информационных технологий, удобрений и ядохимикатов создали специального робота по прокладке оросительных каналов.
Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:
| Команда | Обозначение | Действия робота |
| Перемещение | (X) | Переместиться вперед на X километров, прокладывая за собой оросительный канал |
| Поворот налево | L | Повернуть налево на 90o |
| Поворот направо | R | Повернуть направо на 90o |
Любая программа начинается и заканчивается командами перемещения и не содержит двух команд перемещения или двух команд поворота подряд.
Исходно робот размещается в некоторой точке поля, на котором требуется создать оросительную систему. После запуска робот последовательно выполняет команды своей программы. Программа считается корректной, если полученный в результате ее выполнения канал не имеет самопересечений или самокасаний.
Программисты университета написали программу и собрались отправить ее по электронной почте в министерство. Однако, в результате поражения сети университета вирусом программа оказалась испорчена. А именно, из нее исчезли все команды перемещения. Теперь программистам требуется восстановить программу. Поскольку времени очень мало, решено было оставить сохранившиеся команды поворота, вставив между ними команды перемещения так, чтобы получившаяся программа была корректной.
Входные данные
Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.
Выходные данные
Выведите любую корректную программу, последовательность команд поворота в которой совпадает с последовательностью, заданной во входных данных. Параметр X каждой команды перемещения должен быть положительным целым числом и не должен превышать 109. Все команды выведите в одной строке и друг от друга не отделяйте.
Примеры
Входные данные
LLLRRR
Выходные данные
(4)L(3)L(1)L(2)R(2)R(1)R(1)
#481
Темы:
[Условный оператор (if)]
[Целые числа]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Для заезда в оздоровительный лагерь организаторы решили заказать автобусы. Известно, что в лагерь собираются поехать N детей и M взрослых. Каждый автобус вмещает K человек. В каждом автобусе, в котором поедут дети, должно быть не менее двух взрослых.
Определите, удастся ли отправить в лагерь всех детей и взрослых, и если да, то какое минимальное количество автобусов требуется для этого заказать.
Входные данные
На вход программы поступают 3 натуральных числа, записанных через пробел - N, M и K, каждое из них не превосходит 10 000.
Выходные данные
Выведите количество автобусов, которые нужно заказать. Если же отправить всех в лагерь невозможно, выведите 0 (ноль).
Пример
| Входные данные | Выходные данные |
| 10 4 7 | 2 |
| 10 4 5 | 0 |
#482
Темы:
[Условный оператор (if)]
[Одномерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).
Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.
Входные данные
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.
Во второй строке следуют K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка - это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края).
Выходные данные
Требуется перечислить ножки, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение, как оно задано во входных данных. Ножки следует перечислять слева направо, в том порядке, в котором они встречаются во входных данных.
Пример
| Входные данные | Выходные данные |
| 5 2 0 2 |
2 |
| 13 4 1 4 8 11 |
4 8 |
| 14 6 1 6 8 11 12 13 |
6 8 |
Второй пример соответствует лавочке на рисунке.
#483
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes
На выборах в Государственную думу в избирательные бюллетени внесено N партий. Электронный сканер для считывания информации с бюллетеней передает информацию о каждом бюллетене в следующем формате: если в соответствующей клетке бюллетеня стоит пометка, то сканер передает + (плюс), в противном случае он передает - (минус). Таким образом, он передает последовательность из N символов - плюсов и минусов.
Бюллетень считается действительным, если пометка есть ровно в одной клетке. Недействительные бюллетени в подсчете результатов выборов не участвуют.
Партия проходит в Государственную Думу, только если она набирает не менее 7% от общего числа действительных бюллетеней.
Требуется вывести номера (в порядке их перечисления в бюллетене) всех партий, которые проходят в Государственную Думу.
Входные данные
В первой строке входных данных содержатся два числа, разделенные пробелом: N - количество партий и M - количество бюллетеней. Оба числа натуральные, N <= 200, M <= 100 000.
В следующих M строках записана информация, полученная из бюллетеней. Каждая строка - последовательность из N символов + или - (без пробелов).
Гарантируется, что есть хотя бы один действительный бюллетень.
Выходные данные
Выведите через пробел номера партий, прошедших в Думу, в порядке возрастания. Если ни одна из партий не проходит в Думу, выводить ничего не нужно.
Пример
| Входные данные | Выходные данные |
| 3 4 +-- +-- -+- +-+ |
1 2 |
| 1 5 + - - - - |
1 |
Выбрано
:
|