Заочная олимпиада по программированию

Квант 1985, №6 с. 26 Тег E6DL

Заочная олимпида по программированию

17 февраля 1985 года Учебно-производственный центр вычислительной техники Октябрьского района Москвы и институты Электронных управляемых машин Минипибора СССР и Проблем информационных (шестую) Московскую городскую олимпиду по программированию для школьников, в котором участвовали около 200 человек.

Журнал «Квант» предлагает всем школьникам и учащимся ПТУ, умEOЩИМ программировать (кроме Москвы), задачи этой олимпиды в качестве задания Заочной олимпиды по программированию. Решения отправляйте не позднее 1 августа (по почтовомуITEMПЕЛЮ) на адрес «Кванта», написав на конверте: «Олимпида по программированию». Присланьные решения будут оценяться жюри под председательством доктора физиокатематических наук А. Л. Брудно. Все участникам будут присланы отзываны об их работах. Победители получат Дипломы журнала «Квант».

Имейте в виду, что описки снижают оценку решения. Снижают оценку и алгоритмы с излишим числом действия или массивами, без которых можно обойтись. Хорошие алгоритмы и экономно написанные программы оценку повышают. В каждой работе зачитываются только 3 задачи с более удачными решениями.

Задчи приведены в порядке убывания трудности. Принимаются решения на любых языках программирования. Переед решения надо дать сложное описание алгоритма.

Задачи

Разложение на слагаемые. Напечать все способы представления натурального числа $n$ суммой натуральных чисел. Перестановка слагаемых новым способом не считается.
Равные элементы. Задан массив чисел $P[1:m, 1:n]$ . Каждая строка массива упорядочена по возрастанию. Найти и отпечать число, встречающееся во всех строках, и надпись NET, если такого числа не оказывается.
Несоставляемое число. Задан массив натуральных чисел $M[1:n]$ . Найти и отпечать минимальное натуральное число, не представное суммой элементов массива $M$ . Сумма может состоять и из одного слагаемого, но каждый элемент массива может входить в нее только один раз.
Тетраэды. На гранах двух равных правых tetraэдров $M$ и $N$ написаны числа $M1, M2, M3, M4$ на одном, и $N1, N2, N3, N4$ на другом (в том же порядке). Можно ли совместить tetraэдры так, чтобы на совпавших гранах оказались написаны одинаковые числа? Напечать DA или NET.
Самое частое число. В массиве чисел $M[1:n]$ найти число, повторяющее максимальное количество раз. Если их несколько, то одно из них.
Системы числения. В целочисленном массиве $M[1:9]$ записаны разряды (цифры) некоторого натурального числа в $i$ -ричной системе числения ( $M[1]$ — разряд единиц и т. д.). Отпечать разряд этого числа в $j$ -ричной системе числения. Числа $i$ и $j$ не более числа десять.
Воковая диагональ. Найти сумму элементов $A[i, j]$ массива $A[1:m, 1:n]$ , имеющих заданную разность индексов $i-j=k$ . Число $k$ — целое, но не обязательно положительное.

Пояснение. Здесь массив $P[1:m, 1:n]$ обозначает массив чисел $P_{ij}$ для $i=1, 2, ..., m$ и $j=1, 2, ..., n$ , а запись $P[i, j]$ обозначает элемент $P_{ij}$ . Если сказано, что массив $P[1:m, 1:n]$ задан, то значит заданный числа $m, n$ и значения элементов массива. Аналогичный смысл имеются и задания других массивов.

В программах (решения) ученики вводят извлеканые значения и печатают их. Неокоторые оформляют решения в виде подпрограммы (в алгорите — procedure, в фортера — subroutine и т. д.). В тех языках, где размер массивов нужно задать числа (как на фортера), ученики их выбирают произвольно.

«Хорошие решения» должны укладывать (с точностью до постоянного множителя) в следующие колчества: $m \cdot n$ (задача 2), $n^2$ или $n \cdot \log n$ (задачи 3 и 5), min { $m, n$ } (задача 7), считая $n$ и $m$ большими числами.