Теоретический тур

1. Из окрашенной квадратной пластины размером 3*3 сделали 9 квадратов 1*1. Закодируем любой из единичных квадратов четверкой чисел путем просмотра его сторон подряд и беря 1, если сторона окрашена и 0 - иначе. По введенной четверке чисел узнать есть ли среди имеющихся единичных квадратов квадрат с таким кодом.

2. Постройте алгоритм, который распределяет первые N2 натуральных чисел (N>2) в N групп так, что одновременно выполняются следующие три условия:

а) каждая группа содержит ровно N чисел;

б) каждое принадлежит только одной группе;

в) сумма чисел в каждой группе одинакова для всех групп.

3. У покупателя m монет достоинством , а у продавца n монет достоинством . Какова максимальная стоимость книги, если она по средствам покупателю, но он не может купить ее из-за отсутствия у продавца сдачи?

4. В языке программирования определены:

а) одна строчная переменная B;

б) логическая функция А(S,S1) со строчными oперандaми S, S1. Функция А заменяет в строке B первое вхождение подстроки S на подстроку S1. В случае успешной замены A принимает значение True, иначе False;

в) логические операции над логическими переменными;

г) конструкция цикла

While условие do

begin

операторы присваивания;

end;

Оператор присваивания С:=А(S,S1), где С - логическая переменная, которая принимает значение функции A.

Написать на этом языке программирования программу, которая преобразует входную строку В вида <число>++ , где <число> - строчное представление натурального десятичного числа, в строку вида <число+1>, a строку <число>-- в строку вида <число-1>.

Например, строка 1994++ преобразуется в 1995, а 1994-- в 1993.

I практический тур

5. Задана последовательность чисел. Начальные элементы последовательности имеют вид: 1; 11; 21; 1112; 3112; 211213; 312213; ... . Написать программу для нахождения первого элемента другой последовательности, содержащего цифру пять, если она строится аналогично рассмотренной, но с начального натурального числа n.

6. Для натуральных чисел X и Y будем говорить, что X входит в Y, если двоичную запись числа X можно получить из двоичной записи Y вычеркиванием нулевого, единичного или большего количества цифр. (Например: X=1010 входит в Y=1001100). Постройте алгоритм, который для двух данных натуральных чисел A и B найдет максимальное число C, входящее как в A, так и в B.

7. Какое наименьшее количество российских купюр необходимо, чтобы разменять банкноту "осьминога" планеты "Не_знаю_дробей" достоинством 1000 "вокадусов" из расчета 1 "вокадус" = 1 рублю? Банкнота "осьминога" имеет форму прямоугольника с периметром 101 "ого" и площадью 3003 "ого"2. В настоящее время в России в обращении находятся купюры достоинством в 100000, 50000, 10000, 5000, 1000, 500, 200, 100, 50, 20, 10, 5, 2 и 1 рублей.

II практический тур

8. Даны n карточек, занумерованных числами 1, 2, 3, ..., n (каждый номер встречается только один раз). Карточки расположены в ряд. Под перестановкой понимается единичный обмен местами любых двух карточек.

Цель: используя перестановки расположить карточки в порядке возрастания номеров 1, 2, ..., n.

Задание. Составить программу, которая:

а) вводит с клавиатуры начальное расположение карточек, а также моделирует перемещения;

б) для заданного начального расположения карточек определяет последовательность перестановок, достигающих цели;

в) находит последовательность перестановок, достигающих цели за наименьшее их количество.

Пример: Для последовательности 1, 5, 3, 2, 4 необходимы две перестановки: N5 и N2, а затем N4 и N5, после чего получается упорядоченная последовательность 1, 2, 3, 4, 5.