Задачи очного тура личного первенства по спортивному программированию
A. Голосование
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На Марсе выбирают председателя Верховного Совета. Пришли и проголосовали почти все жители Марса и пока лидирует первый кандидат,
но еще не подсчитаны бюллетени, присланные по почте.
Вычислите минимальное количество голосов, которое должно быть добавлено за второго кандидата,
чтобы за него получилось не менее `X`% голосов из общего количества проголосовавших лично и по почте.
Известно, что все присланные по почте голоса отданы второму кандидату.
Первая строка ввода содержит три целых числа - количество голосов за первого кандидата `A`,
количество голосов за второго кандидата `B` (`0<=B<A<=10^6`), процент голосов для победы `X` (`51<=X<=99`).
Вывести одно целое число - минимальное количество добавочных голосов за второго кандидата для победы с результатом `X` или более %.
```sample Пример ввода
99 1 51
```
```sample Пример вывода
103
```
Пояснение к примеру: после добавления 103 голосов за второго кандидата получится (1+103)/(99+1+103)*100%=51.23% > 51%
B. Перевод
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Несмотря на терраформирование, произведенное Куэйдом с помощью древнего генератора,
атмосфера на Марсе остается разреженной, и
местные жители не могут произнести гласные звуки без дополнительного вдоха.
В записи данная особенность произношения выглядит как
<последовательность гласных букв>h<та же последовательность гласных букв>, например,
"papers, please" превращается в "pahapehers, pleahease".
Туристам с Земли сложно понимать местную речь, и вам поручается написать программу для перевода,
которая уберет обозначение вдоха h и повторение гласных букв из записи фразы, произнесенной марсианином.
Гласными буквами будем считать буквы a, e, i, o, u.
Некоторые гласные звуки могут быть произнесены марсианином за один раз, тогда они не повторяются в записи.
Если части последовательности гласных букв означают разные гласные звуки, как в примере 2, то они повторяются в записи отдельно. Буквы, уже использованные в повторении, более не повторяются.
Первая строка ввода содержит последовательность строчных латинских букв, пробелов и знаков препинания длиной
от 1 до 100 символов - запись произношения фразы марсианином.
Вывести запись фразы в обычной форме.
```sample Пример ввода 1
pahapehers, pleahease
```
```sample Пример вывода 1
papers, please
```
```sample Пример ввода 2
behihind the pihiohoneeheer maharsihio
```
```sample Пример вывода 2
behind the pioneer marsio
```
C. Часы
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Сутки на Марсе имеют продолжительность 24 часа 40 минут.
Жители Марса не стали менять ни продолжительность одной минуты, ни количество часов в сутках, а
добавили дополнительные 40 минут к 24 часу суток.
Полночь (00:00) на Марсе наступает не после 23:59, а после 23:99.
Туристы с Земли не покупают специальные марсианские часы, а просто каждое утро переводят
свои часы на 40 минут назад, чтобы знать текущее время на Марсе.
Напишите программу, которая поможет определить туристу текущее марсианское время по времени на земных часах,
установленных по марсианскому времени в предыдущий день.
Первая строка ввода содержит время на земных часах в формате `HH`:`MM` (`00 <= HH <= 23`, `00 <= MM <= 59`).
Вывести текущее марсианское время в том же формате (час и минута должны быть выведены
как две цифры с ведущим нулем при необходимости).
```sample Пример ввода 1
07:45
```
```sample Пример вывода 1
07:05
```
```sample Пример ввода 2
00:30
```
```sample Пример вывода 2
23:90
```
D. Доставка
Ограничения: время – 100ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Том должен доставить ровно `W` килограмм суперцемента для строительства.
Цемент упакован в мешки по 8 и по 25 килограмм.
Так как Том может переносить только по одному мешку со склада в машину,
то для уменьшения времени погрузки необходимо определить минимальное количество мешков для получения заданного веса.
Первая строка ввода содержит одно целое число `W` (`8 <= W <= 10^9`) - необходимый вес цемента.
Вывести одно целое число - минимальное количество мешков цемента. Если ровный вес не получается, то вывести -1.
```sample Пример ввода 1
10
```
```sample Пример вывода 1
-1
```
```sample Пример ввода 2
24
```
```sample Пример вывода 2
3
```
```sample Пример ввода 3
99
```
```sample Пример вывода 3
6
```
Пояснение к примеру: нужно взять 3 мешка по 25 кг и 3 мешка по 8 кг.
E. Матч
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Том наблюдает за матчем, в котором играют две популярные на Марсе команды.
Продолжительность матча - два тайма по 24 минуты, всего 48 минут.
Команда, за которую болеет Том, иногда проигрывает,
но тогда Том рассчитывает время, в течение которого его любимая
команда лидировала по количеству очков во время матча, и сравнивает его с аналогичным временем у другой команды.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 100`) - количество изменений счета во время матча.
Далее следует `N` строк, содержащих номер команды (1 или 2), получившей очко, и время этого события
в формате `MM`:`SS` (`00 <= MM <= 47`, `00 <= SS <= 59`). События заданы в порядке возрастания времени, нет событий с одинаковым временем.
Вывести два целых числа - время в секундах, в течение которого лидировала первая команда, и время, в течение которого лидировала
вторая команда.
```sample Пример ввода 1
1
1 30:00
```
```sample Пример вывода 1
1080 0
```
```sample Пример ввода 2
3
1 01:15
2 21:15
2 31:20
```
```sample Пример вывода 2
1200 1000
```
F. Марсио
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
 Том разрабатывает игру-платформер про Марсио, первого исследователя Марса.
После разработки уровней Том подсчитал их сложность - сумму минимального необходимого количества
прыжков и выстрелов для прохождения уровня. Некоторые начальные уровни игры оказались слишком сложными
по этой оценке, и Том решил убрать некоторые препятствия и врагов с начальных уровней,
чтобы сложность уровней шла в строго возрастающем порядке.
Так как добавление новых препятствий на уровень является более сложной задачей, то Том хочет минимизировать
суммарное количество добавлений новых препятствий и врагов. С другой стороны Том хочет максимально сохранить
уже имеющиеся препятствия и нужно минимизировать суммарное количество удаляемых препятствий. Также сложность
самого первого уровня игры не должна быть меньше 1.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 100000`) - количество уровней в игре.
Далее следует `N` строк, содержащих по одному целому числу от 1 до `10^6` - начальная сложность уровней до изменений.
Вывести `N` строк по одному числу строке - минимальные изменения, которые нужно сделать на
этом уровне. Отрицательное число означает, что сложность уровня нужно уменьшить на соответствующую
величину, положительное число - что сложность нужно увеличить на эту величину, 0 - что сложность уровня можно оставить без изменений.
Если существует несколько вариантов, то вывести вариант, в котором суммарное количество добавлений на всех уровнях минимально.
Если существует несколько таких вариантов с минимальных количеством добавлений, то вывести тот вариант из них,
в котором суммарное количество удаляемых препятствий минимально.
```sample Пример ввода 1
3
5
5
5
```
```sample Пример вывода 1
-2
-1
0
```
```sample Пример ввода 2
4
5
1
7
5
```
```sample Пример вывода 2
-4
1
-3
0
```
G. Друзья и враги
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В Верховном Совете Марса некоторые члены дружат между собой, а некоторые строят друг другу козни.
Предположим, что в Верховном Совете попытаются применить известные правила
"Враг моего врага — мой друг", "Друг моего врага — мой враг",
"Враг моего друга — мой враг", "Друг моего друга — мой друг" и получить получить полные списки прямых и косвенных
друзей и врагов для каждого члена Совета, то удастся ли это сделать без противоречий (попадание одного и того же человека в оба списка)?
При получении списков возможно применений этих правил неограниченное количество раз.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 100000`) - количество членов Верховного Совета.
Вторая строка ввода содержит одно целое число `K` (`0 <= K <= 100000`) - количество отношений дружбы.
Далее следует `K` строк, содержащих два целых числа от 1 до `N` - номера членов Совета, находящихся в дружеских отношениях.
Следующая строка ввода содержит одно целое число `M` (`0 <= M <= 100000`) - количество отношений вражды.
Далее следует `M` строк, содержащих два целых числа от 1 до `N` - номера членов Совета, находящихся во враждебных отношениях.
Все пары чисел различны, нет пар с совпадающими числами. Отношения дружбы и вражды являются взаимными - если `a` друг `b`, то `b` друг `a`.
Вывести сообщение ``Yes``, если заданные отношения не приводят к противоречиям при применении вышеуказанных правил,
или сообщение ``No``, в противном случае.
```sample Пример ввода 1
7
3
1 2
3 1
5 6
2
2 4
3 4
```
```sample Пример вывода 1
Yes
```
```sample Пример ввода 2
3
0
3
1 2
2 3
3 1
```
```sample Пример вывода 2
No
```
H. Епархии
Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В марсианском поселении распространились несколько экзотических религий, и верующие решили
создать епархии для каждой из них. Епархия должна иметь форму прямоугольника,
и количество верующих, проживающих в этой епархии, должно превышать верующих всех других религий вместе взятых.
Желательно, чтобы эта разница в количестве верующих была максимальной.
Если существует несколько вариантов, обеспечивающих максимальную разницу, предпочтительным является
вариант с наибольшей площадью, чтобы в дальнейшем можно было поселить новых верующих.
Первая строка ввода содержит два целых числа `N` и `M` (`1 <= N, M <= 200`) - размеры поселения.
Далее следует `N` строк, содержащих `M` символов (прописные латинские буквы и символ ``'.'``) - размещение жителей
разных религий в поселении. Символ ``'.'`` означает пустое место в поселении, буквы - место жительства человека с этой религией.
Вывести для каждой религии строку, содержащую обозначение этой религии и координаты для епархии этой религии. Результаты
нужно выводить в порядке возрастания обозначений этой религии. Если существует несколько вариантов для координат епархии
с максимальным превышением количества верующих этой религии над другими и имеющих максимальную площадь, то
можно вывести любой вариант из них.
```sample Пример ввода
3 6
.B..BZ
BABBAZ
ZB..ZZ
```
```sample Пример вывода
A 2 2 2 2
B 1 1 3 4
Z 1 6 3 6
```
I. Ледяное озеро
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вся вода на поверхности Марса находится в замороженном состоянии.
Для упрощения доступа к воде все подземные поселения на Марсе имеют
выходы на замерзшее озеро.
Для передвижения по ледяному озеру
на поверхности были вморожены кубические блоки,
от которых нужно оттолкнуться для начала движения
(возможно отталкивание вбок).
От выхода из поселения можно начать движение в любом направлении.
Лед очень гладкий, поэтому остановиться можно, только уперевшись
в грань блока или край озера или достигнув выхода какого-либо поселения.
Напишите программу, которая рассчитает маршрут движения от одного поселения
до другого, используя минимальное количество отталкиваний.
Первая строка вода содержит два целых числа `N` и `M` (`3 <= N, M <= 200`) - размеры озера.
Далее следует `N` строк, содержащих по `M` символов. Символ ``'.'`` означает
гладкую поверхность озера, символ ``'#'`` - блок, ``'S'`` - выход стартового поселения,
``'E'`` - выход поселения, в которое нужно добраться. Гарантируется, что символы
``'S'`` и ``'E'`` встречаются ровно 1 раз.
Вывести одно целое число - минимальное количество отталкиваний при путешествии из одного поселения в другое.
Если достигнуть конечного выхода нельзя, то вывести -1.
```sample Пример ввода 1
6 8
........
...S..#.
..E.....
.#......
.....#..
........
```
```sample Пример вывода 1
4
```
Пояснение к примеру: сначала нужно скользить направо, затем до упора вниз, налево и вверх. Получается 4 отталкивания - от выхода стартового поселения и 3 блоков.
Если при первом отталкивании достичь берега озера, то далее можно будет
останавливаться только в углах озера.
J. Игра
Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На Марсе школьники играют в следующую игру. Три фишки ставятся на прямой в позиции с целыми координатами.
Игрок, делающий очередной ход, выбирает одну из крайних фишек слева или справа и ставит её между двумя
другими в точку с целыми координатами. Если игрок не может сделать ход по этим правилам, то он проигрывает.
Первая строка ввода содержит три целых числа `A`, `B` и `C` (`0 <= A < B < C <=10^6`) - координаты фишек в начальной позиции.
Вывести 1, если выиграет игрок, делающий первый ход, иначе вывести 2.
```sample Пример ввода 1
1 5 10
```
```sample Пример вывода 1
1
```
Пояснение к примеру: первый игрок переставляет правую фишку в точку с координатой 2. Второй игрок может
сделать только ход левой фишкой в точку с координатой 3 или 4. Следующим ходом первый игрок закрывает последнюю свободную позицию между фишками.
Второй игрок не может сделать ход и проигрывает.
```sample Пример ввода 2
1 2 5
```
```sample Пример вывода 2
2
```
K. Пещера
Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (1)
В пещере на Марсе необходимо проложить канал для связи между поселениями.
За миллионы лет на потолке пещеры выросли сталактиты, а на полу - сталагмиты.
Чтобы проложить канал связи, нужно пробить на некоторой высоте эти образования. Высота туннеля для канала равна 1.
Напишите программу, вычисляющую минимальное количество сталактитов и сталагмитов, которые нужно пробить
при прокладке канала.
Первая строка ввода содержит два целых числа - высота пещеры `H` (`2 <= H <= 500000`) и количество сталактитов и сталагмитов `N` (`1 <= N <= 500000`).
Вторая строка ввода содержит `N` целых чисел - длины сталактитов от 1 до `H-1`.
Третья строка ввода содержит `N` целых чисел - длины сталагмитов от 1 до `H-1`.
Вывести два целых числа - минимальное количество пробиваемых при прокладке канала сталактитов и сталагмитов и количество уровней (целых значений высот), на которых
данный минимум достигается.
```sample Пример ввода
5 7
3 2 4 4 3 2 3
1 4 2 3 3 3 3
```
```sample Пример вывода
7 2
```
Пояснение к примеру:
Расположение сталактитов и сталагмитов показано на рисунке. Если пробивать туннель для канала на уровне 4, то потребуется пробить 8 образований, минимальное количество
достигается на уровнях 1 и 5.
L*. Путешествие
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Том отправляется в путешествие по Марсу, но во время такой поездки важно оставаться на связи со спасательными службами. Поэтому весь маршрут путешествия должен проходить не далее `d` км от какой-нибудь вышки связи.
Первая строка ввода содержит одно число `K` (`1 <= K <= 100`) - количество тестов.
Каждый тест содержит в первой строке два целых числа - максимальное расстояние от вышки `d` (`1 <= d <= 1000`) и
и количество вышек `N` (`1 <= N <= 100`). Далее следует строка с координатами стартовой точки путешествия.
Далее следует строка с координатами конечной точки путешествия. Далее следует `N` строк с координатами вышек. Все координаты целые в диапазоне от 1 до 1000. Все пары координат различны. Стартовая точка находится не далее `d` км от одной из вышек. Размером вышек пренебречь - можно проезжать через точку, где находится вышка.
Для каждого теста вывести строку содержащую одно число - минимальную длину маршрута с точностью `10^-6` или -1, если безопасно добраться до конечной точки невозможно.
```sample Пример ввода
2
2 3
1 1
8 2
2 2
4 4
7 3
1 20
1 1
1000 1000
10 10
```
```sample Пример вывода
7.232241
-1
```
Начало
Соревнования
Аналитическое решение уравнений, неравенств, систем уравнений