Задачи для Программистов

Архив московских студенческих олимпиад по программированию
1979-90 гг.

На этой странице собраны задачи разных лет с институтских, московских городских и всесоюзных студенческих олимпиад по программированию, собранные в 1979 - 1990 гг. Эдгаром Александровичем Черновым за время его участия в проведении студенческих олимпиад по программированию в МАДИ (сейчас МАДИ-ТУ), а также участия в московских городских олимпиадах по программированию среди вузов в качестве руководителя сборной команды МАДИ. Авторами или соавторами большинства задач, предложенных МАДИ являются выпускники МАДИ Юрий Каганов, Виталий Каждан, Стас Коновалов, Алекс Покрас.

Эта страница не является полным собранием всех задач для программирования, которые встречались на олимпиадах за эти годы. В него вошли задачи с внутриинститутских туров не только МАДИ, но и других институтов Москвы (задачи с институтских олимпиад помечены названием института и годом "рождения") и московских городских туров (помечены словом "Москва" и годом, иногда в скобках указан предложивший задачу институт, если он известен). В задачи с московских туров попали как принятые и участвовавшие в соревнованиях, так и те задачи, которые были только предложены для участия, но по каким-либо причинам были отвергнуты. Есть задачи, фигурировавшие на всесоюзных олимпиадах, а также задачи, источник которых неизвестен. Сведения о происхождении задач не проверялись.

Задачи не отсортированы по сложности и оценка сложности не приводится. Названия задач условные, хотя по возможности сохранены названия авторов задач. Текст задач подвергся некоторой правке, в основном стилистического характера. Была также убрана излишняя детализация в описании входных данных, а также всякие упоминания о перфокартах, как об устаревших морально.

Любое некоммерческое использование информации с этой страницы разрешается при условии ссылки на источник информации. Коммерческое использование информации возможно только по письменному разрешения ее владельцев. Если Вы являетесь автором любой из задач, приведенных на этой странице, сообщите мне об этом. Также я был бы рад получить любую дополнительную информацию, задачи более поздних лет с олимпиад по программированию, красивые решения приведенных и других задач, ссылки на аналогичные страницы и т.д. 

Алекс Покрас. Хайфа, 1999 г.

*  *  *

Задачи Олимпиад по Программированию 1979-1990 гг.

1. Матрица и вектор (МАДИ, 1982, I тур)

Осуществить ввод матрицы размерностью 3x20 и целочисленного вектора размерностью 8. Все элементы вектора положительные и не превышают 20. Выдать на печать по одному разу все те столбцы исходной матрицы, номера которых не встречаются в исходном векторе. Распечатка должна иметь вид прямоугольной матрицы из 3 строк, причем столбцы должны идти в их первоначальном порядке.

2. Шах ферзем (МАДИ, 1982, I тур)

Задано шахматное поле 8x8. Каждой клетке соответствует пара целых чисел от 1 до 8 - ее горизонтальная и вертикальная координата (например, левой верхней угловой клетке - 1, 8). Осуществить ввод координат белого ферзя и черного короля и печать координат всех полей, которые ферзь может достичь за один ход, объявив при этом шах. В начальной позиции король не находится под шахом. На каждой строке отпечатать координаты одного поля.

3. Звенья и цепочки (МАДИ, 1982, II тур)

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

4. Оси симметрии (МАДИ, 1982, II тур)

Задан N-угольник на плоскости (N<30). Найти все его оси симметрии и по одному разу вывести на печать для каждой из них на отдельной строке координаты точек пересечения с данной осью контура N-угольника. Первая строка исходных данных содержит число N, остальные строки содержат N пар декартовых координат вершин N-угольника в порядке их соединения сторонами. Все координаты - четные числа.

5. Значение выражения (МАДИ, 1983, I тур)

На строке в позициях 1 до 79 набито арифметическое выражение. В нечетных позициях набиты цифры, в четных - знаки арифметических операций: "+" (сложение), "-" (вычитание), "*" (умножение) и "/" (деление). Напечатать числовое значение арифметического выражения. Порядок выполнения операций соответствует общепринятому.

6. Максимальный фрагмент (МАДИ, 1983, I тур)

Вводится последовательность из 40 натуральных чисел меньших 100. Выделить из данной последовательности подпоследовательность максимальной длины, являющуюся сплошным фрагментом натурального ряда, и напечатать ее.

7. Составление алфавита (МАДИ, 1983, II тур)

Набором называется подмножество латинского алфавита (возможно, пустое). Задано несколько наборов, пронумерованных по порядку. Требуется составить полный упорядоченный латинский алфавит, последовательно выбирая буквы из наборов таким образом, чтобы общее число переходов из набора в набор было минимальным (переход - выбор двух соседних букв алфавита из разных наборов).

Вводится одна символьная строка, содержащая все наборы, разделенные символом *. Ответом является последовательность из 26 чисел, каждое из которых является номером набора, из которого взята соответствующая буква, или, в случае отсутствия в наборах одной из букв, сообщения "нет решения". Наборы нумеруются последовательно в порядке их следования.

8. Пятая звездочка (МАДИ, 1983, II тур)

Задана матрица 11x11, заполненная символами "X" и пробелами. Записать символ "*" во все элементы матрицы, содержащие пробел, замена которого на символ "X" привела бы к образованию сплошного вертикального, горизонтального или диагонального ряда, состоящего ровно из 5 символов "X". Полученную матрицу выдать на печать. Вводится центральная часть матрицы размером 9x9, остальные элементы матрицы считаются пробелами.

9. НОК и НОД (МАДИ, 1984, I тур)

Вводятся два целых числа M и N. Напечатать частное от деления наименьшего общего кратного (НОК) чисел M и N на их наибольший общий делитель (НОД).

10. Сборная команда (МАДИ, 1984, I тур)

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

11. Факториал (МАДИ, 1984, II тур)

Вводится двузначное положительное целое число. Напечатать факториал этого числа.

12. Перестановка букв (МАДИ, 1984, II тур)

Вводятся два 10-буквенных слова. Второе слово получено перестановкой букв первого слова. Требуется перейти от первого слова ко второму, каждый раз меняя местами две соседних буквы и печатая получившуюся строку.

13. Система счисления (МАДИ, 1985, I тур)

Вводятся два целых числа K и N (2<=K<=16, 0<=N<=999). Записать число N в K-ичной системе счисления. В случае K > 10 в качестве цифр 10-15 использовать буквы от A до F.

14. Суммы по диагоналям (МАДИ, 1985, I тур)

Вводится целочисленная матрица M(40x40). Найти такую диагональ, чтобы суммы элементов матрицы, лежащих выше и ниже диагонали, были равны. Элементы, лежащие на диагонали, при подсчете сумм не учитываются. Рассматриваются только диагонали, идущие сверху вниз налево. Напечатать номер диагонали. Диагональ, включающая один элемент M(1,1), имеет номер 1, следующая - 2 и т.д. до 79.

15. Безударные гласные (МАДИ, 1986, I тур)

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

16. Воскресенья одного месяца (МАДИ, 1986, I тур)

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

17. Скобки (МАДИ, 1986, II тур)

Проверить правильность расстановки скобок трех видов (круглых "()", квадратных "[]" и угловых "<>") в символьной строке. Расстановка скобок считается правильной, если:

• множество всех скобок можно разбить на пары однозначно соответствующих друг другу скобок одного вида, в которых открывающая скобка расположена левее закрывающей;
• предыдущее условие выполняется для строк, заключенных между любыми двумя соответствующими друг другу скобками.

Длина вводимой строки не превышает 80 символов, признаком конца строки является символ "*". Требуется распечатать исходные данные в неизменном виде и, в случае обнаружения ошибки, напечатать символ "х" под первым слева ошибочным символом (возможно, звездочкой).

18. Размен (МАДИ, 1986, II тур)

Вводятся два натуральных числа - N и S. Требуется напечатать по одному разу все варианты размена N монетами суммы в S копеек. Варианты, отличающиеся только порядком монет, считаются одинаковыми. Каждый вариант должен быть напечатан на отдельной строке. Имеются в неограниченном количестве монеты достоинством 1, 2, 3, 5, 10, 15, 20 и 50 копеек.

19. Упорядочение по алфавиту (МАДИ, 1987, I тур)

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

20. Натуральный ряд (МАДИ, 1987, I тур)

Вводится число N (1<N<106). Напечатать N-ую цифру числа, составленного из написанных подряд последовательных натуральных чисел, начиная с 1.

21. Ход шашкой (МАДИ, 1987, II тур)

На шашечной доске 8х8 задано положение одной белой и нескольких черных шашек. Координаты полей доски задаются номерами горизонталей и вертикалей (координаты (1, 1) соответствуют левому нижнему углу). Требуется сделать один ход белой шашкой по правилам русских шашек, но без учета превращения шашки в дамку; при этом на печать должны быть выведены координаты всех полей, на которые при ходе попадает белая шашка. Если у белой шашки нет допустимых ходов, то напечатать сообщение "нет хода". Исходные данные задаются в виде пар координат. Первая пара задает положение белой шашки, остальные - черных. Признаком конца списка пар является пара (0, 0).

22. Венгерский кубик (МАДИ, 1987, II тур)

Имеется куб 3x3x3 (венгерский кубик), заданы положение одного из угловых элементарных кубиков и последовательность поворотов граней куба, определить новое положение элементарного кубика. Грани куба обозначаются следующим образом: Ф - фронт, Т - тыл, П - право, Л - лево, В - верх, Н - низ. Каждый поворот выполняется вращением слоя из 9 кубиков, находящихся на соответствующей грани, на 90 градусов по часовой стрелке (при взгляде на эту грань). Ориентация куба при этом не изменяется.

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

23. Олимпиада по программированию (МАДИ, 1988, I тур)

Выступления участников Олимпиады по программированию очениваются целым числом баллов от 0 до 40. Вводятся 30 чисел, представляющих собой количество баллов, набранных каждым из участников. Напечатать в том же порядке занятые участниками места. В случае одинаковых баллов, набранных разными участниками, напечатать через пробел номера первого и последнего из разделенных мест.

24. Шариковая ручка (МАДИ, 1989, I тур)

При нажатии кнопки шариковой ручки на расстояние 6 мм происходит щелчок, называемый "щелчок А". При отпускании кнопки на расстояние 3 мм от начального положения происходит "щелчок Б". Щелчок А происходит только после щелчка Б, а щелчок Б - только после щелчка А. Каждый щелчок А переключает ручку из включенного положения в выключенное и обратно. Вводятся 16 целых чисел, задающих (в мм) перемещения кнопки от текущего положения (положительные - вниз, отрицательные - вверх). В начальном состоянии ручка выключена. Напечатать конечное состояние. Выход кнопки за физические пределы ручки не учитывать.

25. Арифметическое выражение (МФТИ, 1988)

На одной строке размещено арифметическое выражение (в смысле языка Фортран), состоящее из целых констант (каждая константа длиной до 7 цифр) и знаков арифметических операций (+, -, *, /). Выражение не содержит внутри себя пробелов. Определить значение выражения и напечатать результат.

26. Окружение клеток (Отборочный тур, 1983. МАДИ)

Имеетс координатная сетка с шагом 1. Некоторые узлы сетки соединены отрезками, параллельными одной из координатных осей. Провести максимальное количество отрезков единичной длины, причем каждый проводимый отрезок должен завершать окружение единичной клетки. Вводятся пары координат концов отрезков, существующих в начальном положении. Требуется напечатать пары координат концов проводимых отрезков в порядке их проведения.

27. Синтаксический анализ (Отборочный тур, 1983. МАДИ)

Вводится строка символов, содержащая оператор SUBROUTINE языка Фортран-IV. Требуется произвести синтаксический контроль этого оператора и напечатать символ "*" под первым слева ошибочным символом.

28. Биллиард с 6 лузами (МФТИ.1988)

Задан биллиард в виде прямоугольного клеточного поля размером MxN клеток (M - нечетное, определяет длину поля вдоль оси OX). В углах прямоугольного поля и посередине стороны M размещены 6 лунок, каждая размером в одну клетку, пронумерованных от 1 до 6 начиная от левого верхнего угла).

Биллиардный шар начинает движение с клетки с координатами K, L в одном из восьми направлений (вертикально, горизонтально и по двум диагоналям в обоих направлениях). Шар двигается только по целым клеткам и отражается от стенок по закону: угол падения равен углу отражения.

Пренебрегая трением, выяснить: останется ли шар на доске или покинет ее через одну из лунок. В последнем случае указать номер лунки. Исходные данные включают 5 целых чисел M, N, K, L, T. Число T задает начальное направление движения шара.

29. Площадь многоугольника (МФТИ, 1988)

В правом верхнем квадранте плоскости XOY в области 106x106 находится прямоугольный многоугольник со сторонами, параллельными осям координат. Многоугольник задан своими N вершинами, имеющими целочисленные координаты. Следует определить площадь этого многоугольника.

Исходные данные подготовлены в следующем виде: число N и координаты вершин многоугольника (X1, Y1), (X2, Y2) ... (XN, YN). Вершины многоугольника перечислены в произвольном порядке, многоугольник без самопересечений.

30. Магический квадрат

Магическим квадратом порядка n называется квадратная матрица NxN, состоящая из всех натуральных чисел от 1 до N**2, в которой суммы чисел по строкам, столбцам и диагоналям равны одному и тому же числу. Сформировать магический квадрат нечетного порядка (N>1).

31. Расписание игр

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

32. Знакомые студенты

Имеются n студентов S1, S2 ... Sn, среди которых есть знакомые друг с другом. Определить, можно ли разбить всех студентов на две группы так, чтобы студент каждой группы был знаком только со студентами другой.

33. Окно (МИГАИК, 1988)

Определить, пройдет ли прямоугольный параллелепипед с ребрами A, B, C через прямоугольное окно с заданными сторонами.

34. Мышеловка (МИГАИК, 1988) (США, 1983)

Вводится массив из N чисел, в котором записаны натуральные числа от 1 до N. С первого элемента начинается счет: 1, 2, 3 и так до N+1. Если номер при счете совпадает со значением элемента, то фиксируется "попадание", сам элемент удаляется, и счет начинается заново со следующего элемента. После последнего элемента счет продолжается с начала массива. Требуется для введенного массива напечатать список всех попаданий.

Примеры:
    1 3 5 7 9 2 4 6 8 - попадания 1 8
    9 7 3 1 2 4 5 6 8 - попадания 3 1 7

35. Перевод в арабские (МЭИ, 1988)

Вводится строка из символов I, V, X, L, C, D, M. Напечатать эквивалент этого числа в арабских цифрах. Примеры: IV - 4; CCCXCIX - 399.

36. Морской бой (Москва, 1988. МИСиС)

В клеточном поле 10x10 разместить 10 кораблей по правилам игры "Морской бой"  (один 4-клеточный, два 3-клеточных, три 2-клеточных и четыре 1-клеточных, корабли не должны касаться друг друга ни в одной точке) так, чтобы они не касались заминированных клеток. Исходные данные: задано количество мин N и N пар координат заминированных клеток. Для каждого решения задачи выдать матрицу 12x12, по периметру которой расставлены символы "*", клетки, занятые кораблями, отметить символом "Х", клетки, занятые минами, отметить символом "О". Остальные клетки оставить пустыми. Если решения нет, то выдать об этом сообщение.

37. Развертки кубов (МИСиС, 1984)

Даны две развертки кубов, на гранях которых записаны натуральные числа. Определить, относятся ли эти развертки к одному и тому же кубу.

38. Биллиард с 4 лузами

Биллиард представляет собой клетчатый прямоугольник размера NxM. В клетке с координатами (I, J) находится шар. В переменной K задано одно из четырех значений от 1 до 4, определяющих направление, в котором начинает двигаться шар по следующей схеме (шар движется по диагонали): 1 - вправо и вверх, 2 - вправо и вниз, 3 - влево и вниз, 4 - влево и вверх. Достигнув стенки биллиарда, шар отражается от нее и продолжает двигаться по перпендикулярному диагональному направлению. Движение шара заканчивается выходом из биллиарда, если он попадает в одну из угловых клеток.

Требуется для заданных N, M, I, J и K определить, выйдет шар за пределы биллиарда или нет. Если выйдет, то указать, через какой угол и через сколько ударов о стенки биллиарда. Распечатать название угла, через который выходит шар, в виде координат угла и количество ударов о стенку биллиарда. Если движение шара зацикливается, то выдать об этом сообщение и указать количество ударов в одном цикле.

39. Цепочка пар (Москва, 1985)

Есть 18 различных четырехразрядных чисел без знака. Преобразованием является замена ровно одной цифры на большую. Вводится 9 пар четырехразрядных чисел. Составить самую длинную цепочку для каждой пары, которая преобразует одно число в другое с использованием исходных чисел.

40. Одинаковые произведения (Москва, 1985)

Имеется 2*N чисел, про которые известно, что среди них ровно M пар таких, что произведение одного числа на другое в каждой из пар равно одному и тому же числу. Найти и напечатать все эти пары.

41. Сколько треугольников (Москва, 1985)

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

42. Наибольшая степень (Москва, 1985)

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

43. Нечетная сумма (Москва, 1985)

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

44. Выбор формулы (Москва, 1985)

Вводятся шестерки целых чисел A, B, C, D, E, Y. Первые пять чисел в каждой шестерке по модулю не превосходят 50. Известно, что в каждой шестерке Y получен из A, B, C, D и E по одной и той же формуле

Y = ((((A *1 B) *2 C) *3 D) *4 E)

причем все операции (*1, *2, *3 и *4) выбраны, возможно, с повторением, из набора: "+" (сложение), "-" (вычитание), "*" (умножение) и "/" (целая часть частного). Требуется найти и напечатать соответствующую формулу.

45. Связные множества (Москва, 1985)

Дана матрица NxN (1<N<50), состоящая из нулей и единиц. Определить количество связных множеств, на которое можно разбить позиции, занятые единицами.

Множество элементов называется связным, если из любого его элемента (I, J) может быть получен любой другой элемент этого множества последовательным изменением (увеличением или уменьшением) одной из координат на единицу, причем все промежуточные элементы должны принадлежать этому множеству.

46. 3 + 5 (Москва, 1984)

Вводятся числа большие 7. Требуется каждое число выдать в виде 3*A+5*B для всех A и B.

47. Сумма подмножества (Москва, 1984)

Вводится N натуральных чисел. Найти такое натуральное число, которое не может быть представлено суммой подмножества введенных чисел.

48. Сортировка по "A" (Москва, 1984)

Дан набор из N строк (N<=100). Длина каждой строки L (L<=80). Вывести сначала строки, у которых в 1-й позиции находится символ "A", затем строки с символом "A" во 2-й позиции и т.д. Внутри групп сортировка в последующих позициях в алфавитном порядке.

49. Упорядочение матрицы (Москва, 1984)

Вводится матрица MxN. Упорядочить матрицу, переставляя строки, так чтобы первый столбец был упорядочен по возрастанию значений элементов столбца. Если элементы первого столбца равны, то упорядочить по второму столбцу, и т.д.

50. Минимальная разность (МИИГА, 1989)

Дан массив из М целых чисел. Разбить исходный массив на 2 массива так, чтобы разность между суммой чисел одного сформированного массива и суммой чисел другого сформированного массива была бы минимальной.

51. Перенос цифры (МЭИ, 1989)

Для введенных цифр M и N (M>0, N>1) найти натуральное число (если оно существует), оканчивающееся цифрой M и увеличивающееся при переносе этой цифры в начало числа в N раз.

52. Объединение отрезков (МЭИ, 1989)

Вводится целое число N (N<20) и целочисленные массивы L(N) и R(N) такие, что
    -10000 < L(I) < 10000
    -10000 < R(I) < 10000
    L(I) < R(I).
Исходные данные задают множество из N отрезков на числовой оси, L(I) и R(I) координаты левого и правого концов I-го отрезка. Найти суммарную длину заданных отрезков.

53. Треугольная таблица (МАТИ)

Натуральные числа организованы в таблицу, как показано на рисунке:

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

54. Маршрут в матрице

Задана матрица NxN. Ее элементы - целые числа. В матрице отмечены два элемента (заданы их координаты). Найти в матрице такой маршрут, соединяющий эти элементы, чтобы сумма значений элементов, встретившихся при проходе по этому маршруту, была максимальной, и вывести его.

55. Три поля

Дана шахматная доска 8x8 и на ней задано положение коня и отмечены три поля (заданы их координаты). В минимальное число ходов конем посетить все эти три поля и вывести маршрут.

56. Вычеркивание символов (Всесоюзная Олимпиада, 1984)

Вводится строка, содержащая 80 символов и двузначное число N. Символы в строке считаются по порядку - 1, 2 ... N. N-й символ вычеркивается (если N>80, то после последнего символа строки счет переходит на ее первый символ), остальные символы "подтягиваются". Процедура повторяется до тех пор, пока не останется один символ. Вывести оставшийся символ на печать.

57. Складывание листа (Всесоюзная Олимпиада, 1984)

Имеется квадратный лист бумаги, разграфленный на малые квадратики. Длина стороны листа N квадратиков. Лист складывается пополам (правые верхний и нижний углы накладываются на соответствующие левые) и еще раз пополам (нижние левый и правый углы на соответствующие верхние). Процедура складывания продолжается до тех пор. пока не останется один квадратик. Затем стопка перенумеровывается сверху вниз. Лист раскладывается. Напечатать расположение полученных чисел на листе для заданного N.

58. Наибольшая подстрока (Москва, 1981)

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

Пример:
    Исходные строки: ABCD и ABD
    Циклические повторения: ABCDABCDABCDABCD... и ABDABDABDABDABDA...
    Наибольшая общая подстрока: DAB

59. Шахматные слоны (Москва, 1990)

На шахматной доске размером MxM (M<1000) расположены N слонов (1 < N < min(M2,100). Определить количество клеток, которые находятся под боем хотя бы одного из этих слонов. Слон бьет клетку, если он находится на одной диагонали с ней. Считается также, что слон бьет и ту клетку, на которой он находится.

60. Геометрические фигуры (Москва, 1990)

По заданным целочисленным координатам четырех точек на плоскости определить, какая получится плоская геометрическая фигура, если их соединить отрезками.  Исходные данные: 4 пары координат точек.

61. Слова (Москва, 1990)

Задан алфавит из N<10 букв и набор из K<10 слов, составленных из букв этого алфавита. Определить, существует ли слово из заданного алфавита, пересекающееся с каждым словом из заданного набора ровно по одной букве (возможно повторяющейся), и если существует, то построить такое слово.

62. Кантовка ящика (Москва, 1990)

На координатной плоскости расположен ящик в форме параллелепипеда, прилегая к осям OX и OY. Размеры ящика по оси OX - LX, OY - LY и высота LZ - целые числа из интервала от 1 до 99. Вершина угла, прилегающая к началу координат, помечается. Ящик кантуется по координатной плоскости в соответствии с заданной последовательностью кантовки (север, юг, запад, восток). Определить координаты X, Y и Z вершины после кантовки.

63. Острова (Москва, 1990)

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

64. Проволока (Москва, 1990)

Есть проволока длины L и набор прутьев длин K1...Kn. Нарезать из проволоки стандартные прутья длины Ki (i=1...n), так чтобы количество прутьев и длина остатка были бы минимальны.

65. Считалочка (Москва, 1983, II тур) (Кнут. Исскуство программирования)

Вводятся 2 целых числа: M и N (M<999, N<999). N - число субъектов, M - число слов в считалочке. Счет начинается с первого субъекта (по одному слову на каждого) и продолжается по кругу. Субъект, на которого выпадает последнее слово, выбывает. Счет продолжается со следующего субъекта. Напечатать номер последнего оставшегося субъекта.

66. Пересечение отрезков

Вводятся координаты четырех точек, расположенных на плоскости. Первая и вторая точки определяют отрезок AB, третья и четвертая - отрезок CD. Напечатать координаты четырех точек и сообщение о том, пересекаются или нет эти отрезки.

67. Подбор чисел (МИСИ, 1986)

Для заданных целых чисел N и M таких, что 2 <= N <= 20, M <= 999, N(N+1)/2 <= M сгенерировать и напечатать все наборы чисел K(I) из N чисел, удовлетворяющих условиям
    0 < K(1) < ... < K(N)
    K(1) + K(2)+ ... + K(N) = M
например для N = 3, M = 10 напечатать
    1: 1 2 7
    2: 1 3 6
    3: 1 4 5
    4: 2 3 5

68. Кольцевой массив (МФТИ, 1987)

Задан массив натуральных чисел от 1 до N (N<10000), элементы которого расположены в порядке возрастания, и задано целое число K. Массив свернут в кольцо (за N следует 1). Составить программу, реализующую следующую процедуру: на каждом шаге из массива исключается один элемент, причем i-ое исключение задается числом li и производится следующим образом: начиная с первого после исключенного на предыдущем шаге исключается li элемент. li = K. Для первого шага подсчет начинается с первого элемента. На печать выдать значения трех последних исключенных элементов.

69. Матричный принтер (МФТИ, 1987)

Имеется матричное печатающее устройство, которое может печатать символы как слева направо, так и справа налево. После печати очередного символа каретка устанавливается на правую границу позиции с отпечатанным символом (при движении вправо) или на левую границу (каретка движется влево). Промежутков между позициями нет. Перевод бумаги на новую строку только в одном направлении. Время перевода каретки на N позиций (в том числе в начало и конец строки) равно времени печати N символов. Длина строки печатающего устройства 72 символа. Начальное положение каретки - перед первой позицией первой строки. Каждая строка печатается целиком за один проход каретки. Файл из M < 100 строк необходимо напечатать за минимальное время. Предполагается, что каждая строка содержит хотя бы один символ, отличный от пробела.

Требуется вывести на печать файл данных. Перед каждой строкой выводится знак "+" или "-", если строка должна печататься справа налево. Входные данные: число M и M строк файла данных.

70. Взаимно простые числа (Москва, 1987, МИСиС)

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

71. Пересекающиеся окружности (Москва, 1987, МИСиС)

Заданы тройки чисел (координаты центра и радиус). Найти наибольшее количество пар пересекающихся окружностей.

72. Два кратных (Москва, 1987, МИСиС)

Задано число. Найти пару чисел с наибольшим общим кратным, которые равны в сумме исходному числу.

73. Упорядоченные матрицы (Москва, 1987, МИСиС)

Заданы два числа N и M. Подсчитать количество возможных упорядоченных по возрастанию элементов по строкам и по столбцам матриц размерности NxM.

74. Башня из бокалов (Москва, 1987, МИСиС)

Заданы пары целых чисел, обозначающих длину ножки и глубину бокалов. Бокалы могут быть вставлены друг в друга. Из всех бокалов строится башня. Указать порядок вложения бокалов, при котором общая высота башни будет минимальной.

75. Муха и слон (Москва, 1987, МИСиС)

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

76. Отборочные соревнования (Москва, 1987, МИРЭА)

По результатам отборочных соревнований участники имеют результаты: штрафные баллы - W1, W2 ... Wn; очки - V1, V2 ... Vn. Отобрать команду из N человек, которая набрала максимальное количество очков при суммарном штрафе меньшем, чем Wmax.

77. Наилучшее приближение (Москва, 1987, МЭИ)

Найти наилучшее приближение числа "пи" в виде дроби M/N, где M, N - целые числа. В качестве исходных данных задано число K - количество цифр в числах M и N.

78. Счастливые билеты (Москва, 1987, МЭИ)

Написать программу, определяющую количество "счастливых" трамвайных билетов с номерами, принадлежащими заданному интервалу номеров от N1 до N2 (N1<=N2). Граничные номера входят в интервал. Номер трамвайного билета представляет собой шестизначное неотрицательное число, записываемое без подавления незначащих нулей. Номер считается счастливым, если суммы первых трех и последних трех его цифр равны. Билет с номером 000000 существует.

79. Значащие цифры (Москва, 1987, МАМИ)

Вводятся два произвольных целых числа C и D. Определить пять значащих цифр частного от деления C на D.

80. Разные цифры (МТИ, 1987, Текстильный институт)

Напечатать все N-значные натуральные числа, в десятичной записи которых нет одинаковых цифр.

81. Ломаная без самопересечений (Москва, 1981)

Вводится натуральное число N (N<100) и N пар целых координат Xi и Yi точек на плоскости. Напечатать номера точек в таком порядке, чтобы при соединении их отрезками получалась ломаная замкнутая линия без самопересечений.

82. Вставка чисел (МЭИ, 1987, I тур)

Вводятся натуральные числа N, K (N<999, K<999) и последовательность из N целых чисел, в которую надо вставить K целых чисел так, чтобы полученная последовательность содержала наибольшую возрастающую последовательность идущих подряд целых чисел. Из двух последовательностей большей является более длинная, а в случае равной длины - с наибольшим первым элементом.

83. Произведение полиномов (МЭИ, 1987, I тур)

Два полинома P1 и P2 заданы в виде последовательностей пар (K, N). каждая из которых содержит ненулевой коэффициент K, при некотором XN и степень N. Количества ненулевых коэффициентов в каждом полиноме N1 и N2 вводятся перед вводом полиномов (N1<9, N2<9). Коэффициенты K и степени N положительные и не превосходят 99. Напечатать в таком же виде (последовательности пар) полином, являющийся произведением полиномов P1 и P2.

84. Точки в круге (МЭИ, 1987, I тур)

Вводится целое положительное число R (R<=999). Найти количество точек плоскости с целочисленными координатами X и Y, лежащих внутри (в том числе на границе) круга с радиусом R и центром в начале координат.

85. Отрезки и треугольники (МЭИ, 1987, II тур)

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

Пример: Задано 6 отрезков с длинами 2, 3, 3, 3, 4, 6. Из них можно составить различные невырожденные треугольники со сторонами (2 3 3), (2 3 4), (3 3 3), (3 3 4), (3 4 6). Ответ: пять треугольников.

86. Следующее число (МЭИ, 1987, II тур)

Для заданного натурального числа N (число цифр в числе N не превышает 80) получить следующее (наименьшее среди чисел, больших чем N) число с такой же суммой цифр, что и N.

87. Поменять значения (МИГАИК, 1987) (Кнут. Искусство программирования)

Поменять местами значения переменных А и В не используя вспомогательную переменную.

88. Большее число (МИГАИК, 1987)

Записать большее из А и В в арифметическом выражении, используя только функции SQR(X), ABS(X), SIN(X).

89. Простые числа (МИГАИК, 1987)

Дано число М. Найти сумму и количество простых чисел, меньших М.

90. Выпуклый четырехугольник (МИГАИК, 1987)

Даны координаты четырех точек в системе XOY. Определить, можно ли из этих точек образовать выпуклый четырехугольник?

91. Три по три (Отборочный тур, 1988)

Представим себе массив всех 9-значных целых десятичных чисел, каждое из которых содержит ровно три разные цифры, а каждая цифра в числе ровно три раза. Пусть этот массив упорядочен по возрастанию и нули в начале числа допускаются. Следовательно, первое число в массиве 000111222, а последнее 999888777.

Вводятся в произвольном порядке числа, принадлежащие этому массиву. Требуется для каждого из них напечатать число, непосредственно предшествующее ему и непосредственно следующее за ним в описанном массиве.

92. Точка в треугольниках

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

93. Мат в один ход

Вводятся (в обычной шахматной нотации) позиция белого короля, позиция белого ферзя и позиция черного короля. Ход белых. Позиция реальная, то есть черному королю в данный момент не угрожает ни белый ферзь, ни белый король. Требуется оценить каждую позицию по одной из двух возможностей:

1. мат в один ход возможен;
2. мат в один ход невозможен.

94. Палиндром (СТАНКИН, 1989)

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

95. Отражение от краев (МГИ, 1989)

Из шахматной доски вырезан прямоугольник, образованный N рядами шахматных полей по M полей в ряду. В I-ое черное поле J-ого ряда записывается число K<50. Оно записывается еще K-1 раз в черных полях: сначала по диагонали, идущей вверх и влево от исходного поля, затем вниз и влево от последнего поля предыдущей диагонали. Подобным образом ряд клеток "отражается" от краев поля и далее Если некоторое поле оказывается угловым, последовательность обрывается независимо от количества заполненных полей. Если некоторое поле встретилось в последовательности R>1 раз, в нем записывается число R*K.

Вывести на печать итоговое заполнение полей (незаполненные поля разрешается заполнять нулями). Исходные данные: N, M, I, J, K.

96. Засолка огурцов (МГИ, 1989)

При засолке в стеклянную банку вмещается 3 больших и 1 маленький огурец, либо 2 больших и 4 маленьких, либо 1 большой и 8 маленьких, либо 12 маленьких.  Определить, хватит ли 4 банок для засолки M маленьких и N больших огурцов, сколько банок потребуется и как они будут заполнены.

97. Волки, козы и капуста (МГИ, 1989)

В ограниченном пространстве в начале первой недели имеются L волков, M коз и N кочанов капусты. Волк, съев козу, живет неделю, коза съедает 1 кочан в день. Волк от голода помирает за 4 недели, а коза - за 3 недели. Животные не создают запасов пищи и потребляют свою еду исключительно в одиночку. При наличии пищи на всех животных никто не остается голодным, а при нехватке ее потребляют более сильные. В начальный момент животные голодны. Волки проворнее коз. Коза, съедаемая на Т-й неделе, не успевает поесть капусты. Определить, сколько волков, коз и кочанов капусты останется к началу десятой недели.

98. Окруженные элементы (МГИ, 1989)

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

99. Представление числа (МАСИ, 1988)

Задан массив натуральных чисел M длины N, а также натуральное число K. Установить, представимо ли K суммой каких-либо элементов массива M. Каждый элемент M может входить в сумму не более одного раза.

100. Сумма трех квадратов (МИСИ, 1988)

Найти все натуральные числа в пределах от 1 до N<101, квадраты которых не раскладываются в сумму трех квадратов натуральных чисел.

101. Шаблон (Москва, 1988, МАДИ)

Вводятся две символьных строки, ограниченные символом "пробел". Напечатать "да", если вторая строка может быть получена из первой заменой всех, возможно, содержащихся в первой строке символов "*" на любое число (возможно 0) любых символов. В противном случае напечатать "нет".

102. Расстановка знаков (Москва, 1988, МФТИ)

Дана последовательность цифр 1234567890. Требуется расставить между некоторыми из цифр знаки арифметических операций +, - и * так, чтобы значение полученного выражения, вычисленное по общепринятым правилам, было равно заданному числу M. Между двумя цифрами можно ставить только один знак операции. Операция * имеет больший приоритет, чем операции + и -. Задачу требуется решить для нескольких чисел М. Для каждого числа напечатать все возможные варианты расстановки знаков.

103. Батареи из единиц (МТИММП, 1988)

Дан одномерный массив чисел, состоящий только из нулей и единиц. Последовательность из не менее чем K рядом стоящих единиц называется "K-батареей". Для K = 2, 3, 4, 5 подсчитать количество K-батарей.

104. Полная спираль (МИИГАИК, 1988) (Кнут. Исскуство программирования)

Образовать квадратную матрицу последовательными целыми числами от 1 до M2 (0<M<30), располагая их по спирали, начиная с левого верхнего угла и продвигаясь по часовой стрелке.

105. Кратчайшая ломаная (Москва, 1988)

На координатной плоскости задано N (N<20) горизонтальных прямых и на каждой K-й (K=1,N) прямой задано MK (MK<10) узловых точек. Требуется найти минимальный по длине путь от нижней прямой к верхней, проходящей ровно через 1 узловую точку на каждой прямой. Результат выдать в виде координат узловых точек. Исходные данные: на первой строке - число прямых N, на каждой следующей строке - число узловых контрольных точек на соответствующей прямой, координата Y прямой, координаты X контрольных точек на этой прямой. Координаты X идут в порядке возрастания.

106. Построение последовательности (СТАНКИН, 1988)

Для заданного натурального N (N<1000) составить последовательность символов такую, что длина последовательности равна N, последовательность состоит из цифр "1", "2" и "3", в последовательности нет рядом стоящих одинаковых подпоследовательностей.

Примеры:
    правильно: n=4 - 1231, n=6 - 121321
    неправильно: n=6 - 123112, n=10 - 12312131213

107. Ходы ладьей (МАДИ, 1982, Отборочный тур)

Вводятся координаты N полей шахматной доски. Определить, можно ли, двигаясь ладьей только по заданным полям, обойти их все. Программа должна печатать ответ "да" или "нет".

108. Складывание полоски (МЭИ, 1988)

Полоска бумаги складывается пополам налево или направо до пяти раз. В сложенной полоске листки нумеруются сверху вниз. Напечатать расположение номеров листков во вновь развернутой полоске слева направо. Последовательность складывания задается в исходных данных символами "Л" и "П", например, "ЛПЛЛП".

109. Прямоугольники в картинке (Москва, 1981)

Вводятся N строк, образуя "картинку" размером Nx80 символов. Найти количество различных прямоугольников, состоящих из одного и того же символа (кроме пробелов), исключая одиночные точки.

110. Видимые точки (Москва, 1988)

Задан несамопересекающийся многоугольник и точка T, не лежащая на его границе. Координаты всех вершин многоугольника и точки T целые. Определить множество вершин многоугольника, "видимых" из точки T. Вывести координаты видимых вершин в том порядке, как эти вершины заданы во входных данных. Входные данные: координаты XT и YT точки T. Количество вершин многоугольника N. N пар координат Xi, Yi вершин многоугольника в порядке обхода вершин по часовой стрелке.

Видимость: точка А "видима" из точки B, если отрезок [A, B] не пересекает никакую сторону многоугольника.

111. Наводнение в пещере (МГИ, 1988)

Пещера представляет собой цепочку из N прямоугольных помещений. Помещение с номером i описывается неравенствами: ximin < x < ximax, yimin < y < yimax, zimin < z < zimax, причем величины ximin ... zimax - целые. Общая граница двух смежных помещений служит проемом, их соединяющим. Верхняя граница первого помещения служит входом в пещеру. В результате наводнения в пещеру попала вода в объеме Q.

Определить, какое количество воды окажется в результате в каждом помещении. Считать, что вода поступает медленно, т.е. пока в i-м помещении вода не достигнет нижнего края проема в i+1-е помещение, уровень воды в нем возрастает.

112. Натуральные числа (Москва, 1989, МЭИ)

Для введенного натурального числа N (1<=N<106). Определить количество натуральных чисел из интервала от 1 до N (включительно) таких, что цифры в их десятичной записи не убывают.

113. Пожар на складе (Москва, 1989)

На складе сложены в параллелепипед LxMxN (L - высота, M - ширина, N - длина, 1<L<M<N<10) единичные кубические секции. Для каждой секции (I, J, K) задано время ее горения - целое число минут от 1 до 5 или 0, если секция не горит. Через сколько минут кончится пожар, если горение параллелепипеда удовлетворяет следующим условиям:

• первой загорается секция (1,1,1) (и только она);
• возгорание секции происходит после того, как сгорит соседняя (касающаяся общей грани).

114. Суша и море (МИСиС, 1989)

Заданы две матрицы из единиц и нулей: A размера NxM и B размера KxL (1<N<20, 1<M<20, 1<K<20, 1<L<20). В матрице A единицы обозначают сушу, а нули - море. В матрице B единицы изображают некоторую фигуру. Определить, сколькими способами эту фигуру можно расположить на суше так, чтобы никакая часть фигуры не намокла в море (поворачивать фигуру нельзя, можно только перемещать по вертикали и горизонтали). Исходные данные: N, M, A, K, L, B. Распечатать исходные матрицы и число способов размещения фигуры в свободной форме.

115. Зашифрованное письмо (МИСиС, 1989)

Вводится зашифрованный текст из N строк, в каждой строке M символов и целое число K. Буквы и знаки текста при шифровке не изменялись, изменен только порядок следования символов. Расшифровка текста производится по следующему правилу. Выбирается первая буква текста (левая верхняя). Начиная со следующей буквы (второй) отсчитывается K-я буква и она выбирается из текста. Затем, начиная со следующей буквы, отсчитывается K-я буква и она выбирается из текста и так далее. Отсчет слева направо и сверху вниз. При подходе к концу текста счет продолжается с начала текста и при этом все выбранные буквы не учитываются (пропускаются). Расшифровка заканчивается, когда из текста будут выбраны все символы. Расшифровать введенный текст.

116. Наибольший отрезок (Москва, 1988, МИЭМ)

Задано M произвольных отрезков на числовой оси. Каждый отрезок задается значениями левой и правой границы. Найти длину наибольшего отрезка в их объединении.

117. Трассировка (Москва, 1988, МИЭМ)

Дано квадратное поле размером NxN клеток (N<80), в клетках помещены символы "Н" - начало трассы, "К" - конец трассы, "П" - преграда, "." - свободная клетка. Двигаться от клетки к клетке можно только по вертикали и горизонтали. Построить трассу минимальной длины, проходящую через свободные клетки и соединяющие "Н" и "К". Если трассу построить нельзя, то выдать соответствующее сообщение.

Исходные данные: N, изображение поля. Вывод результата: изображение поля с трассой, представленной "*" или сообщение о невозможности построить трассу.

118. Точка и многоугольник (Москва, 1988, МИЭМ)

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

119. Составное число (МИСиС, 1987)

Найти наименьшее составное число N такое, что N+2=M2, где M - некоторое нечетное число.

120. Заработная плата (МТИММП, 1987)

Дан фонд заработной платы (целое число) бригады из N человек, работающих на единый наряд, и массив КТУ. Определить зарплату каждого работника в соответствии с КТУ так, чтобы зарплата делилась на 5.

121. Инфиксная форма (МИИТ, 1987)

В алгебраическом выражении используются однородные десятичные операнды без знака, равноприоритетные бинарные операции (+, *, /, -) и круглые скобки. Преобразовать выражение в инфиксную форму без скобок.

122. Непересекающиеся ломаные (МИИТ, 1987)

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

123. Отрезки в квадрате (МИРЭА, 1987)

Дан квадрат с целочисленной длиной стороны и некоторое количество отрезков. Концы отрезков расположены только на двух параллельных сторонах. В одной внутренней точке пересекаются не более двух отрезков. Определить число областей, на которые разобьется квадрат N отрезками (0<N<100). Исходные данные: N, A(N) - массив координат левых концов; B(N) - массив координат правых концов.

124. Прямоугольник и круги (МИРЭА, 1987)

Прямоугольник образован линиями пересечения четырех прямых X=A, X=B, Y=-C, Y=C, где A<B, C>0. Задано множество кругов с центрами в точках (Ki, 0) и радиусами Ri, где 1 < i < N. Определить, покрывают ли круги заданный прямоугольник.

125. Кафе-мороженое (Москва, 1987. МИРЭА)

После каждого занятия три члена математического кружка заходят в кафе-мороженое. При этом в кружке действует строгое правило: после каждого визита в кафе никакие двое из участников этого визита потом больше мороженое не едят. На последнем занятии выяснилось, что теперь члены кружка не смогут есть мороженое втроем. Сколько могло быть занятий кружка, если в кружке N человек (N>2). Приведите один из возможных ответов.

126. Дорога в лесу (Москва, 1987. МИСиС)

План леса задан N тройками чисел (Xi, Yi, Ri), где (Xi, Yi) - координаты центра i-го дерева, а Ri - его радиус. Провести в этом лесу прямолинейную дорогу наибольшей ширины между деревьями в направлении, заданном вектором (a, b) так, чтобы ее обочины с обеих сторон касались деревьев. В качестве результата выдать ширину найденной дороги и номера двух деревьев, которых она касается, одного слева и одного справа, либо сообщение о том, что не вырубая деревьев, дорогу провести невозможно.

127. Пересечение многоугольников (Москва, 1987)

В первом квадранте плоскости XOY в области 80x80 заданы координатами вершин два прямоугольных несамопересекающихся многоугольника. Следует определить общую область, принадлежащую этим многоугольникам. Координаты вершин заданы последовательностью пар чисел, задающих координаты (X, Y) вершин при обходе многоугольников по часовой стрелке, начиная с каждой левой нижней вершины каждого многоугольника. Общую область следует отобразить в виде булевой матрицы 80x80, единичные элементы которой соответствуют общей области, а нулевые - нет. Исходные данные: число вершин первого многоугольника, пары координат вершин (x, y) первого многоугольника, число вершин второго многоугольника, пары координат вершин (x, y) второго многоугольника.

128. Наикратчайший путь (МИСИ, 1986)

A и B - левый верхний и правый нижний углы прямоугольной решетки. Из A в B ведет система дорог, топологически эквивалентная следующей: Известны отрезки дорог Lij между каждыми двумя соседними перекрестками i, j (0<Lij<9, Lij - целое число от 0 до 9). Определить длину наикратчайшего пути из A в B, напечатать номера последовательно проходимых узлов i, j сети по этому кратчайшему пути.

129. Группы чисел (МГИ, 1986)

Вводится число N (N<20) и N целых чисел, каждое из которых состоит из 20 цифр. Найти среди этих чисел все четные, среди остальных все кратные трем, среди остальных все кратные пяти и все остальные. В таком порядке их вывести на печать. Перед каждой группой чисел вывести ее название.

130. Прямоугольное пастбище (МГИ, 1986)

Прямоугольное пастбище разбито на одинаковые ячейки, образующие N рядов по M ячеек в каждом ряду (N<10, M<10). Каждая ячейка, кроме одной, имеет два входа, последняя - только один. Известно, что маршрут обхода пастбища без повторения ячеек существует (при сделанных предположениях он единственный).  Найти этот маршрут, то есть последовательность пар (I, J). Границы ячеек ориентированы по странам света, которым присвоены следующие коды: 1 - восток, 2 - север, 3 - запад, 4 - юг. Исходные данные представлены в следующем виде: N, M и M пар кодов сторон света для первого и второго входов в ячейку; если вход только один, то второе число равно 0.

131. Разрезание прямоугольника (1984)

Вводятся целочисленные размеры бумажного прямоугольника MxN и 4 пары целочисленных размеров прямоугольных частей MIxNI (I=1..4) на которые необходимо разрезать исходный прямоугольник так, чтобы не было обрезков бумаги. Определить, можно ли выполнить это задание и напечатать соответствующее сообщение. Напечатать исходный прямоугольник символами "1", "2", "3" и "4", чтобы одинаковые символы соответствовали своей части прямоугольника.

132. Квадрат из чисел (МЭСИ, 1986)

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

133. Четырехстороннее домино (1) (Москва, 1986, МИИТ)

Имеются 9 квадратных фишек, каждая из которых разделена диагоналями квадрата на четыре части. На каждой части написано некоторое целое число, причем все числа на одной фишке различны.

Необходимо разместить эти фишки на доске 3x3 так, чтобы на соприкасающихся гранях фишек стояли одинаковые числа, либо диагностировать невозможность подобного размещения.

134. Четырехстороннее домино (2) (Москва, 1986, МИИТ)

Имеются K квадратных фишек, каждая из которых разделена диагоналями квадрата на четыре части. На каждой части написано некоторое целое число, причем все числа на одной фишке различны. Необходимо выбрать из этого множества 4 фишки, которые могут быть размещены на доске 2x2 так, чтобы на соприкасающихся гранях фишек стояли одинаковые числа, либо диагностировать невозможность такого выбора.

135. Буквы в таблице (СТАНКИН, 1986)

Прямоугольная клетчатая таблица представляет собой экран NxM, на котором белые клеточки образуют фон, а черные - изображение. На экране прямыми линиями, параллельными краям таблицы, изображены буквы Г, Е, Н, О, Р, С, Ь. Букв на экране много. Буквы расположены хаотически, между собой не соприкасаются. Размеры букв и соотношения размеров в букве - самые разные. Толщина линий - одна клетка. Параллельные линии в букве имеют одинаковую длину и между ними всегда есть промежуток. Перпендикулярные линии стыкуются общей клеткой. Подсчитать количество букв каждого вида.

136. 6 натуральных чисел (Москва, 1986, МИТХТ)

Найти минимальное число, которое можно представить в виде суммы квадратов 6 натуральных чисел не единственным образом.

137. Календарь (Москва, 1987, МЭСИ)

Вводятся даты в формате ДДММГГ из интервала времени от 01.01.80 до 31.12.99. Для каждой введенной даты подсчитать количество таких же дней недели в интервале времени от 01.01.80 до этой даты. Предусмотреть проверку корректности заданных дат и печать сообщений об ошибках.

138. Перестановки в массиве (МФТИ, 1986)

Задан целочисленный массив N длины K, элементы которого пронумерованы от 1 до K. Составить программу перестановки элементов массива N таким образом, чтобы в преобразованном массиве сначала располагались нечетные по номерам элементы массива N, а затем элементы с четными номерами. При этом порядок следования элементов в преобразованном массиве должен соответствовать порядку их следования в массиве N.

Алгоритм преобразования массива N должен быть таким, чтобы дополнительная память, используемая программой, не зависела от K. Отпечатать исходный массив и преобразованный.

139. Перевертыши (Москва, 1986 МЭСИ)

Задан набор слов. Определить, можно ли из всех слов данного набора составить перевертыш, и если можно, то составить и распечатать (перевертыш - это строка, которая читается слева направо и справа налево, если исключить пробелы: ДОРОГА НАЛЕВО ВЕЛА НА ГОРОД).

140. Треугольные мозаики (Москва, 1986 МИСиС)

Треугольной мозаикой называется плоская связная конфигурация, состоящая из равных треугольников, касающихся друг друга по общим сторонам (из каждого треугольника можно попасть в любой другой, пересекая стороны). Составить программу, которая могла бы распечатать любую треугольную мозаику, состоящую не более чем из семи треугольников, в виде какой-либо наглядной картинки.

Исходные данные. Способ кодирования мозаики для ввода в программу придумывается автором программы. Ограничение - код должен быть набором не более чем из 20 цифр.

141. Максимальный квадрат (Москва, 1986. СТАНКИН)

Некоторое количество клеток на клетчатой доске размером MxN занято фишками. Доске соответствует матрица. Свободная клетка кодируется нулем, занятая - единицей. Найти один из квадратов максимальной площади, целиком состоящий из незанятых клеток. Напечатать площадь квадрата и координаты верхнего левого угла, если площадь не нулевая. Исходные данные: M, N, матрица

142. Восстановление решетки (Москва, 1986. МИСИ)

Имеется прямоугольная решетка размера MxN (M>1, N>1), в которой все соседние по вертикали и горизонтали узлы соединены звеньями. Узлы решетки пронумерованы случайным образом от 1 до M*N (M*N<86). Вводятся пары чисел, являющиеся номерами концов всех звеньев решетки. Напечатать решетку в виде матрицы номеров узлов.

143. Выход спирали (Москва, 1983, I тур)

Дана матрица A размером MxN (M>2, N>2, N<=20). Элементами матрицы могут быть целые двузначные числа. От элемента A(I,J) проведена спираль по часовой стрелке шага K. Спираль завершается при первом выходе за границу матрицы. Найти максимальное значение из всех промежуточных алгебраических сумм элементов матрицы A, лежащих на пути развертывающейся спирали. Сумму напечатать.  Вводятся: M, N, I, J, K и матрица A

144. Каноническое разложение (Москва, 1983, I тур)

Вводится пара чисел M и P, причем P - простое и M>P. Определить, в какой степени число P входит в каноническое разложение числа M! (M-факториал).

145. Пирамидки из монет (Москва, 1988, МИСиС)

Есть набор монет разных диаметров. Сложить их в пирамидки так, чтобы количество пирамидок было минимальным, а в каждой пирамидке разность диаметров монет, из которых она сложена, была постоянной.

146. Крестики-нолики (Москва, 1987, МИСиС)

На поле 10x10 задана позиция игры "Крестики-нолики" (символы "Х", "О" или пробелы). Определить, выигрывают ли "X" одним ходом и напечатать этот ход. Если нет, то определить, выигрывают ли ответным ходом "О".

147. Кирпичная ограда (Москва, 1987, МИСИ)

Ограда строится из кубических кирпичей одинакового размера следующим образом: выкладывается прямоугольник KxL кирпичей шириной в один кирпич, затем на него укладываются еще такие же прямоугольники. Высота ограды - M кирпичей. Вводится целое число N - суммарное количество кирпичей. Определить, сколько разных оград можно построить (при разных M, L, K)?

148. Число из нулей и единиц (Москва, 1987, МИСИ)

Найти такое наибольшее число из нулей и единиц, чтобы последовательности из N подряд цифр не повторялись (1<N<=11).

149. Редактирование массива (Москва, 1987, МАТИ)

Массив называется отредактированным, если разность между любыми двумя его соседними элементами по модулю не превышает некоторого заданного числа E. Вводится целочисленный массив A из N элементов и число E. Отредактировать массив, изменив минимальное число элементов.

150. Ближайшее большее (1986)

Вводится натуральное десятичное число, количество цифр в котором не превышает 80. Напечатать ближайшее большее число с той же суммой цифр.

Приложение 1.

В нижеследующей таблице приведены места, занятые в разные годы в московских городских олимпиадах по программированию сборной командой МАДИ и участниками команды МАДИ в личном зачете. В личном зачете отсутствуют фамилии участников команды, не решивших ни одной задачи. Таким участникам, по установившейся на олимпиадах по программированию традиции, места в личном зачете присваивались в алфавитном порядке, по этой причине точная информация о них безвозвратно утеряна.

Приложение 2.

Расшифрованные названия московских институтов (на 1990 год)

Back to Alex Pokras Home Page

(C) Alex Pokras, 1999