Теоретический тур
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.