Завдання 2-го туру (Real Time) відкритої олімпіпади з
учителів України з інформатики
10.10.09
початок туру 11-00, закінчення 16-00
Задача Pal
Послідовність чисел є симетричною, якщо вона однаково читається як зліва направо, так і справа наліво. Наприклад, наступні послідовності є симетричними:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Дано послідовність чисел. Потрібно визначити, яку мінімальну кількість і яких саме чисел треба дописати в кінець цієї послідовності, щоб вона стала симетричною.
Технічні умови
Програма Pal читає з клавіатури число N — кількість елементів даної послідовності, а далі N чисел — елементи послідовності –натуральні числа від 1 до 9. 1≤N≤100. Програма виводить число M — мінімальну кількість елементів, які слід дописати до послідовності, а потім в тому ж рядку M чисел (кожне — від 1 до 9) — числа, які треба дописати до послідовності. Всі числа розділено пропусками.
|
Приклад 1
Введення 5 1 2 1 2 2 Виведення 3 1 2 1
|
Приклад 2
Введення 5 1 2 3 4 5 Виведення 4 4 3 2 1 |
Задача Rect
Дано прямокутник, довжини сторін якого є натуральними числами. На скільки квадратів (не обов’язково однакових) можна розрізати даний прямокутник? Відрізати квадрат можливо лише таким чином, щоб та частина, що залишається, утворювала знову деякий прямокутник. Квадрат, що був відрізаний на черговому кроці, більше не розрізається.
Технічні умови
Програма Rect зчитує з клавіатури числа a і b - довжини сторін (1<=a,b<=1000000000). Програма виводить на екран шукану кількість квадратів.
Приклад
| Введення | Виведення |
| 3 5 | 4 |
Задача Turtle
Виконавець «Черепашка» може виконувати наступні команди:
1) команди переміщення – F <distance> (переміститися вперед на <distance> метрів), B <distance> (переміститися назад на <distance> метрів);
2) команди зміни напряму руху – L <angle> (повернути на <angle> градусів вліво), R <angle> (повернути на <angle> градусів управо).
Напишіть програму, що визначає довжину шляху, який подолаэ черепашка після виконання заданої послідовності команд, та відстань, на яку вона переміститься з початкового положення.
Технічні умови
Програма читає з клавіатури ціле число N (0 ≤N≤1000) – кількість команд, які виконує «Черепашка». Далі програма читає з наступних N рядків по одній команді у форматі: одна з літер F, B,L, R – код команди, і через пропуск число, яке знаходиться в межах від 0 до 1000 і має не більше 2 знаків після десяткової крапки – відстань<distance> або кут<angle>. Програма виводить на екран довжину пройденого "Черепашкою" шляху і через пропуск відстань між початковим і кінцевим положенням «Черепашки», округливши до двох знаків після коми.
Приклад
| Введення | Виведення |
|
7 F 10.0 R 90.0 F 10.0 L 90.0 B 10.0 R 270.0 F 10.0 |
40.00 0.00
|
Задача Max
В Дубовецькому районі є N населених пунктів, деякі з них з’єднані дорогами з мостами, вантажопідйомність яких обмежена. З будь-якого села можна проїхати в будь-яке. Кожна дорога має 1 міст.
Дано: Для кожного села список сіл, що зв’язані з ним дорогами і список максимально можливих вантажів, що можливо провезти по відповідним мостам. По дорозі можливий рух в будь-якому напрямі.
Потрібно: Скласти програму, що визначає максимальний вантаж, який можливо провезти між заданими селами
Технічні умови. Програма Маx читає з клавіатури число М (1< M £ 100) – кількість доріг, в наступному рядку – 3 числа: кількість сіл N (1< N £ 100), номери початкового села F та кінцевого L (1 £ F, L £ N ). В M наступних рядках задано дороги. Кожен рядок – три числа через пропуск. Перші 2 – номери сіл, між якими дорога, а 3-є – вантажопідйомність мосту, не більша за 32767. Всі числа цілі. Программа виводить на екран єдине число – шукану величину.
Приклад
| Введення | Виведення |
|
5 4 1 4 1 2 5 1 3 8 2 3 6 2 4 4 3 4 3 |
4 |
Задача Cavalery
На шахівниці розміром NxM знаходиться Q коней в різних клітинках. Шахіст намагається зібрати всіх коней в одну, відому йому клітинку. Знайти мінімальну кількість ходів, яку потрібно для цього зробити шахісту. Якщо задача не має розв’язку (а це буває тоді, коли хоча б 1 кінь не може дійти до заданої клітинки), повідомити про це. Мабуть, вам вже зрозуміло, що в одній клітинці може знаходитись одночасно скільки завгодно коней.
Технічні умови.
Програма
Cavalery читає з клавіатури
розміри шахівниці N, M
(2 ≤ N, M ≤ 100),
координати клітинки, де коні повинні зібратися,
S, T (номер рядка та
стовпчика), кількість коней Q
(0 ≤ Q ≤ 10000), потім Q
пар чисел – координати кожного коня. Програма виводить на екран одне число
– мінімальну кількість ходів, або, якщо задача не має розв’язку,
кількість коней, що не можуть дійти до заданої клітинки.
Приклади
Введення
4 4 1 1 3 2 3 3 2 3 3
Виведення
6
Введення
5 5 3 4 0
Виведення
0
Завдання підготували Пасіхов Ю.Я, Непомнящий Г.І., Олійник О.І.