printЗадачи онлайн-тура отборочных командных соревнований школьников

print1. Пароль

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

Для разблокировки мобильного телефона на экран выводится `K` различных символов-картинок по кругу. Пользователь должен провести по последовательности из `L` символов, не отрывая пальца от экрана. Чтобы последовательность-пароль нельзя было определить по следам на стекле, символы выводятся каждый раз в разном порядке. Символ может встречаться в пароле несколько раз, но не может встречаться в пароле подряд, так как ввод такой последовательности невозможен. Например, допускается пароль XOX, но не пароли XOO, OOX или OOO.
Напишите программу, вычисляющую количество различных паролей длины `L`.
Первая строка ввода содержит два целых числа – количество символов `K` (`2\ ≤\ K\ ≤\ 20`) и длина пароля `L` (`1\ ≤\ L\ ≤\ 10`).
Вывести одно целое число – количество различных паролей длины `L` из `K` символов, в которых нет одинаковых символов подряд.

Пример ввода 1

3 3

Пример вывода 1

12

Пример ввода 2

4 3

Пример вывода 2

36
Пояснение к примеру 1: возможны следующие 12 паролей из трех букв длины 3: aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc.

print2. Обмен

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

Петя коллекционирует наклейки с героями комиксов, а Маша – наклейки с феями. В магазине за покупку свыше некоторой суммы выдают запечатанный пакет с разными наклейками. У Пети уже скопилось `X` ненужных ему наклеек с феями, а у Маши – `Y` наклеек с супергероями. Они договорись поменяться наклейками  – за каждые `A` наклеек с феями Петя сможет получить `B` наклеек с супергероями.
Напишите программу, которая вычисляет, сколько наклеек с супергероями сможет выменять Петя.
Первая строка ввода содержит четыре целых числа – количество наклеек `X` и `Y` (`1\ ≤\ X,\ Y\ ≤\ 10^9`) и обменный курс `A` и `B` (`1\ ≤\ A,\ B\ ≤\ 10,\ "НОД"(A,B)=1`).
Вывести одно целое число – количество наклеек с супергероями, которые сможет выменять Петя.

Пример ввода

10 7 2 3

Пример вывода

6
Пояснение к примеру: Петя отдает 4 наклейки с феями и получает 6 наклеек с супергероями.

print3. Осторожно!

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

Когда выпал первый снег, Ральф скатал несколько больших снежных комов и сделал из них гигантскую скульптуру. Но вскоре потеплело, и снег начал таять. Ральф хочет огородить предупредительными знаками часть двора, на которую возможно падение снега из разрушающейся скульптуры.
Напишите программу, которая определяет, какую часть двора необходимо оградить.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 100`). Следующие `N` строк содержат по `M` символов '#' и '.' – вид скульптуры сбоку. Символ '#' показывает расположение снежного кома, а символ '.' – пустое место. Изображение содержит как минимум один символ '#'.
Вывести два целых числа – номера самой левой позиции и самой правой позиции, где возможно падение снега.

Пример ввода 1

5 7
.......
...#...
..##.#.
...###.
...#.#.

Пример вывода 1

3 6

Пример ввода 2

1 3
.#.

Пример вывода 2

2 2

print4. Дележ сада

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

Траляля и Труляля поссорились и решили поделить дом и сад вокруг дома пополам. Дом имеет прямоугольную форму и расположен на прямоугольном участке. Остальную часть участка занимает сад. Стены дома параллельны границам участка и осям координат.
Разделить дом Траляля и Труляля смогли легко, но сад имеет более сложную форму, поэтому напишите программу, которая определяет координату `X` вертикальной линии, которая поделит площадь сада пополам.
Первая строка ввода содержит четыре целых числа `X_1`, `Y_1`, `X_2`, `Y_2` – координаты противоложных углов участка, на котором расположены дом и сад. Вторая строка ввода содержит четыре целых числа `X_3`, `Y_3`, `X_4`, `Y_4` – координаты противоложных углов дома (`0\ ≤\ X_1\ ≤\ X_3\ <\ X_4\ ≤\ X_2\ ≤\ 1000`, `0\ ≤\ Y_1\ ≤\ Y_3\ <\ Y_4\ ≤\ Y_2\ ≤\ 1000`, площадь сада не равна нулю).
Вывести одно число – координату `X` вертикальной линии, которая поделит площадь сада пополам с точностью `10^{-6}`.

Пример ввода

2 1 7 5
3 2 5 4

Пример вывода

5.000000

print5. Завтрак

Ограничения: время – 300ms/600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

39491.jpg
`N` домиков стоят в ряд на пляже. Каждое утро две машины развозят еду проживающим в домиках. Одна машина едет с левой стороны, другая – с правой. Когда машина подъезжает к домику, люди, проживающие в нем, выходят и забирают свой завтрак. Выдача одной порции еды занимает 1 единицу времени, переезд между соседними домиками – 5 единиц времени. Количество проживающих в домиках может различаться, поэтому, если разложить порции в машины поровну, то еда в одной из машин может закончиться раньше и проживающим нужно будет дожидаться другую машину.
Напишите программу, которая поможет определить, сколько порций нужно загрузить в каждую машину, чтобы раздача еды завершилась как можно быстрее.
Первая строка ввода содержит одно целое число `N` – количество домиков (`1\ ≤\ N\ ≤\ 10^5`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 0 до `10^4` – количество проживающих в домиках слева направо.
Вывести два целых числа – количество порций, которые нужно загрузить в левую и в правую машину. Если последняя порция может быть выдана как левой, так и правой машиной без увеличения общей продолжительности раздачи еды, то её нужно погрузить в левую машину.

Пример ввода

4
1 1 7 5

Пример вывода

5 9
Пояснение к примеру:
Левая машина выдает 1 порцию еды в 1-м домике, проезжает ко 2-му домику, выдает 1 порцию еды, проезжает ко 3-му домику и выдает там 3 порции, затрачивая на все действия 1+5+1+5+3=15 единиц времени.
Правая машина выдает 5 порций еды в 4-м домике, затем проезжает ко 3-му домику и выдает там 4 порции, затрачивая на все действия 5+5+4=14 единиц времени.
Таким образом раздача еды завершается за 15 единиц времени.

print6. Молекулярный синтезатор

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

За 60 секунд до катастрофы Том Томсон погрузил ресурсы в спасательную шлюпку и отчалил от корабля. Консервированный томатный суп закончился за несколько дней до приземления на неизвестную планету. К счастью на поверхности планеты Том смог найти химикаты, содержащие углерод (C), водород (H), кислород (O), азот (N) и другие химические элементы (обозначаемые остальными буквами латинского алфавита), а шлюпка была оборудована молекулярным синтезатором, который может, переставляя атомы, получить продукт с любой заданной химической формулой.
Напишите программу, вычисляющую количество (в молях) продукта с заданной химической формулой, которое можно получить из одного моля химиката с заданной формулой.
Первая строка ввода содержит формулу химиката, вторая строка – формулу изготавливаемого продукта. Длины обеих строк от 1 до 2500 символов, формула содержит прописные буквы латинского алфавита от A до Z – обозначения атомов, после которых может идти число от 1 до 1000 – количество атомов. Если число не указано, то подразумевается, что количество атомов равно 1. Атомы могут указываться несколько раз в химической формуле, тогда их количество суммируется.
Вывести одно число – количество продукта в молях, которое можно изготовить из одного моля химиката с точностью `10^{-6}`.

Пример ввода

C12H22O11
C2H5OH

Пример вывода

3.666667

print7. Сортировка

Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

Задан набор из `M` операций обмена `(a_1,b_1),\ …,\ (a_M,\ b_M)` над массивом из `N` чисел `X_1,\ …,\ X_N`. Необходимо отсортировать массив в неубывающем порядке, используя эти операции обмена. Каждая пара `(a_i,\ b_i)` означает, что можно поменять местами элементы массива `X_{a_i}` и `X_{b_i}`. Операции обмена можно применять неограниченное количество раз и в произвольном порядке.
Напишите программу, определяющую, можно ли упорядочить некоторый массив, используя заданный набор операций обмена.
Первая строка ввода содержит два целых числа – размер массива `N` (`2\ ≤\ N\ ≤\ 100000`) и количество операций обмена `M` (`1\ ≤\ M\ ≤\ min(200000,(N*(N-1))/2)`). Далее следует `M` строк, содержащих по два целых числа `a_i,\ b_i` (`1\ ≤\ a_i\ <\ b_i\ ≤\ N`) – описание операции обмена. Далее следует строка, содержащая одно целое число `K` (`1\ ≤\ K\ ≤\ 10`) – количество массивов, которые нужно отсортировать. Далее следует `K` строк, в каждой строке по `N` целых чисел в диапазоне от 0 до `10^9` - массивы для сортировки.
Вывести `K` строк, для каждого массива вывести на соответствующей строке сообщение YES, если массив можно отсортировать с помощью заданного набора операций обмена, иначе вывести сообщение NO.

Пример ввода

4 2
1 2
3 4
2
4 2 8 4
1 3 2 4

Пример вывода

YES
NO

print8. Симметричный сигнал

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Посылки Темы Где Обсудить (0)

Сигнал из космоса, полученный Элли, имеет странную симметрию. Возможно анализ этой симметрии позволит расшифровать сигнал. Сигнал является длинной последовательностью из цифр от 0 до 9. Элли заметила, что сигнал можно разбить на `k` подстрок `s_1,\ s_2,\ …,\ s_k` таким образом, чтобы `s_i`=`s_{k+1-i}` для всех `i` от 1 до `k`. Например, сигнал 714471 можно представить как одну подстроку, три подстроки 71,44,71 или четыре подстроки 71,4,4,71.
Напишите программу, определяющую, на какое максимальное количество подстрок можно разбить последовательность цифр, чтобы эта последовательность подстрок была симметричной.
Первая строка ввода содержит последовательность из цифр длиной от 1 до `10^6` цифр.
Вывести одно целое число – максимальное количество подстрок в разбиении.

Пример ввода

714471

Пример вывода

4
loading