Материал: Организация и методика проведения турнира программистов в школе

Сюжет условия часто завязан на одном или нескольких героях, вступающих в конфликт друг с другом или с окружающей средой. Часто они являются программистами и также поставлены перед некоторой задачей. Нередко все задачи олимпиады связаны единой сюжетной линией. В этом случае сюжет олимпиады раскрывается постепенно от задачи к задаче.

Турнир (от старофранцузского <#"865279.files/image001.jpg">

Задача 10.

Вводится матрица a(m,n) из 0 и 1. Найти в ней квадратную подматрицу из одних единиц максимального размера.

Задача 11.

Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).

Переформулировка задачи 11.

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

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

Задача 12.

Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам.

Задача 13.

Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и

а) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при этом из текущей клетки можно перейти

) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;

) в любую из 8 соседних клеток;

б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).

Задача 14.

Дан выпуклый n-угольник, n=>3, своим обходом по контуру. Разбить его на треугольники (n-3)-мя диагоналями, непересекающимися кроме как по концам, таким образом чтобы

а) Cумма их длин была минимальной;

б) Максимальная из диагоналей имела наименьшую длину.

Задача 15.

Задано число А и два вектора b[1..n] и c[1..n].

Найти множество I, являющееся подмножеством множества {1,...,n}, такое, что

является максимальной из всех возможных

Задача 16.

Пусть x=(a1,a2,...,am) и y=(b1,b2,...,bn) - две заданных строки символов.

Определим d(x,y) как минимальное число вставок, удалений и замен символа, которое необходимо для преобразования x в y.

Например: d(ptslddf,tsgldds)=3

Для заданных x и y найти d(x,y).

Задача 17.

Вводится три неотрицательных числа d, i, c и две строки X и Y. Найти преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:

удалить любой символ из X (стоимость операции d);

вставить любой символ в X (стоимость операции i);

заменить символ в X на произвольный (стоимость операции e).

Задача 18.

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Задача 19.

Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А1,...Аn, заданных своими размерами n(i)*m(i). При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.

Замечание:(i) - число строк в матрице Ai(i) - число столбцов в матрице Ai

n(i)=m(i)+1.

Задача 20.

а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов (одного "разрыва" возрастающей подпоследовательности).

Например: A=(1,2,3,2,4,3,4,6);

Искомая подпоследовательность (1,2,3,2,3,4,6)

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, m пар соседних элементов (возрастающая подпоследовательность с m "разрывами").

Задача 21.

В заданной последовательности целых чисел найти максимально длинную подпоследовательность чисел такую, что каждый последующий элемент подпоследовательности делился нацело на предыдущий.

Задача 22.

Возвести число А в натуральную степень n за как можно меньшее количество умножений.

Задача 23.

Заданы z и y - две последовательности. Можно ли получить последовательность z вычеркиванием элементов из y.

Задача 24.

Найти максимальную по длине последовательность z, полученную вычеркиванием элементов как из x, так и из y.

Задача 25.

Пусть x и y - две бинарных последовательности (т.е. элементы последовательностей - нули и единицы); x и y можно рассматривать как запись в двоичной форме некоторых двух натуральных чисел.

Найти максимальное число z, двоичную запись которого можно получить вычеркиванием цифр как из x, так и из y. Ответ выдать в виде бинарной последовательности.

Компетентное жюри следит за ходом отдельных этапов турнира, разрешает возникающие спорные вопросы, подводит итоги и награждает победителей. В жюри могут входить педагоги и методисты, психолог, представители интересов игроков (дети, родители), школьники, спонсоры.

В подготовке вопросов, заданий для 1 и 2 этапов игры могут участвовать не только педагоги и методисты, но и сами школьники. Например, старшеклассники могут предлагать вопросы и задачи для школьников младших классов.

Вообще, для проведения турниров целесообразно составлять базу вопросов, заданий, задач. Это могут быть и прочитанные в учебниках, задачниках, интернет задания, и придуманные организаторами и участниками турнира задачи.

Операторы цикла

№1. Даны два целых числа A и B (A < B). Вывести все целые числа, расположенные между данными числами (включая сами эти числа), в порядке их возрастания, а также количество N этих чисел.

№2. Даны два целых числа A и B (A < B). Вывести все целые числа, расположенные между данными числами (не включая сами эти числа), в порядке их убывания, а также количество N этих чисел.

№3. Дано вещественное число A и целое число N (> 0). Вывести A в степени N: AN = A·A·...·A (числа A перемножаются N раз).

№4. Дано вещественное число A и целое число N (> 0). Вывести все целые степени числа A от 1 до N.

№5. Дано вещественное число A и целое число N (> 0). Вывести 1 + A + A2 + A3 + ... + AN. Begin85. Дано вещественное число A и целое число N (> 0). Вывести 1 - A + A2 - A3 + ... + (-1)NAN.

№6. Дано целое число N (> 1). Вывести наименьшее целое K, при котором выполняется неравенство 3K > N, и само значение 3K.

№7. Дано целое число N (> 1). Вывести наибольшее целое K, при котором выполняется неравенство 3K < N, и само значение 3K.

№8. Дано вещественное число A (> 1). Вывести наименьшее из целых чисел N, для которых сумма 1 + 1/2 + ... + 1/N будет больше A, и саму эту сумму.

№9. Дано вещественное число A (> 1). Вывести наибольшее из целых чисел N, для которых сумма 1 + 1/2 + ... + 1/N будет меньше A, и саму эту сумму.

№10. Дано целое число N (> 0). Вывести произведение 1·2·...·N. Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и выводить его как вещественное число.

№11. Дано целое число N (> 0). Если N - нечетное, то вывести произведение 1·3·...·N; если N - четное, то вывести произведение 2·4·...·N. Чтобы избежать целочисленного переполнения, вычислять это opnhgbedemhe с помощью вещественной переменной и выводить его как вещественное число.

№12. Дано целое число N (> 0). Вывести сумму 2 + 1/(2!) + 1/(3!) + ... + 1/(N!) (выражение N! - "N факториал" - обозначает произведение всех целых чисел от 1 до N: N! = 1·2·...·N). Полученное число является приближенным значением константы e = exp(1) (= 2.71828183...).

№13. Дано вещественное число X и целое число N (> 0). Вывести 1 + X + X2/2! + ... + XN/N! (N! = 1·2·...·N). Полученное число является приближенным значением функции exp в точке X.

№14. Дано вещественное число X и целое число N (> 0). Вывести X - X3/3! + X5/5! - ... + (-1)NX2N+1/(2N+1)! (N! = 1·2·...·N). Полученное число является приближенным значением функции sin в точке X.

№15. Дано вещественное число X и целое число N (> 0). Вывести 1 - X2/2! + X4/4! - ... + (-1)NX2N/(2N)! (N! = 1·2·...·N). Полученное число является приближенным значением функции cos в точке X.

№16. Дано вещественное число X (|X| < 1) и целое число N (> 0). Вывести X - X2/2 + X3/3 - ... + (-1)N-1XN/N. Полученное число является приближенным значением функции ln в точке 1+X.

№17. Дано вещественное число X (|X| < 1) и целое число N (> 0). Вывести X - X3/3 + X5/5 - ... + (-1)NX2N+1/(2N+1). Полученное число является приближенным значением функции arctg в точке X.

№18. Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A < B). Отрезок [A, B] разбит на равные отрезки длины H с концами в N точках вида A, A + H, A + 2H, A + 3H, ..., B. Вывести значение H и набор из N точек, образующий разбиение отрезка [A, B].

№19. Дано целое число N (> 2) и две вещественные точки на числовой оси: A, B (A < B). Функция F(X) задана формулой F(X) = 1 - sin(X). Вывести значения функции F в N равноотстоящих точках, образующих разбиение отрезка [A, B]: F(A), F(A + H), F(A + 2H), ..., F(B).

№20. Дано число D (> 0). Последовательность чисел AN определяется следующим образом: A1 = 2, AN = 2 + 1/AN-1, N = 2, 3, ... Найти первый из номеров K, для которых выполняется условие |AK - AK-1| < D, и вывести этот номер, а также числа AK-1 и AK.

Двумерные массивы (матрицы)

№21. Дано число k (0 < k < 11) и матрица размера 4 x 10. Найти сумму и произведение элементов k-го столбца данной матрицы.

№22. Дана матрица размера 5 x 9. Найти суммы элементов всех ее четных1|нечетных2 строк3|столбцов4.

№23. Дана матрица размера 5 x 10. Найти минимальное1|максимальное2 значение в каждой строке3|столбце4.

№24. Дана матрица размера 5 x 10. В каждой строке1|столбце2 найти количество элементов, больших3|меньших4 среднего арифметического всех элементов этой строки1|столбца2.

№25. Дана матрица размера 5 x 10. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждой строке1|столбце2.

№26. Дана матрица размера 5 x 10. Найти минимальное1|максимальное2 значение среди сумм элементов всех ее строк3|столбцов4 и номер строки3|столбца4 с этим минимальным1|максимальным2 значением.

№27. Дана матрица размера 5 x 10. Найти минимальный1|максимальный2 среди максимальных1|минимальных2 элементов каждой строки3|столбца4.

№28. Дана целочисленная матрица размера 5 x 10. Вывести номер ее oepbni1|последней2 строки3|столбца4, содержащего равное количество положительных и отрицательных элементов (нулевые элементы не учитываются). Если таких строк3|столбцов4 нет, то вывести 0.

№29. Дана матрица размера 5 x 10. Вывести номер ее первой1|последней2 строки3|столбца4, содержащего только положительные элементы. Если таких строк3|столбцов4 нет, то вывести 0.

№30. Дана целочисленная матрица размера M x N. Различные строки (столбцы) матрицы назовем похожими, если совпадают множества чисел, встречающихся в этих строках (столбцах). Найти количество строк1|столбцов2, похожих на первую3|последнюю4 строку1|столбец2.

№31. Дана целочисленная матрица размера M x N. Найти количество ее строк1|столбцов2, все элементы которых различны.

№32. Дана целочисленная матрица размера M x N. Вывести номер ее первой1|последней2 строки3|столбца4, содержащего максимальное количество одинаковых элементов.

№33. Дана квадратная матрица порядка M. Найти сумму элементов ее главной1|побочной2 диагонали.

Деревья

№34. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл с именем Name все возможные пути, ведущие от корня к листьям (каждый путь записывается в отдельной строке файла). Перебирать пути, начиная с "самого левого" и заканчивая "самым правым", при этом первыми заменять конечные элементы пути.

№35. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл с именем Name все пути, ведущие от корня к листьям и удовлетворяющие следующему условию: никакие соседние элементы пути не нумеруются одной и той же цифрой. Каждый путь записывается в отдельной строке файла. Порядок перебора путей - тот же, что в задании №34.

№36. Дано упорядоченное дерево глубины N (N > 0 - четное), каждая внутренняя вершина которого имеет два непосредственных потомка: A с весом 1 и B с весом -1. Корень дерева C имеет вес 0. Записать в текстовый файл с именем Name все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей - тот же, что в задании №34.

№37. Дано упорядоченное дерево глубины N (N > 0) того же типа, что и в задании Proc83. Записать в текстовый файл с именем Name все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2. Каждый путь записывается в отдельной строке файла. Порядок перебора путей - тот же, что в задании №34.

№38. Дано упорядоченное дерево глубины N (N > 0 - четное) того же типа, что и в задании Proc83. Записать в текстовый файл с именем Name все пути от корня к листьям, удовлетворяющие следующим условиям: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2, а суммарный вес всех элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей - тот же, что в задании №34.

3.3 Подготовка школьников к олимпиаде

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

Владеть языком программирования (Pascal или Си/Си++)

Уметь:

. придумывать и реализовывать алгоритмы решения задач;

. оценивать время их работы;

. тестировать;

. отлаживать свои программы.

Знать следующие алгоритмы:

класс

Алгоритмы целочисленной арифметики

. Поиск делителей числа. Простые числа 2. Разложение числа на простые множители 3. Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) 4. Представление чисел. Выделение цифр числа 5. Перевод чисел из одной системы счисления в другую 6. Делимость чисел 7. Действия с многозначными (большими) числами

Рекуррентные уравнения и динамическое программирование

. Понятие задачи и подзадачи

. Понятие рекуррентного соотношения

Задачи комбинаторики

. Перестановки

. Сочетания

.