#111474

Числа и цифры

Темы: [Простые числа и разложение на множители]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2012, Задача B ]

Дано натуральное число N. Требуется написать программу, которая находит такое минимальное число M, произведение цифр которого равно N.

Входные данные

Вводится целое число N (1 ≤ N ≤ 2·10⁶) .

Выходные данные

Выведите на экран одно число M ≥ 10 или фразу «No solution». Число M должно начинаться со значащей цифры (не с нуля).

Примеры тестов

Входные данные

Выходные данные

Входные данные

Выходные данные

#111475

Обмен королей (O)

Темы: [Обход в ширину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2012, Задача D ]

В Шахматной Стране всегда пользовались популярностью различные спортивные соревнования: ферзебол, рокировочная борьба, эндшпилевые бега. Но наибольшую популярность в этом году получила спортивная игра «обмен королей».

Суть её заключается в следующем. Двух королей (белого и чёрного) ставят на прямоугольное шахматное поле, некоторые клетки которого отмечены как недостижимые. По правилам игры короли делают ходы по очереди (сначала белый, а затем чёрный), не наступая на недостижимые клетки. Игра считается успешно законченной, если черный и белый короли поменялись местами. В соревновании побеждает та пара королей, которая смогла поменяться местами за минимальное количество ходов.

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

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

Входные данные

В первой строке входных данных даны целые числа N и M (1 ≤ N, M ≤ 8) — размеры доски по вертикали и по горизонтали, соответственно. В следующих N строках даны M символов — состояние доски в начале игры. Символ «.» обозначает пустую клетку, символ «*» — недостижимую клетку, символ «W» — белого короля, «B» — черного короля. Гарантируется, что символы «W» и «B» встречаются на поле ровно по одному разу, и короли не находятся в соседних клетках изначально.

Выходные данные

В выходной файл необходимо вывести минимальное количество ходов, которое потребуется для того, чтобы белый король поменялся местами с чёрным. В случае, если поменять королей местами невозможно, требуется вывести «Impossible» без кавычек.

Примеры тестов

Входные данные

4 3
*.*
W.B
...
*.*

Выходные данные

Входные данные

2 3
W..
..B

Выходные данные

Impossible

Примечание

Последовательность ходов, необходимая для обмена королей в первом тесте, приведена на рисунке:

$\text{[math]}$

#111985

Информатическая сила

Темы: [Арифметические алгоритмы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 7-9 классы, Информатическая сила ] [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 10-11 классы, Информатическая сила ]

В одной школе издавна велись соревнования в информатической силе между классами одной параллели. По введённой учителями шкале информатическая сила класса — это суммарное количество задач, решённых всеми школьниками этого класса на последней районной олимпиаде. Соревновательный дух школы весьма высок, а значит, каждый участник решил хотя бы одну задачу.

В школьной летописи сохранились информатические силы двух классов, $A$ и $B$, а также количество задач на олимпиаде $N$. Завучу, нашедшему летопись, очень хочется узнать, могло ли быть в первом классе больше учеников, чем во втором.

Напишите программу, которая определит, могло ли быть учеников в классе с информатической силой $A$ больше, чем учеников в классе с информатической силой $B$.

Входные данные

Вводятся три целых числа, каждое в своей строке — $A$, $B$, $N$ ($0 \le A, B \le 10 000, 1 \le N \le 10 000$).

Выходные данные

Выведите «Yes», если в первом классе могло быть больше учеников, чем во втором, и «No», в противном случае.

Примечания

Тесты к этой задаче состоят из трех групп.

Тесты 1 – 3. Тесты из условия, оцениваются в ноль баллов.
Тесты 4 – 17. В тестах этой группы $0 \le A, B \le 10, 1 \le N \le 10$. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 18 – 30. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 70 баллов, баллы ставятся только при прохождении всех тестов группы.

Примеры

Входные данные

60
30
4

Выходные данные

Yes

Входные данные

30
30
1

Выходные данные

No

Входные данные

30
150
4

Выходные данные

No

#111986

Олимпийский огонь

Темы: [Цикл for]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 7-9 классы, Олимпийский огонь ]

В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из $N$ этапов, каждый длиной $a_i$ километров ($1 \le i \le N$). У организаторов имеется большое количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении $K$ километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.

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

Входные данные

В первой строке заданы два натуральных числа $N$ и $K$ ($N \le 100, K \le 10^6$ ).

Во второй строке заданы $N$ натуральных чисел $a_i (a_i \le 10^6 )$.

Выходные данные

В первой строке выведите одно натуральное число $F$ — количество факелов, которое понадобится организаторам для проведения эстафеты олимпийского огня.

Примечания

В данной задаче баллы за каждый тест начисляются независимо от прохождения остальных тестов и суммируются.

Примеры

Входные данные

4 3
3 5 4 1

Выходные данные

Входные данные

10 1
1 2 3 4 5 6 7 8 9 10

Выходные данные

#111987

Шахматные клетки

Темы: [Цикл for]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 7-9 классы, Шахматные клетки ]

Недавно Петя услышал на шахматном кружке о мегашахматах.

Поле для мегашахмат — это разделённый на клетки прямоугольник, в котором каждый горизонтальный ряд клеток имеет свою высоту, а каждый вертикальный столбец — свою ширину. Всего на поле n рядов и m столбцов клеток, высота i-го ряда составляет a_i сантиметров, а ширина j-го столбца — b_j сантиметров. Столбцы нумеруются слева направо, а строки — снизу вверх. Клетки покрашены в чёрный и белый цвета в шахматном порядке, левая нижняя клетка поля черная. Это значит, что соседи каждой клетки по вертикали и горизонтали отличаются от нее по цвету.

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

Входные данные

В первой строке вводятся два целых числа n и m — количества рядов и столбцов клеток на поле для мегашахмат (1 ≤ n, m ≤ 10⁵).

Во второй строке вводится n целых чисел a_i — высоты рядов клеток в сантиметрах (1 ≤ a_i ≤ 100).

В третьей строке вводится m целых чисел b_j — ширины столбцов клеток в сантиметрах (1 ≤ b_j ≤ 100).

Выходные данные

Выведите два числа в одной строке: площадь всех чёрных клеток и площадь всех белых клеток в квадратных сантиметрах на поле.

Примеры тестов

Входные данные

8 8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Выходные данные

32 32

Входные данные

2 3
3 2
3 2 1

Выходные данные

16 14

Примечание

Второй тест из условия соответствует рисунку.

Тесты к этой задаче состоят из трех групп. Если решение не проходит какую-либо группу тестов, следующие группы не проверяются.

Тесты 1 – 2. Тесты из условия, оцениваются в ноль баллов.
Тесты 3 – 20. В тестах этой группы 1 ≤ n, m ≤ 10³, 1 ≤ a_i, b_i ≤ 10. Эта группа оценивается в 40 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 21 – 32. В тестах этой группы дополнительные ограничения отсутствуют. Прохождение тестов из этой группы оценивается из 60 баллов, баллы начисляются за каждый тест независимо от прохождения остальных тестов и суммируются.