Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики
(Вінницька область)
4 лютого 2017 р.

Задача Tree. По дорозі додому Маруся знайшла ціле число N, що не перевищує за абсолютним значенням 10¹². Розповіла про свою знахідку брату і він запропонував  просту задачу - записати  три різних числа, добуток яких дорівнює N.

Технічні умови. Програма Tree зчитує з пристрою стандартного введення єдине ціле число N, що не перевищує 10¹² за абсолютним значенням. Програма виводить на пристрій стандартного виведення три цілих числа, кожне з яких не перевищує 10¹² за абсолютним значенням, що задовольняють умові задачі. Якщо таких чисел не існує, виведіть три нулі, якщо розв’язків кілька – виведіть будь-який.

Приклад

Задача Physics. Є 𝑁 стовпчиків, утворених кубиками: 1-й стовпчик являє собою 𝑎₁ поставлених один на іншого кубиків, 2-й — 𝑎₂ кубиків, тощо. Усi цi кубики однакові. Все це разом узяте акуратно нахиляють праворуч — так, що деякі з кубиків зісковзують зі своїх стовпчиків i сповзають у правіші:

Вважаємо, що кубики не можуть обертатися навколо своїх ребер чи «провалюватися», тобто кубики не перекидаються, а лише зміщуються на правіші позиції. Напишіть програму, яка за початковою конфігурацією кубиків знаходитиме кінцеву, тобто кількість кубиків у кожному стовпчику та кількість кубиків у кожному рядку після того, як процес припиниться).

Технічні умови. Програма Physics читає з пристрою стандартного введення (клавіатури) число 𝑁 (2 <= 𝑁 <= 123456) - кількість стовпчиків, далі в тому ж  рядку через пропуски 𝑁 натуральних чисел 𝑎1, 𝑎2, . . . , 𝑎𝑁 — кількість кубиків 1-му, 2-му, . . . , 𝑁-му стовпчиках (злiва направо). Кожне з цих чисел у межах 1 ≤ 𝑎_i ≤ 123456. Програма виводить на пристрій стандартного виведення (екран)  в одному рядку через пропуски кінцеві кількості кубиків по стовпчиках (зліва направо) і кінцеві кількості кубиків по рядках (усім непорожнім, знизу догори). Ні кількість стовпчиків, ні кількість рядків виводити не треба.

Приклади:

Задача Palway. Задано квадратну таблицю n × n, що складається з натуральних чисел. Роз­гля­да­ти­ме­мо шля­­­хи з лі­­­вої верхньої комірки таблиці у праву нижню, які до­ві­льним чи­ном ідуть по ко­мір­ках таблиці праворуч та донизу (але ніколи ліворуч або вгору). Уз­довж кож­ного такого шляху розташовано 2n - 1 число. Якщо для пев­ного шляху даний набір чисел є «симетрич­ним», тобто читається у зворот­но­му порядку так само, як і у прямому, називати­ме­мо вибраний шлях па­лін­дро­міч­ним. За заданою таблицею встановіть загальну кількість на ній палін­дро­міч­них шляхів.

Технічні умови. Програма Palway читає з пристрою стандартного введення ціле число n (2 <= n <= 100) – розмір таблиці. У наступних n рядках файлу записано по n нату­ра­ль­них чисел, що не перевищують 10 000 та задають таблицю. Програма виводить на пристрій стандартного виведення єдине число - остачу від ділення на 101 кі­ль­кості паліндромічних шляхів на заданій таблиці.

Приклади

Коментар

У першому прикладі є чотири паліндромічних шляхи:

1. праворуч — праворуч — донизу — донизу (7–10–5–10–7);
2. праворуч — донизу — праворуч — донизу (7–10–8–10–7);
3. донизу — праворуч — донизу — праворуч (7–5–8–5–7);
4. донизу — донизу — праворуч — праворуч (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 <= 10⁹) - розміри дошки уздовж осі X і осі Y відповідно та x, y (1 <= x <= N; 1 <= y <= M) - координати стартової позиції черепашки. Програма виводить на пристрій стандартного виведення єдине число - кількість клітинок, відвіданих черепашкою.

Приклади