Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики
(Вінницька область)
4 лютого 2017 р.
Задача Tree. По дорозі додому Маруся знайшла ціле число N, що не перевищує за абсолютним значенням 1012. Розповіла про свою знахідку брату і він запропонував просту задачу - записати три різних числа, добуток яких дорівнює N.
Технічні умови. Програма Tree зчитує з пристрою стандартного введення єдине ціле число N, що не перевищує 1012 за абсолютним значенням. Програма виводить на пристрій стандартного виведення три цілих числа, кожне з яких не перевищує 1012 за абсолютним значенням, що задовольняють умові задачі. Якщо таких чисел не існує, виведіть три нулі, якщо розв’язків кілька – виведіть будь-який.
Приклад
| Введення 24 |
Виведення 2 3 4 |
| Введення 72 |
Виведення 3 4 6 |
Задача Physics. Є 𝑁 стовпчиків, утворених кубиками: 1-й стовпчик являє собою 𝑎1 поставлених один на іншого кубиків, 2-й — 𝑎2 кубиків, тощо. Усi цi кубики однакові. Все це разом узяте акуратно нахиляють праворуч — так, що деякі з кубиків зісковзують зі своїх стовпчиків i сповзають у правіші:
Вважаємо, що кубики не можуть обертатися навколо своїх ребер чи «провалюватися», тобто кубики не перекидаються, а лише зміщуються на правіші позиції. Напишіть програму, яка за початковою конфігурацією кубиків знаходитиме кінцеву, тобто кількість кубиків у кожному стовпчику та кількість кубиків у кожному рядку після того, як процес припиниться).
Технічні умови. Програма Physics читає з пристрою стандартного введення (клавіатури) число 𝑁 (2 <= 𝑁 <= 123456) - кількість стовпчиків, далі в тому ж рядку через пропуски 𝑁 натуральних чисел 𝑎1, 𝑎2, . . . , 𝑎𝑁 — кількість кубиків 1-му, 2-му, . . . , 𝑁-му стовпчиках (злiва направо). Кожне з цих чисел у межах 1 ≤ 𝑎i ≤ 123456. Програма виводить на пристрій стандартного виведення (екран) в одному рядку через пропуски кінцеві кількості кубиків по стовпчиках (зліва направо) і кінцеві кількості кубиків по рядках (усім непорожнім, знизу догори). Ні кількість стовпчиків, ні кількість рядків виводити не треба.
Приклади:
| Введення 4 3 2 1 2 |
Виведення 1 2 2 3 4 3 1 |
(цей приклад відповідає рисунку) |
| Введення 7 4 1 1 1 2 1 1 |
Виведення 1 1 1 1 1 2 4 7 2 1 1 |
Задача Palway. Задано квадратну таблицю n × n, що складається з натуральних чисел. Розглядатимемо шляхи з лівої верхньої комірки таблиці у праву нижню, які довільним чином ідуть по комірках таблиці праворуч та донизу (але ніколи ліворуч або вгору). Уздовж кожного такого шляху розташовано 2n - 1 число. Якщо для певного шляху даний набір чисел є «симетричним», тобто читається у зворотному порядку так само, як і у прямому, називатимемо вибраний шлях паліндромічним. За заданою таблицею встановіть загальну кількість на ній паліндромічних шляхів.
Технічні умови. Програма Palway читає з пристрою стандартного введення ціле число n (2 <= n <= 100) – розмір таблиці. У наступних n рядках файлу записано по n натуральних чисел, що не перевищують 10 000 та задають таблицю. Програма виводить на пристрій стандартного виведення єдине число - остачу від ділення на 101 кількості паліндромічних шляхів на заданій таблиці.
|
№ |
Введення |
Виведення |
|---|---|---|
|
1 |
3 |
4 |
|
2 |
6 |
50 |
Приклади
Коментар
У першому прикладі є чотири паліндромічних шляхи:
- праворуч — праворуч — донизу — донизу (7–10–5–10–7);
- праворуч — донизу — праворуч — донизу (7–10–8–10–7);
- донизу — праворуч — донизу — праворуч (7–5–8–5–7);
- донизу — донизу — праворуч — праворуч (7–5–8–5–7).
У другому прикладі кожен з 252 можливих шляхів є паліндромічним, тож за умовою слід вивести остачу від ділення 252 на 101 — число 50.
Задача Turtle. Черепашка знаходиться на полі в клітинку розміром N х M в клітинці з координатами (x, y) і дивиться вздовж додатного напрямку осі x. Черепашка починає йти по полю за таким алгоритмом:
- пройти на одну клітинку вперед, повернути на 90° вправо.
- пройти на одну клітинку вперед, повернути на 90° вправо.
- пройти на дві клітинки вперед, повернути на 90° вправо.
- пройти на дві клітинки вперед, повернути на 90° вправо.
- пройти на три клітинки вперед, повернути на 90° вправо.
- пройти на три клітини вперед, повернути на 90° вправо.
- пройти на чотири клітини вперед, повернути на 90° вправо.
І так далі...
Рух триває до тих пір, поки черепашка не вийде за межі поля. Напишіть програму, яка порахує кількість відвіданих черепашкою клітинок.
Технічні умови. Програма Turtle читає з пристрою стандартного введення 4 натуральних числа N, M (1 <= N, M <= 109) - розміри дошки уздовж осі X і осі Y відповідно та x, y (1 <= x <= N; 1 <= y <= M) - координати стартової позиції черепашки. Програма виводить на пристрій стандартного виведення єдине число - кількість клітинок, відвіданих черепашкою.
Приклади
| Введення | Виведення |
| 7 6 3 4 2 2 1 1 2 2 1 2 |
36 2 4 |