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

Для разблокировки мобильного телефона на экран выводится `K` различных символов-картинок по кругу. Пользователь должен провести по последовательности из `L` символов, не отрывая пальца от экрана. Чтобы последовательность-пароль нельзя было определить по следам на стекле, символы выводятся каждый раз в разном порядке. Символ может встречаться в пароле несколько раз, но не может встречаться в пароле подряд, так как ввод такой последовательности невозможен. Например, допускается пароль XOX, но не пароли XOO, OOX или OOO.

Напишите программу, вычисляющую количество различных паролей длины `L`.

Первая строка ввода содержит два целых числа – количество символов `K` (`2\ ≤\ K\ ≤\ 20`) и длина пароля `L` (`1\ ≤\ L\ ≤\ 10`).

Вывести одно целое число – количество различных паролей длины `L` из `K` символов, в которых нет одинаковых символов подряд.

3 3

12

4 3

36

Петя коллекционирует наклейки с героями комиксов, а Маша – наклейки с феями. В магазине за покупку свыше некоторой суммы выдают запечатанный пакет с разными наклейками. У Пети уже скопилось `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

Когда выпал первый снег, Ральф скатал несколько больших снежных комов и сделал из них гигантскую скульптуру. Но вскоре потеплело, и снег начал таять. Ральф хочет огородить предупредительными знаками часть двора, на которую возможно падение снега из разрушающейся скульптуры.

Напишите программу, которая определяет, какую часть двора необходимо оградить.

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

Вывести два целых числа – номера самой левой позиции и самой правой позиции, где возможно падение снега.

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

3 6

1 3
.#.

2 2

Траляля и Труляля поссорились и решили поделить дом и сад вокруг дома пополам. Дом имеет прямоугольную форму и расположен на прямоугольном участке. Остальную часть участка занимает сад. Стены дома параллельны границам участка и осям координат.

Разделить дом Траляля и Труляля смогли легко, но сад имеет более сложную форму, поэтому напишите программу, которая определяет координату `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

`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 единиц времени.

За 60 секунд до катастрофы Том Томсон погрузил ресурсы в спасательную шлюпку и отчалил от корабля. Консервированный томатный суп закончился за несколько дней до приземления на неизвестную планету. К счастью на поверхности планеты Том смог найти химикаты, содержащие углерод (C), водород (H), кислород (O), азот (N) и другие химические элементы (обозначаемые остальными буквами латинского алфавита), а шлюпка была оборудована молекулярным синтезатором, который может, переставляя атомы, получить продукт с любой заданной химической формулой.

Напишите программу, вычисляющую количество (в молях) продукта с заданной химической формулой, которое можно получить из одного моля химиката с заданной формулой.

Первая строка ввода содержит формулу химиката, вторая строка – формулу изготавливаемого продукта. Длины обеих строк от 1 до 2500 символов, формула содержит прописные буквы латинского алфавита от A до Z – обозначения атомов, после которых может идти число от 1 до 1000 – количество атомов. Если число не указано, то подразумевается, что количество атомов равно 1. Атомы могут указываться несколько раз в химической формуле, тогда их количество суммируется.

Вывести одно число – количество продукта в молях, которое можно изготовить из одного моля химиката с точностью `10^{-6}`.

C12H22O11
C2H5OH

3.666667

Задан набор из `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

Сигнал из космоса, полученный Элли, имеет странную симметрию. Возможно анализ этой симметрии позволит расшифровать сигнал. Сигнал является длинной последовательностью из цифр от 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