Районные олимпиады

 

1987-88 учебный год

1. Написать алгоритмы перехода улицы с двусторонним движением транспорта при наличии и отсутствии светофора.

2. Некто стоит у реки с чайником емкостью 3 литра и кувшином 5 лит­ров. Ка­ким образом он может отмерить 4 литра? Написать алгоритм решения этой задачи.

3. Даны числа a, b, c, x. Составить алгоритм вычисления y=ax²+bx+c с исполь­зованием следующего набора операций: сложение, вычитание, возве­дение в квадрат, деление на два.

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

5. Дана последовательность u_k чисел Фибоначчи 1, 1, 2, 3, 5, ...  , т.е. u_k+2=u_k+1+u_k. Написать программу, которая проверит, делится ли число u₅₀ на 5.

6. Написать программу вычисления суммы 1+1/2+1/3+...+1/n для задан­ного n. Результат вычисления выразить в форме дроби p/q, где p и q - целые несократимые числа.

 

1988-89 учебный год

1. Написать программу, которая вводит два натуральных числа X и Y, вы­числяет (не употребляя операцию X^Y) и печатает X в степени Y.

2. Число из n цифр называется числом Армстронга, если сумма цифр, возведен­ных в n-ю степень, равна самому числу. Написать программу нахож­дения всех чисел Армстронга, состоящих из двух, трех и четырех цифр.

3. Дана таблица А[0:50]. Каждый ее i-ый элемент заменить на среднее арифме­тическое i+1, i, i-1 элементов, где i=1, 2, ..., 49. Дополнительную таб­лицу не вводить.

4. Составить алгоритм нахождения среди чисел 0,3; 0,3*1,3; 0,3*1,3*2,3; ... пер­вого, большего заданного a.

5. Используя графические команды, составить алгоритм рисования на кон­верте заданного почтового индекса.

6. Периодическая функция определена на всей числовой  прямой и имеет пе­риод 1. График этой функции на отрезке [0:1] имеет вид:

Написать программу вычисления значения y по значению x.

7. Вычислить значения выражений:

                           sin x+sin sin x+... +sin sin ... sin x,

                                                                                           ---------------

                                                                                                      n раз

sin x+sin x²+...+sin xⁿ,

sin x+sin²x+...+sinⁿx,

при x=0,5 и n=15.

8. Вычислить время движения тела по заданной скорости (км/час) и расстоя­нию (км). Напечатать время движения в часах, минутах и секундах.

 

1989-90 учебный год

1. По заданному n вычислить. Оценить для каких достаточно больших n будет работать ваша программа.

2. Можно ли разменять 25 рублей десятью купюрами достоинством в 1, 3 или 5 рублей? Тот же вопрос для девяти купюр.

3. Задан массив из нулей и единиц. Проверить строго ли они чередуют­ся.

4. Имеются 4 пакета и весы с двумя чашками без гирь. С помощью пяти взве­шиваний расположить пакеты по весу. Та же задача для пяти пакетов за семь взве­шиваний.

5. В таблице умножения столбиком

                                                   *          0          2          *

                                                               2          *          *

                                       -----------------------------

                                                   *          *          *          2

                                       1          *          *          1

                           2          *          *          *

   --------------------------------------------------

               1          0          *          *          *          *          *

действия производятся в троичной системе счисления. Восстановить утерян­ные цифры.

6. Найти k-ое простое число в арифметической  прогрессии 11, 21, 31, 41, 51, 61, ... . Привести ответ для k = 1, 10, 100, 1000 и т. д.

7. В таблице B(M), содержащей много нулей, заменить каждую группу подряд идущих нулей на один нуль. Дополнительную таблицу по возможности не использо­вать.

 

1990-91 учебный год

1. Два двузначных числа, записанных одно за другим, образуют четырех­знач­ное число, которое делится на их произведение. Найти эти числа.

2. Горизонтали и вертикали шахматной доски занумерованы числами от 1 до 8. Вводятся четыре числа a, b, c, d. Определить, одного ли цвета поля (a, b) и (c, d).

3. Вводятся 365 строк вида "юг", "северо-запад", "юго-восток" и т.д. - инфор­мация о направлении ветра в течении года. Напечатать, какое направ­ление ветра было преобладающим в каждом месяце.

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

5. Чему равно значение функции Ф(1990), вычисляемой по следующему алго­ритму?

ЦЕЛ АЛГ Ф( ЦЕЛ К )

НАЧ

   ЦЕЛ С,М,А1,А2

   С:=0; А1:=1; А2:=-1; М:=1

   ПОКА М < К

   НЦ       ЕСЛИ А1 > 0

               ТО С:=С+М

               ИНАЧЕ С:=С-М

               ВСЕ

   А1:=А1+А2; А2:=А1-А2; А1:=А1-А2; М:=М+1

   КЦ

   ЗНАЧ:=С

КОН

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

6. В поселке N домов, расположенных вдоль прямой дороги с одной стороны на равных расстояниях. В поселке проводят телефонную связь. В таблице T указано, сколько телефонных аппаратов надо установить в каждом доме. Каждый телефон должен быть связан с АТС отдельным проводом. Оп­ределить в каком доме надо установить АТС, чтобы суммарное расстояние от АТС до телефонных аппаратов было минимальным. Если решений несколько, достаточно найти любое. Кроме того известно, что в поселке очень много до­мов, а ЭВМ для проведения расчетов имеет малое быстродействие.

7. Из записи натурального числа выбросить цифры 1 и 5, оставив преж­ним по­рядок цифр. Например, число 527012 преобразуется в число 2702.

8. Найти такие две различные наименьшие степени натурального числа n, у которых три последние цифры одинаковы.

 

1991-92 учебный год

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

2. Бортовой компьютер крылатой ракеты выполняет только два арифме­тиче­ских действия: сложение и умножение, но на нем требуется постоянно вычислять с высокой скоростью значения полинома F(x)=x⁴+4x³+7x²+6x+2 для различных аргу­ментов x. Разработать такую схему вычислений, которая требует как можно мень­шего суммарного количества арифметических дейст­вий на одно вычисление значе­ния F.

3. Заданы натуральные числа a, b, c, d в записи химической реакции X_aY_b+ZZ_cY_d+X, где X, Y, Z - атомы или группы атомов. Написать алго­ритм, ко­торый находит такие коэффициенты, чтобы знак "стрелки" можно было заменить знаком равенства.

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

5. Составить программу поиска в тексте газетной статьи наиболее упот­реби­тельной аббревиатуры (например: СССР, США, ВЛКСМ и т.п.).

6. Если число атомов водорода (H) - A, число атомов кислорода (O) - B, число атомов серы (S) - C, то сколько молекул серной кислоты (H₂SO₄) мо­жет получиться? Написать и отладить программу, которая находит это число по трем натуральным числам A, B, C.

7. Составить программу проверки домашней работы первоклассника по мате­матике. На входе - строка типа "2+7=9" или "8-5=4", на выходе - сообще­ние о ее пра­вильности или неправильности. Можно ограничиться сложением и вычитанием од­нозначных чисел, попробуйте двузначные, умножение, деле­ние.

 

1992-93 учебный год

1. Дано действительное число x. Не пользуясь никакими другими ариф­метиче­скими операциями, кроме умножения, сложения и вычитания, вычис­лить 1-2x+3x²-4x³ и 1+2x+3x²+4x³. Разрешается использовать не более восьми операций.

2. Вычислить значение i-го бита (1i8) во введенном символе.

3. Дано натуральное число n (n9999). Верно ли, что все четыре цифры числа различны?

4. Два поля шахматной доски задаются в общепринятой нумерации (например, a1, h8). Выяснить можно ли с первого поля попасть на второе од­ним ходом слона. Если нет, то выяснить можно ли это сделать за два хода.

5. Дано натуральное число n, действительные числа x₁, x₂, ..., x_n. Вы­числить (x₁+2x₂+x₃)(x₂+2x₃+x₄)...(x_n-2+2x_n-1+x_n) в режиме пошагового вво­да данных.

6. Даны две строки, в каждой из которых содержится очень длинное на­тураль­ное число. В третьей строке сформировать их сумму.

7. Из двух одинаково упорядоченных массивов размером k и l сформи­ровать один массив размером k+l, упорядоченный в обратную сторону.

8. Расставьте машины по своим местам, не выводя их из гаража. Каждая ма­шина может передвигаться на ближнее свободное место вперед, назад, вле­во, вправо.

9. Тома "Детской энциклопедии" стоят в таком порядке: 1, 2, 6, 10, 3, 8, 4, 7, 9, 5. Как поставить их по порядку, если можно брать два соседних тома и ставить их, не меняя порядка, рядом на новое место (в начале, в конце или между двумя томами)?

10. Вычислить

.

11. Дано натуральное число n. Получить число, в котором переставлены первая и последняя цифры числа n.

12. Дано натуральное число n, равное выраженной в копейках цене неко­торого товара, например 317, 5005, 100 и т.д. Выразить цену в рублях и ко­пейках, например 3 руб. 17 коп., 50 руб. 05 коп., 1 руб. 00 коп. и т.д. (число копеек записывается всегда двумя цифрами).

13. Случайным образом перемешайте буквы во введенном слове (цифры во вве­денном числе).

 

1993-94 учебный год

1. Порядок для точек плоскости определен следующим образом: (x, y)<(u, v), если либо x<u, либо x=u и y<v. Перечислить точки заданного мно­жества точек на плоскости в соответствии с этим порядком.

2. Напечатать элементы заданной матрицы размером 5*5 в следующем по­рядке:

.

Элементы матрицы a_ij равны 5i+3j.

3. Функция f(n) определена для целых положительных чисел следую­щим обра­зом:

( - целая часть числа n/i).

Вычислить f(k) для k=15, 16, ..., 30.

4. Задан текст, в котором нет вхождений символов "(" и ")". Выполнить его сжатие, т.е. заменить всякую максимальную подпоследовательность, со­ставленную из более трех вхождений одного и того же символа, на (k)s, где s - повторяемый сим­вол, а k>3 - количество его повторений.

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

6. Перечислить все пары "соседних" простых чисел, не превосходящих задан­ного N, троичные представления которых получаются друг из друга за­писью цифр в обратном порядке (первая такая пара - это 5 и 7).

7. Определить допустимость хода шахматной фигуры на "пустой" доске. За­дано: положение фигуры до и после хода, название фигуры и ее цвет.

 

1994-95 учебный год

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

2. В заданном интервале [a, b] найти все натуральные числа, десятичная запись которых есть строго возрастающая или строго убывающая последовательность цифр. Далее выдать их количество.

3. Подсчитать количество строк заданной целочисленной матрицы n*n, являющихся перестановкой чисел 1, 2, ..., n.

4. Найти покрытие без наложений заданного клеточного поля A полями вида B . Например, поле  покрывается полями B, а поле  вообще нельзя покрыть без наложений такими полями. Способы задания клеточного поля и представления результатов придумайте сами.

 

1995-96 учебный год

1. Задано целое число N (1N1000000). Найти наименьшее натуральное число с произведением цифр равным N. Если такого числа нет, то вывести 0. Например, для N=10 программа печатает 25, а для N=13 - 0.

2. Всю неделю бутылка "Чегонадо" стоила k рублей, а пустая бутылка - l рублей. Компания друзей, собравшаяся в понедельник, располагала первоначальным капиталом в n рублей и купила на все деньги "Чегонадо". Употребив все, они на следующий день сдали пустые бутылки, добавили сдачу с предыдущего дня и снова на все деньги купили "Чегонадо". Данная процедура продол­жалась каждый день, пока была возможность.

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

3. В последовательности цифр a₁,  a₂,  a₃, ... каждый член, начиная с четвертого, равен последней цифре суммы трех преды­дущих. Написать программу,  которая по заданным a₁, a₂, a₃ и N определяет a_N (N1000000000).  Алгоритм с  количеством  дейст­вий, пропорциональным N, недопустим.

4. Даны четыре слова. Написать программу, проверяющую, можно ли из данных слов составить кроссворд при условии, что каждое слово пересекается с двумя другими и располагается  сверху  вниз или слева направо.  Сетка не обязательно симмет­рична. Результат вывести в виде кроссворда.

 

1996-97 учебный год

1. Сообщество роботов живет по следующим законам:

- один раз в начале года они объединяются в группы по три или пять роботов;

- за год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых;

- роботы объединяются так, чтобы собрать за год наибольшее количество новых роботов;

- каждый робот живет три года после сборки.

Известно, что начальное количество роботов равно k и все они только что собраны. Сколько роботов будет через n  лет?

2. Во введенном тексте задано предложение, в котором встречается одно перечисление двух объектов с помощью предлога “и”. Поменять местами слова, соединенные этим предлогом. Например, текст “А и Б сидели на трубе” заменить на “Б и А сидели на трубе”.

3. Подсчитайте количество одно, двух, трех и четырех палубных кораблей, расположенных на поле для игры в “морской бой”. Корабли не могут быть изогнутыми и друг с другом не соприкасаются. Поле для игры задается в виде таблицы 10 на 10, каждый элемент которой равен либо 0, если клетка свободна, либо 1, иначе.

4. Дано целое число m. Вставить между некоторыми цифрами 1, 2. 3, 4, 5, 6, 7, 8, 9, записанными именно в таком порядке, знаки +, - так, чтобы значением получившегося выражения было число m. Например, если m=122, то подойдет следующее равенство 12+34-5-6+78+9. Если требуемая расстановка знаков невозможна, то сообщить об этом.

5. Коридор размером 2 на n (n<101) решили застелить покрытием, представляющим собой плитки размером 1 на 2. Сколькими способами это можно сделать, если надо обойтись наименьшим количеством плит и не должно быть незастеленной поверхности? Например, коридор 2 на 3 можно застелить тремя способами, а 2 на 4 - пятью.

6. Задан ряд последовательных натуральных чисел от n до m (n<m<1000), из которого удаляют сначала все числа, стоящие на нечетных местах. Затем из оставшегося ряда удаляют все числа, стоящие на четных местах. Эти действия повторяют до тех пор пока не останется одно число. Какое это число?

 

1997-98 учебный год

1. По заданным n (n<7) и k определить сколько существует n-значных чисел, заканчивающихся цифрой k и делящихся на 3.

2. Последовательность целых чисел строится следующим образом:

- первое задается (обозначим его через a),

- каждое следующее число является суммой цифр квадрата предыдущего.

Например, если a=4, то получится последовательность 4, 7, 13, 16, ....

По заданным a и n определить n-е число в этой последовательности. Известно, что a<10000 и n<1000000.

3. По заданному n (1<n<7) определить все n-значные числа, обладающие свойством: среднее арифметическое всех чисел, получающихся из исходного числа различными перестановками его цифр, равно самому числу.

4. Заданы натуральные числа k и n (k<100). Из числа 12345123445... 123455 (цифры 12345 записываются k раз) вычеркнуть n цифр так, чтобы оставшееся число было максимально возможным.

Например, если из числа 12345 вычеркнуть 3 цифры, то должно получиться 45.

5. В романе n глав (n<100). В i-й главе a_i страниц. Требуется издать роман в k томах так, чтобы количество страниц в самом толстом томе было минимально. Делить главы нельзя. Написать программу определения количества страниц самого толстого тома.

Например, роман из 3 глав (1, 2, 2 страницы, соответственно) издать в 2 томах можно двумя способами:

1-й том - 1 и 2 главы, 2-й том - 3 глава;

1-й том - 1 глава, 2-й том - 2 и 3 главы.

Тогда в первом способе самый толстый том имеет 3 страницы, а во втором - 4 страницы. Таким образом ответом будет - 3 страницы.

6. В десятичной записи дроби m/n вычеркнули k-ю цифру после запятой. Сравнить (меньше, больше, равно) полученное число с дробью m/n. Известно, что m, n < 1000 и k < 30000.

Например, если в дроби 1/3 вычеркнуть 10-ю цифру, то получится опять дробь 1/3 и ответом будет - равно.

7. Имеется n карточек, на каждой стороне каждой карточки написано одно целое число. Известно, что каждое из чисел 1, 2, ..., n встречается на карточках дважды. Требуется узнать можно ли карточки выложить так, чтобы каждое из чисел 1, 2, ..., n было на верхней стороне одной из карточек; если можно, то указать какие из них надо перевернуть для этого.

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

Например, если заданы 3 карточки с числами - 1 и 2,  3 и 2, 1 и 3, то для решения задачи достаточно перевернуть 1-ю карточку или (другое решение) 2-ю и 3-ю карточки.

8. 3-х мерное пространство разбито на кубики с ребром длины 1. Сколько из них помещается в сфере радиуса r, центр которой находится в вершине одного из кубиков? Натуральное число r задано и не больше 1000. Для r=3 таких кубиков 56.

 

1998-99 учебный год

1. Сколько среди n-значных чисел, состоящих из цифр 2 и 5, таких, у которых две двойки не стоят рядом.

Входные данные.

Натуральное число n вводится с клавиатуры.

Выходные данные.

Полученное число вывести на экран.

Технические ограничения.

n £ 21.

Пример.

Входные данные	Выходные данные
2	3

 

2. Записать в таблицу n*n четыре буквы “a”, “b”, “c” и “d” так, чтобы в любых двух клетках, между которыми ровно одна клетка (по горизонтали, вертикали или диагонали), содержались различные буквы. В соседних клетках могут быть одинаковые буквы.

Входные данные.mso-bidi-font-size:10.0pt'>n £ 100.

Пример.

Входные данные	Выходные данные
3	594

 

2. Для действительного числа x обозначим через [x] – целую часть x, а через {x} – дробную часть.

По заданному N найти наименьшее положительное число x, удовлетворяющее неравенству [x]*{x}³N.

Входные данные.

Натуральное число N вводится с клавиатуры.

Выходные данные.

Найденное число вывести на экран в виде десятичной периодической дроби.

Технические ограничения.

N £ 1000.

Пример.

Входные данные	Выходные данные
3	4.75

 

3. На доске записано число N. Каждую секунду к числу на доске добавляется его максимальный простой делитель. Через сколько секунд число на доске будет делиться на заданное число P?

Входные данные.

Числа N и P вводятся с клавиатуры.

Выходные данные.

Ответ выдать на экран.

Технические ограничения.

Числа N и P являются положительными целыми и не превышают 32767.

Пример.

Входные данные	Выходные данные
5 2	1

 

4. Можно ли заданные n  натуральных чисел x₁, x₂,…, x_n расставить по кругу так, чтобы любые два соседних числа имели общую цифру.

Входные данные.

Все числа вводятся с клавиатуры в следующем порядке: n, x₁, x₂,…, x_n.

Выходные данные.

Ответ выдать на экран, указав номера чисел в одной из таких расстановок, если такое возможно. Иначе напечатать сообщение «Такой расстановки нет».

Технические ограничения.

Число n<10, а числа x₁, x₂,…, x_n являются положительными целыми и не превышают 32767.

Пример.

Входные данные	Выходные данные
3 12 51 25	1 3 2

 

2000-2001 учебный год

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

Входные данные.

Содержатся в текстовом файле INPUT.TXT.

Выходные данные.

Вывести в текстовый файл OUTPUT.TXT возраст Пети или сообщение “ERROR’ если Петя ошибся в вычислениях.

Технические ограничения.

Возраст Пети не превышает 100 лет.

Пример.

Входные данные	Выходные данные
120	5

 

2. Шахматная. На шахматной доске стоят ферзь и конь. Каждая фигура задана своими координатами. Определить количество полей, которые находятся под боем.

Входные данные.

В текстовом файле INPUT.TXT в первой строке записаны координаты ферзя, во второй – коня.

Выходные данные.

Вывести в текстовый файл OUTPUT.TXT найденное количество полей.

Пример.

Входные данные	Выходные данные
a1 h8	22

4. Квадрат. Квадрат разбит на n² прямоугольников. Площади некоторых из них указаны на рисунке (выполненном не в масштабе). Найдите площадь пря

4

 

8