Задания 3-го (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) — числа, которые нужно дописать к последовательности. Все числа разделены пробелами.

Задача Rect

Дан прямоугольник, длины сторон которого - натуральные числа. На сколько квадратов (не обязательно одинаковых) можно разрезать данный прямоугольник? Отрезать квадрат только так, чтобы остающаяся часть образовывала снова некий прямоугольник. Квадрат, отрезанный на очередном шаге, больше не разрезается.

Технические условия

Программа Rect читает с клавиатуры числа a и b - длины сторон (1<=a,b<=1000000000). Программа выводит на экран  искомое количество квадратов.

Пример

Задача 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>. Программа выводит на экран длину пути, пройденного  "Черепашкой", и через пробел  расстояние между начальным и конечным положением «Черепашки», округлив до двух знаков после запятой.

Пример

Задача Max

В  Дубовецком  районе имеется N населенных пунктов,  некоторые из них соединены дорогами с мостами, грузоподъемность которых ограничена.  Из  любого села можно проехать в любое. Каждая дорога имеет 1 мост.

Дано: Для каждого села  список сел, связанных с ним дорогами и список максимально возможных грузов, которые можно провезти по соответствующим мостам.  По дороге возможно движение в произвольном направлении.

Надо:  Составить программу,  определяющую максимальный груз, который можно провезти между заданными селами

Технические условия.  Программа Маx читает с клавиатуры число М   (1< M £ 100)   – количество дорог, в следующей строке – 3 числа:  количество сел N  (1< N £ 100), номера начального села F  и конечного L  (1 £ F,  L £ N ).    В  M  последующих строках задано дороги.  Коаждая строка – три числа через пробел. Першвые 2 – номера сел, между которыми дорога,  а 3-є – грузоподъемность моста, не большая 32767.  Все числа  целые. Программа выводить на экран единственное число – искомую величину.

 Пример

Задача  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

 Задания подготовили Пасихов Ю.Я, Непомнящий Г.И., Олейник А.И.