Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики
(Вінницька область)
4 лютого 2017 р.
Задача Tree. По дорозі додому Маруся знайшла ціле число N, що не перевищує за абсолютним значенням 1012. Розповіла про свою знахідку брату і він запропонував просту задачу - записати три різних числа, добуток яких дорівнює N. (N=(-1)*1*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
7 10 5
5 8 10
8 5 7 | 4 |
2
| 6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 | 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 |
