Задачи личного первенства по спортивному программированию
A. Степени 3
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Найти разложение натурального числа `N` на слагаемые, являющиеся степенями 3, включая `3^0`.
Например, `N=12` можно представить как `3^2+3^1`, `3^2+3^0+3^0+3^0` или
`3^1+3^1+3^1+3^1`.
Ввод содержит целое число `N` (`1 <= N <= 10^9`).
Вывести одно целое число -- минимальное количество слагаемых при разложении `N`.
```sample Пример ввода
12
```
```sample Пример вывода
2
```
B. Родственные числа
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Будем называть два натуральных числа `A` и `B` родственными, если существуют два натуральных числа `X` и `Y` (`X>=1, Y>=1`) таких, что
`A^X=B^Y`.
Например, 4 и 8 являются родственными, так как `4^3=64`, `8^2=64`.
Ввод содержит два натуральных числа `A`, `B` (`1 <= A,B <= 10^9`).
Вывести два наименьших натуральных числа `X` и `Y`, для которых `A^X=B^Y`, иначе вывести ``NO``.
```sample Пример ввода 1
4 8
```
```sample Пример вывода 1
3 2
```
```sample Пример ввода 2
2 5
```
```sample Пример вывода 2
NO
```
C. Различные числа
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана последовательность из `N` целых чисел. К последовательности можно применять следующую операцию.
Выбрать подпоследовательность и увеличить все её элементы на 1.
Подпоследовательность -- это элементы последовательности с номерами `k_1, k_2, ..., k_m`, где
`m` -- длина подпоследовательности (`1<=m<=N`), `1<=k_1<k_2<...<k_m<=N`.
Необходимо сделать все числа в последовательности различными за наименьшее количество операций.
Например, в последовательности 1,2,1,2 можно сделать все числа различными за две операции.
Сначала нужно увеличить элементы с номерами 2,3,4, получив последовательность 1,3,2,3, затем
увеличить элементы с номерами 2, получив последовательность 1,4,2,3, в которой нет одинаковых элементов.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 10^5`).
Вторая строка ввода содержит `N` целых в диапазоне от 1 до `10^6`.
Вывести одно целое число -- наименьшее количество операций, чтобы сделать все числа различными
в заданной последовательности.
```sample Пример ввода
4
1 2 1 2
```
```sample Пример вывода
2
```
D. Максимальное число
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана последовательность из `N` натуральных чисел. Необходимо переставить элементы этой последовательности так,
чтобы число, образованное при записи этих элементов без пробелов, было максимальным.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 10^5`).
Вторая строка ввода содержит `N` целых в диапазоне от 1 до `10^6`.
Вывести элементы последовательности в порядке, при котором образуемое после удаления пробелов число будет максимальным.
Если существует несколько вариантов, то можно вывести любой из них.
```sample Пример ввода
4
75 12 8 82
```
```sample Пример вывода
8 82 75 12
```
E. Перестановка
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Перестановкой называется последовательность чисел от 1 до `N`, в которой каждое число встречается ровно 1 раз.
Найти перестановку из `N` элементов, такую что последовательные числа в ней не находятся рядом, т.е. `|P_i-P_{i+1}|>=2` для всех `i in 1...n-1`.
Ввод содержит одно целое число `N` (`2 <= N <= 10^5`).
Вывести перестановку из чисел от 1 до `N`, удовлетворяющую требованиям. Можно вывести любой из вариантов. Если такой перестановки не существует, вывести одно число `-1`.
```sample Пример ввода 1
5
```
```sample Пример вывода 1
1 4 2 5 3
```
```sample Пример ввода 2
2
```
```sample Пример вывода 2
-1
```
F. Q-zar
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В игре Q-zar игроки делятся на две команды. Игроки первой команды имеют номера с 1 по 4, второй -- с 5 по 8.
Попадание в игрока другой команды приносит команде 10 очков. Если стрелявший игрок уже попадал в кого-нибудь в течении 10 секунд,
то начисляются дополнительные 5 баллов.
Напишите программу, которая подсчитает по протоколу игры количество очков, начисленных каждой команде.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 100`) -- количество попаданий.
Далее следует `N` строк, в каждой строке три целых числа -- время попадания `t_i` (`0 <= t_i <=1000`, `t_i<t_{i+1}`),
номер стрелявшего игрока `a_i` и номер игрока, в которого попали, `b_i` (`1<= a_i, b_i <=8`, гарантируется, что номера `a_i` и `b_i` относятся к разным командам).
Вывести два целых числа -- количество очков, начисленных первой и второй команде.
```sample Пример ввода 1
4
5 1 5
15 1 7
21 8 1
32 8 2
```
```sample Пример вывода 1
25 20
```
```sample Пример ввода 2
4
10 2 5
15 1 7
20 2 7
25 2 5
```
```sample Пример вывода 2
50 0
```
Пояснение к примеру 2: за 1-е и 2-е попадания первая команда получает по 10 очков, за 3-е и 4-е -- по 15 очков, так как попадания были в
течении 10 секунд после предыдущего выстрела игрока с номером 2.
G. Фабрика клонов
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Джедай находится в огромном зале на фабрике клонов и хочет добраться до таинственной двери в противоположном углу зала.
По залу в четырех направлениях на разной высоте летают платформы. В момент, когда платформы пролетают друг над другом, можно перескочить
с одной платформы на другую. На стенах зала находятся порталы, при достижении стены зала платформа вместе с
грузом на ней перемещается к противоположной стене.
Первая строка содержит два целых числа `R, C` (`2 <= R,C <= 50`) -- размеры зала.
Далее следует `R` строк, содержащих `C` символов -- вид зала сверху в начальный момент времени `t=0`. Символ ``'.'`` означает, что в этой клетке нет платформы.
Символы ``'v', '^', '<', '>'`` показывают наличие платформы и направление её движения.
Джедай находится в левом верхнем углу зала, гарантируется что в этой клетке находится платформа.
Вывести одно целое число -- минимальное время до достижения правого нижнего угла зала.
Если достижение правого нижнего угла невозможно, то вывести `-1`.
```sample Пример ввода 1
3 5
>^..v
...<.
.v..^
```
```sample Пример вывода 1
5
```
```sample Пример ввода 2
3 5
<....
.v...
...>.
```
```sample Пример вывода 2
31
```
```sample Пример ввода 3
2 2
><
><
```
```sample Пример вывода 3
-1
```
H. Кто хочет стать миллионером?
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В игре "Кто хочет стать миллионером?" игрок должен ответить на `n` вопросов.
Приз удваивается в каждом раунде, но сложность вопросов также возрастает. После ответа на `n`-й вопрос игра завершается.
В данном варианте игры у игрока до начала 1-го раунда уже есть приз 1$.
Обычно после прочтения вопроса игрок может выбрать одно из действий:
* забрать уже выигранный приз и завершить игру;
* ответить на вопрос, удвоить свой приз при правильном ответе и продолжить играть, или уйти ни с чем при неправильном ответе.
Игрок может оценить вероятность `p_i` правильного ответа на `i`-й вопрос.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 30`) -- количество вопросов в игре.
Вторая строка ввода содержит `N` чисел `p_i` в диапазоне от 0 до 1 -- вероятность, что игрок может ответить правильно
на `i`-й вопрос.
Вывести одно число -- ожидаемый выигрыш игрока с точностью `10^{-3}` при наилучшей стратегии игрока.
```sample Пример ввода 1
1
0.6
```
```sample Пример вывода 1
1.200
```
```sample Пример ввода 2
3
1.0 0.3 0.9
```
```sample Пример вывода 2
2.160
```
Пояснение к примеру 1: Если игрок отвечает на вопрос правильно, то с вероятностью 0.6 он получает приз 2$, но с вероятностью 0.4 он теряет всё.
Таким образом ожидаемый выигрыш игрока равен `0.6*2+0.4*0=1.2`. При выборе варианта "забрать приз" он получит 1$, поэтому
лучшей стратегией будет попытаться ответить на вопрос.
I. Идентификация гор
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Маленькая гора может казаться выше высокой горы, если высокая гора находится дальше от наблюдателя.
Маленькая гора может даже закрывать высокую гору.
Напишите программу, которая поможет определить названия видимых гор. Будем считать мир плоским, склоны всех гор имеют форму конуса
с наклоном 45 градусов, т.е. радиус каждой горы равен ее высоте. Горы могут пересекаться друг с другом, но не могут находиться внутри другой горы.
Наблюдатель находится в точке с координатами (0,0) на высоте 0.
Первая строка ввода содержит одно целое число `N` (1 <= N <= 1000) -- количество гор.
Далее следует `N` строк, каждая строка содержит три целых числа -- координаты горы `x`,`y` (`-10000 <= x, y <=10000`),
её высоту `h` (1 <= h <= 10000`) и слово из прописных латинских букв длиной не более 30 -- название горы.
Все названия уникальны. Гарантируется, что наблюдатель не попадает внутрь или на склон горы.
Вывести названия гор, видимых наблюдателю по часовой стрелке, начиная с оси `Y`. Если две горы видны в одном направлении,
то сначала вывести название более высокой горы. Названия гор, скрытых от наблюдателя другими горами, не выводить.
```sample Пример ввода 1
3
0 10000 8849 ARARAT
10000 0 5959 ANETO
0 -10000 4808 MONBLAN
```
```sample Пример вывода 1
ARARAT
ANETO
MONBLAN
```
```sample Пример ввода 2
6
8 0 5 A
9 1 5 B
9 0 5 C
9 -1 5 D
16 0 10 E
120 0 80 F
```
```sample Пример вывода 2
B
F
A
D
```
J. Раскраска графа
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дан связный неориентированный граф из `N` вершин и `N` ребер.
Между двумя вершинами может быть не более одного ребра, также ребра соединяют только различные вершины (нет петель).
Необходимо покрасить некоторые вершины в красный цвет так, чтобы каждая вершина была соединена ребрами ровно с одной красной вершиной.
Первая строка ввода содержит одно целое число `N` (`3 <= N <= 100000`) -- количество вершин в графе.
Далее следует `N` строк, каждая строка содержит два целых числа в диапазоне от 1 до `N` -- номера вершин, соединенных ребром.
Вывести одно число -- минимальное количество вершин, которые нужно покрасить в красный цвет.
Если раскрасить граф указанным способом невозможно, то вывести число `-1`.
```sample Пример ввода 1
4
1 2
2 3
3 4
4 1
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
3
1 2
2 3
3 1
```
```sample Пример вывода 2
-1
```
```sample Пример ввода 3
7
1 2
2 3
2 4
3 4
4 5
5 6
6 7
```
```sample Пример вывода 3
4
```
Пояснение к примеру 1: Нужно покрасить вершины с номерами 1 и 2.
Начало
Соревнования
Системы счисления с другим основанием