---------105.PAS--------- Два выпуклых многоугольника р и Р на плоскости заданы координатами вершин (x1,y1), (x2,y2) ,..., (xm,ym); (X1,Y1), (X2,Y2) ,..., (XM,YM). Вершины перечислены в произвольном порядке. Написать алгоритм, определяющий расстояние между многоугольниками. ---------111.PAS--------- 5. Анализ циклов В символьном массиве PROGRAM [1:N] записана программа на языке БЕЙСИК. В каждом элементе массива содержится один опера- тор, его номер равен номеру элемента массива. Циклы со счетчи- ками оформляются в языке БЕЙСИК так: в начале цикла находится оператор FOR <имя переменной-счетчика>=<выражение> TO <выраже- ние> STEP <выражение>, в конце цикла - оператор NEXT < имя счетчика >. Имя переменной состоит из одного или двух симво- лов: первый - латинская буква, второй - латинская буква или цифра. Написать алгоритм, проверяющий правильность взаимного расположения циклов в заданной программе. Операторы переходов не используются. Предполагается, что каждый оператор FOR и NEXT в отдельности написан правильно; во всех операторах цикла в программе начальное, конечное значения и шаг счетчика заданы числами, знак шага совпадает со знаком разности конечного и начального значений. ---------112.PAS--------- 6. Контекстная замена (Ukr'90) Заданы символьные строки S0, S1 и S2. Написать алгоритм, заменяющий в строке S0 все подстроки, равные S1, на подстроки, равные S2. Если две подстроки, равные S1, перекрываются, в первую очередь обрабатывается левая. ---------116.PAS--------- 10. Телефон-1 Поселок состоит из N домов, расположенных вдоль прямой до- роги с одной стороны на равных расстояниях. В поселке проводят телефонную связь. В таблице Т указано, сколько телефонных аппа- ратов надо установить в каждом доме. Написать алгоритм, опреде- ляющий номер дома, в котором надо установить АТС, чтобы суммар- ное расстояние от АТС до всех телефонных аппаратов было мини- мальным. Если оптимальных домов несколько, достаточно найти лю- бой. Каждый телефон связан с АТС отдельным проводом. ---------124.PAS--------- 18. Месторождение-2. Геологи ищут месторождение, определяя концентрацию полез- ного вещества в пробах. Пробы берутся в разных точках прямоу- гольника Х1 Ж Х Ж Х2, Y1 Ж Y Ж Y2 на плоскости. В точке прямоу- гольника (Хm, Ym) с максимальной концентрацией вещества нахо- дится месторождение. Зависимость концентрации С вещества в точ- ке (Х, У) от расстояния между этой точкой и точкой местонахож- дения (Хm, Ym) - монотонно убывающая функция расстояния С(S) неизвестного вида. Расстояние S = Записать программу, определяющую координаты месторождения Хm, Уm с отклонением расстояния не более чем на (EP), сделав как можно меньше "проб" - определений С в точках ( Х, У ). Раз- решается при определении места очередной "пробы" использовать результаты предыдущих проб. ---------125.PAS--------- 19. Терминалы-3 В разных помещениях здания надо установить N терминалов. Заданы их координаты X[i], Y[i], Z[i], i=1,...,N. Написать ал- горитм, определяющий, в какой точке здания надо установить ЭВМ, чтобы суммарная длина кабелей связи, идущих от каждого терминала к ЭВМ, была минимальной. Кабели могут проходить только вертикально или горизонтально параллельно стенам. а). Решить задачу в предположении, что к каждому термина- лу должен идти отдельный кабель. б). Решить задачу в предположении, что несколько термина- лов могут полностью или частично использовать одни и те же участки кабелей. в). Решить задачу в предположении, что по каждому участку кабеля может идти не более К линий к терминалам. ---------127.PAS--------- 21. Частотный словарь Составить алгоритм, подсчитывающий для заданного текста количества вхождений в него всех слов, встречающихся в нем хо- тя бы один раз. Различные формы слов при склонении/спряжении считать отдельно. ---------128.PAS--------- 22. Поиск перевертышей Символьная строка содержит последовательность слов, раз- деленных пробелами. Найти все пары перевертышей - слов, одно из которых читается слева направо так же, как второе справа налево. ---------130.PAS--------- 24. Эйлеров путь (Ukr'89) Есть N селений. Некоторые селения попарно соединены тро- пинками, вне селений никакие две тропинки общих точек не име- ют. В целочисленной таблице ТРОПЫ[1:N, 1:N] задана информация о тропинках; количество тропинок между i-тым и j-тым селениями равно значению элемента таблицы ТРОПЫ[i,j]=ТРОПЫ[j,i]0 (в том числе для i=j). а). Написать алгоритм, определяющий, можно ли пройти по всем тропинкам, не проходя ни по одной из них дважды. б). Написать алгоритм, определяющий путь, проходящий по каждой тропинке ровно один раз, если такой путь существует. в). Написать алгоритм, определяющий все пути, проходящие по каждой тропинке ровно один раз. ---------131.PAS--------- 25. Кратчайший путь В некотором государстве имеется N городов, некоторые из них соединены дорогами. Для каждого города задан список горо- дов, связанных с ним дорогой, и список длин соответствующих дорог. Между любыми городами есть хотя бы одна цепочка дорог. Неравенство треугольника может не выполняться. а) Выделены два города. Написать алгоритм, определяющий путь минимальной длины между этими городами. б) Написать алгоритм, определяющий для данного города ми- нимальные пути во все остальные города. ---------14.PAS--------- 3.а/ Два человека играют в такую игру:имеется поле MxN, игро- ки по очереди ставят на поле по одному шахматному коню. Коня можно ставить на любую клетку, которая не занята и не находит- ся под боем какого-либо коня,поставленного раннее любым из игроков. Игрок, который не сможет сделать очередной ход, счи- тается проигравшим. Написать программу, выступающую за игрока, имеющего выигрыш- ную стратегию. б/ Задача аналогична задаче 3.а/, но на поле выставляются слоны. ---------141.PAS--------- 2. Поиск месторождения (Киев'89). Геологи ищут месторождение, определяя концентрацию полез- ного вещества в пробах. Пробы берутся в разных точках отрезка [X1, X2]. В точке Xm с максимальной концентрацией вещества на- ходится месторождение. Зависимость концентрации С(X) вещества от координаты точки - функция, монотонно возрастающая на [X1, Xm] и убывающая на [Xm, X2]. Написать программу, определяющую точку месторождения Xm с отклонением расстояния не более, чем на (EP), сделав как можно меньше "проб" - определений С(X). Разрешается при определении места очередной пробы использовать результаты предыдущих проб. ---------142.PAS--------- 3. Модель жизни по Конвею (Обл'89). В некоторых клетках поля М x N живут организмы; задается их расположение в начальный момент времени, например: Если в текущий момент времени по соседству с организмом (по горизонтали,вертикали и диагонали) есть два или три орга- низма,он будет жить и в следующий момент времени; если по со- седству с организмом меньше двух или больше трех организмов, в следующий момент времени он умрет или от одиночества или от перенаселения. Если рядом с пустой клеткой находится ровно три организма, в следующий момент времени в ней появится новый ор- ганизм. Пример последовательных состояний поля: Написать программу, вводящую начальное расположение орга- низмов, вычисляющую наиболее эффективным способом и выводящую положение организмов для последующих моментов времени. ---------145.PAS--------- 6. Длиннейшая монотонная подпоследовательность (ИК'87). Дана последовательность N чисел. Ее подпоследовательнос- тью будем называть любое подмножество множества ее элементов, упорядоченное так, чтобы индексы элементов последовательности возрастали. а). Составить алгоритм, вычисляющий для данной конечной последовательности длину ее монотонно убывающей подпоследова- тельности с максимальным количеством элементов. б). Составить алгоритм, вычисляющий для данной конечной последовательности ее монотонно убывающую подпоследователь- ность с максимальным количеством элементов. в). Составить алгоритм, вычисляющий для данной конечной последовательности все ее монотонно убывающие подпоследова- тельности с максимальным количеством элементов. ---------147.PAS--------- 8. Быки и коровы. В игру "Мастермайнд" ("Быки и коровы") играют так: один человек задумывает четырехзначное число, в котором никакие две цифры не совпадают; другой игрок называет четырехзначные числа с попарно несовпадающими цифрами; первый игрок для каждого из этих чисел сообщает второму общее количество его цифр, имею- щихся в задуманном числе, и количество совпадающих цифр в оди- наковых разрядах названного и задуманного числа. Второй игрок должен угадать задууманное число за как можно меньшее количе- ство вопросов. Написать программу, играющую: а) за задумывающего игрока; б) за отгадывающего игрока. ---------177.PAS--------- Задача 2 (Багдадский вор) В высотном здании (150) этажей багдадского банка возник пожар. Огонь распространяется по зданию со скоростью 1 этаж в минуту. В здании имеется лифт, который движется со скоростью 10 этажей в минуту и застревает, если проходит через этаж, охва- ченный огнем. В момент начала пожара лифт стоит на первом этаже и там же находится знаменитый багдатский вор, задача которого вынести из банка как можно больше хранящихся там золотых монет, воспользовавшись паникой и тем, что служащие спешно покидают здание по наружным пожарным лестницам. Вор знает номера этажей, на которых хранятся монеты, и точные их количества на каждом таком этаже. Для поиска монет на этаже и переноса их в лифт требуется полторы минуты. Написать программу, которая определяет максимально возмож- ное количество монет, которое может унести вор. Программа ввод- ит номер этажа, где начался пожер, и затем последовательность из 149 чисел - количества монет со 2 по 150 этажи (на первом этаже монет нет). ---------181.PAS--------- 2. Вычислите, в какой координатной четверти расположен треугольник, образованный прямой, заданной уравнением y=ax+b, и осями координат. ---------201.PAS--------- 6. Даны натуральные m,n. Составить программу, которая для введенных пользователем натуральных M и N печатает самую короткую десятичную а) 1/n б) m/n. в форме: 0. P1 P2 ... PI (R1 R2 ... RJ), где R1 R2 ... RJ - период. Так, при M=1, N=2 печатается 0.5(0), а при M=1, N=3 - 0.(3). Считается, что период конечной дроби состоит из цифры 0. ---------229.PAS--------- 1. Дана вещественная таблица a[1], a[2],...,a[1000]. Определить максимальное количество подряд идущих положительных элементов последовательности, не прерываемых ни нулями, ни отрицательными элементами. ---------238.PAS--------- 8. При проведении физического эксперимента по фиксации траектории движения частиц с помощью ЭВМ детекторы сгруппированы следующим образом: Д Д ... Д Д Д ... Д ......... Д Д ... Д Перекрытая детекторами область отображается в памяти ЭВМ двумерным массивом M[1:N,1:K], элементы которого представляют собой цифровую фотографию исследуемой области. При фиксации элементарной частицы детекторами в позиции (I,J) соответствующий элемент матрицы M принимает значение 1, в противном случае 0. Определите, содержит ли данная цифровая фотография информацию, которая может быть интрепретирована как след прямолинейной траектории, начинающейся и заканчивающейся за пределами фотографии. ---------240.PAS--------- 512 2. Найти все цифры десятичной записи числа 3 . ---------241.PAS--------- 1. Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников. Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD. Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника. ---------242.PAS--------- 2. Построить алгоритм, моделирующий на экране дисплея движение с постоянной скоростью V двух окружностей радиуса R внутри прямоугольной области, заданной координатами своих вершин. В момент начала движения координаты центров окружностей - (X1,Y1) и (X2,Y2), а углы между траекториями движения и вертикальной осью координат - A1 и A2. Столкновения окружностей между собой и с границами области - упругие. ---------243.PAS--------- 3. Данные N косточек домино по правилам игры выкладываются в прямую цепочку начиная с косточки, выбранной произвольно, в оба конца до тех пор, пока это возможно. Построить алгоритм, позволяющий определить такой вариант выкладывания заданных косточек, при котором к моменту, когда цепочка не может быть продолжена, "на руках" останется максимальное число очков. ---------244.PAS--------- 4. Имеются два одинаковых диска. На каждом из них есть круглое отверстие радиуса R, касающееся границы диска. Диски расположены горизонтально, плотно прижаты друг к другу и скреплены общей осью, проходящей через их центр вращения. Верхний диск неподвижен, а нижний равномерно вращается с заданной угловой скоростью W2. Вдоль границы верхнего диска катятся с постоянной угловой скоростью W1 N шаров радиуса R. Шары расположены плотно друг за другом и пронумерованы цифрами от 1 до N. Если при совпадении отверстий на дисках шар проваливается, то плотность цепочки шаров "мгновенно" восстанавливается. Построить алгоритм, позволяющий определить номера первых M шаров, выпавших при совпадении отверстий на дисках, если в момент начала движения угол между центрами отверстий верхнего и нижнего дисков был равен A1, а угол между центрами отверстия верхнего диска и первым шаром цепочки - А2. Угол сектора, по дуге которого расположена цепочка шаров, равен А3. ---------246.PAS--------- 2. "Караван". Географическая карта местности задана квадратной сеткой определенного масштаба. В узлах сетки известна высота над уровнем моря. Между соседними узлами высота изменяется плавно. Караван перемещается только по линиям сетки. (Перемещение по диагонали запрещается). Путь между двумя соседними точками с угло наклона больше 45 градусов считается непроходимым. Провести караван из точки А(X1,Y1) в точку B(X2,Y2) по пути с наименьшим перепадом высоты или сообщить об отсутствии решения. Примечание: Перепадом высот на маршруте называется разность высот между самой высокой и самой низкой точками маршрута. ---------247.PAS--------- 3. "Царевна". В одной из клеток поля nхn (n>1) Кощей Бессмертный спрятал Марью Царевну, создав еще неизвестное число m (11 WWWW . нц WW . . если остаток (k,i) = 0 WWWW . . . то печать (i) WW . . . k:= k/i . . . иначе i:=i+1 WWWWW . . все WWW . кц WW кон WWW Команда печать (i) печатает число i; остаток (k,i) - остаток от деления k на i. Какие числа будут напечатаны при исполнении алгоритма задачаI (n) для целого n1 ? Обоснуйте ответ. ---------252.PAS--------- Т2. Прямоугольник, стороны которого параллельны осям координат, будем задавать координатами его левого нижнего и правого верхнего углов. (Всего, таким образом, для задания прямоугольника понадобятся 4 числа). Заданы два прямоугольника ПрI и Пр2. Определить площади той части прямоугольника ПрI, которая не входит в Пр2. (На рисунке заштрихована эта часть для разных вариантов расположения ПрI и Пр2. Возможны и другие варианты; алгоритм должен быть пригоден для всех вариантов.) ---------253.PAS--------- Т3. В стране имеется n городов, пронумерованных от 1 до n; между некоторыми из них налажено самолетное сообщение. Таблица есть_рейс [1:n,1:n] содержит информацию о рейсах: есть_рейс[i,j] равно 1, если i<>j и из города i есть рейс в город j, и равно 0 в противном случае. (Рейсы проходят без промежуточных посадок; наличие рейса из i в j не гарантирует наличия рейса из j в i.) Известно, что: (I) из любого города можно попасть в любой (возможно, с пересадками); (2) в любой город прибывает столько же рейсов, сколько вылетает (в i-м столбце таблицы есть_рейс столько же единиц, сколько в i-й строке). Доказать, что можно вылететь из некоторого города и, воспользовавшись ровно по одному разу каждым рейсом, вернуться в этот же город. Составить алгоритм нахождения такого маршрута. (Существует алгоритм, требующий выполнения не более 4 CGn команд для некоторой константы C, не зависящей от n.) ---------257.PAS--------- 1. По итогам работы составлены два списка по оценке трудового участия одних и тех же N сотрудников (1 < N < 6): первый - по решению трудового коллектива, второй - по мнению начальника. Начисленная премия сотруднику определяется по формуле: j-1 Si = i (N+1) + 2 i + 3 i , где i - номер сотрудника, j - его номер в списке начальника. Зная лишь сумму премий всех сотрудников и первый из списков, составить алгоритм, позволяющий установить второй список. ( Н.Н.Красовский ) ---------259.PAS--------- 3. Задано на плоскости множество из h прямоугольников, стороны которых параллельны осям координат, при этом каждый прямоуголь- ник задается координатами левой нижней и правой верхней его вершин. Составить алгоритм определениянаибольшего натурального числа k , для которого существует точка плоск ости, принадлежа- щая одновремено k прямоугольникам. Примечание: эффективным считается алгоритм, число действий 3 в котором пропорционально n . Точка, лежащая на границе прямоу- гольника, принадлежит ему. Упрощенный вариант: прямоугольник заменить отрезками на оси OX. ( А.Шень) ---------260.PAS--------- I.На столе лежит игральный кубик гранью io к нам, гранью jo - вверх. Написать программу, определяющую последовательность "кантований" кубика ("на нас", "от нас","вправо","влево"), после выполнения которых кубик окажется на прежнем месте, но к нам - гранью i , a вверх - гранью j . k k Примечание: Под кантованием понимается перекатывание кубика через соприкасающееся со столом ребро без скольжения. Другие спосо- бы перемещения кубика запрещены. Нумерация граней кубика такова , что если его положить на грань ц цифрой "5", то боковые грани букдут иметь номера "6", "4", "3" при обходе по часовой стрелке, а верхняя - номер "2". ---------262.PAS--------- 1. Круг разрезан несамопересекающейся ломаной, координаты вершин которой заданы парами натуральных чисел (x1,y1), ..., (xk,yk). Первая и последняя вершины лежат на границе круга, а остальные - внутри его. Определить, можно ли разъединить две получившиеся части круга (выход из плоскости не допускается). ---------264.PAS--------- Практический тур. N i N 3. Обозначим S(N,a,b) = WWWWWWWW ,где =x +x +...x , [log k] k 1 2 n k=1 b k=1 a [log k] означает целую часть log k; b b z через log k обозначено такое число z, что b =k. b Требуется составить программу, которая выводит результат с возможно большим числом верных десятичных знаков: максимальной точностью а) S(100, 3, 2) б) S(100, 3, 1.9) в) S(100, 3.1, 1.9) ---------265.PAS--------- 1. Палиндромом называют последовательность некоторых символов, которые читаются одинаково как слева направо, так и срава налево. Педложите алгоритм, позволяющий в заданной строке найти подстроку-палиндром макимальной длины. ---------267.PAS--------- 3. Вершины и стороны N-угольника помечены натуральныи числами от 1 до 2N. Если суммы трех чисел, соответствующих каждой стороне, равны, то N-угольник называется магическим. Требуется: а) для заданного натурального N сформировать хотя бы один магический N-угольник. б) для заданного натурального N сформироать возможно большее число магических N-уольников. ---------268.PAS--------- МАРШРУТ. Скала имеет форму тела вращения. Ее основание лежит на плоскости xOy. Каждо звено образуется частью конической поверхности. Гору завершает плато. Требуется написать программу, которая вычисляет кратчайший путь от точки А при основании скалы до точки В на плато. Программа должна проложить маршрут в ответ на вводимые данные: координаты точек А и В; количество звенев N; радиусы Ri (i=1,...,N) при основании каждого звена; длины Li (i=1,...,N) отрезок - образующий каждого звена. Радиусы Ri строго монотонно убывают с ростом i. Выполнены соотношения: Li  Ri - Ri+1, i=1,...,N; RN+1=0, LN=RN (N-e звено образует плато). Для каждого звена уазывается, куда направлен склон - в гору или под гору - при движении к оси скалы. ---------269.PAS--------- ВЕЛОСИПЕД. Папа Карло собрал Буратино трехколесный велосипед. Не умея делать круглые колеса, он выпилил их из дерева в виде многоугольников. Заметим, что задние колеса велосипеда жестк закреплены на оси. Буратино взял велосипед отправиля к Мальвине по ровной дороге. Для исходного положения колес требуется определить: а) углоую амплитуду (в радианах) качания оси задних колес отоситеьно дороги при езде; б) как следует повернуть на оси одно заднее колес относительно другого, чтобы амплтуда этого качания была минимальной; в) угловую амплитуду качания перекладины, соединяющей переднюю ось с серединой задней при езде на велосиеде, у которого задняя ось с колесами - конструкция, симметричная относительно плоскости, перпендикулярной оси в ее середине. Многоугольники колес задаются координатами своих вершин в произвольном порядке. Также задаются расстояние между задними колесами и длин перекладины, упомянутой в пункте в). ---------273.PAS--------- Задача 1. Восстановление двоичного дерева. Двоичным деревом называется такое, из каждой вершины которого исходит не более двух дуг. Обход двоичного дерева (порядок, в котором перечисляются все его вершины) можно задавать следующими способами: ЛКП - для каждой вершины сначала обходится ее ЛЕВОЕ поддерево, потом КОРЕНЬ (сама эта вершина), потом ПРАВОЕ поддерево; КЛП - сначала КОРЕНЬ, потом ЛЕВОЕ поддерево, потом ПРАВОЕ поддерево (тоже для каждой вершины); ЛПК - сначала ЛЕВОЕ поддерево, потом ПРАВОЕ, потом КОРЕНЬ. Например, для дерева D / \ B E / \ \ A C G / F имеем: ЛКП=ABCDEFG, ЛПК=ACBFGED, КЛП=DBACEGF. Написать программу, которая по представлениям ЛКП и КЛП одного и того же дерева (вводимых как строки из не более чем 100 символов, обозначающих вершины) вычисляет и печатает его представление ЛПК. ---------275.PAS--------- Задача 3. Робот в крепости. Робот находится в крепости, разделенной на клетки. Написать программу для робота, которая гарантирует его выход из крепости, если только это возможно. Считайте, что в Ваш язык программирования добавлены следующие операторы для управления роботом: 1) ИДИ(w) - указывает роботу переместиться на 1 клетку в направлении w (1 - север, 2 - запад, 3 - юг, 4 - восток). 2) СТЕНА(w) - логическая функция, выдающая значение ИСТИНА, если в соседней клетке по направлению w находится препятствие, не позволяющее роботу перейти туда. 3) ЗАКРАСИТЬ (n) - у робота есть краски 5 различных цветов; по этой команде он закрашивает клетку, на которой стоит, цветом n (n=1..5), однако нельзя закрашивать одну и ту же клетку дважды. 4) ЦВЕТ - функция, анализирующая цвет клетки, на которой стоит робот, и выдающая 0, если клетка не закрашена, или ее цвет (1..5). Первоначально вся крепость не закрашена. 5) ?СТОП - команда, проверяющая, достиг ли робот выхода из крепости, и если это так, то останавливающая его работу. 6) УНИЧТОЖИТЬ - команда, вызывающая самоуничтожение робота (что надо сделать, если выйти из крепости невозможно). Примечание. Так как размеры крепости не известны и могут быть очень большими, то объем памяти, используемой программой, не должен зависеть от размеров и формы крепости. ---------276.PAS--------- Задача. Размещение слова. Имеется буквенная матрица размером M*N (значения M и N не превосходят 20), в одной из позиций которой стоит дефис, и слово, длина которого не превосходит 100, с дефисом внутри. Написать программу, которая вводит данную матрицу и слово и затем печатает аналогичную матрицу из целых чисел, в которой число в строке I и столбце J равно числу способов, какими данное слово можно разместить в исходной матрице из букв, начиная с клетки, имеющей те же координаты I и J. Соседние буквы слова должны находиться в клетках, смежных по вертикали, горизонтали или диагонали (по любому из восьми направлений). Например, для матрицы размером 3*5 А С А Н К Г Т Е П Т Р У Б Р - и слова САНКТ-ПЕТЕРБУРГ будет напечатано: 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 что означает, что данное слово может быть размещено в исходной матрице единственным способом, начиная с клетки [1,2]. ---------277.PAS--------- 1. Задана квадратная матрица 10 на 10, элементами которой являются числа А и В (А/=В), причем диагональные элементы матрицы равны А. Определить все пары чисел (i,j) такие, что в j-том столбце стоят все элементы, равные А, а в i-той строке все элементы, кроме диагонального, равны В. ---------278.PAS--------- 2. Задана строка из 80 символов. Составить программу для определения наиболее часто встречающейся подстроки длины не менее двух символов. Если две подстроки разной длины имеют одну частоту повторения, то выдавать строку большей длины. ---------279.PAS--------- 3. В предложенной программе найти все ошибки и соптимизировать программу без изменения алгоритма. Задача: вычислить и напечатать 100 100 А[i,j] , где i=1 j=1 A[j,j] = sin i + cos 0.5 + (x[j] + i/x[j])*y[i] + x[j], если ___________ x[k]=(-b + b**2 - 4cd) / 2d y[k]=2d**2 + 3c*d*b**4/4 - 5/d*b*c b=0.2 + k d=0.4 + 0.1k c=0.3 + 0.2k k=1,2,3,...,100 Текст программы: SUMMA: PROC OPTIONS (MAIN); DCL (B,D,C,S) FLOAT; DCL (I,J) FIXED; DCL (X(100),Y(100),A(100,100)) FLOAT; B:=0.2; D:=0.4; C:=0.3; /* построение вектора Х */ DO I=1 BY 1 TO 100; B=B+1; D=D+0.1; C=C+0.2; X(I)=(-B+SQRT(B**2 - 4*D*C))/(2*D); END; B=0,2; D=D+0.1; C=0.3; /* построение вектора Y */ DO I=1 BY 10 TO 100 B=B+1; D=D+0.1; C=C+0.2; Y(I)=2*D**2 + 3*C*D*B**4/4 + 5/D/B/C; END; DO I=1 BY 1 TO 100; /* построение матрицы А */ DO J=1 BY 1 TO 100; A(I,J)=(SIN(I) + COS(0.5) +(X(J)+I/X(J))*Y(I) + X(J)); END; END; S=0; /* вычисление суммы элементов матрицы А */ DO I=1 TO 100 BY 1; DO J=1 BY 1 TO 100; S=S+A(I,J); END; END; PUT SKIPLIST('СУММА ЭЛЕМЕНТОВ'); PUTSKIP(S) END; ---------280.PAS--------- 4. Для предложенной программы составить возможно более полную систему тестов. Программа определяет местоположение элемента А в массиве V=(V(1), V(2), ..., V(N)), используя метод деления пополам. INTEGER FUNCTION ELEM(V,N,A) DIMENSION V(N) INTEGER N,A,T,J,L,M I=1 J=N 40 IF(I.GE.J) GO TO 10 L=(I+J)/2 IF (V(L).NE.A) GO TO 20 ELEM=L RETURN 20 IF (V(L).GT.A) GO TO 30 J=L-1 GO TO 40 30 I=L+1 GO TO 40 10 ELEM=999 RETURN END ---------281.PAS--------- Задача 1. В городе N имеется 10 улиц и 10 проспектов, образующих 100 перекрестков. На каждом перекрестке расположен почтовый ящик. Робот-почтальон, выезжаюшщий с почтамта (0,0), должен собрать все письма из ящиков и доставить на почтамт за минимальное время. Робот имеет автоопросчик, позволяющий определить наличие писем в ящике на расстоянии не более 2 кварталов. Робот может двигаться только по улицам и проспектам; одна команда перемещает его на один квартал вправо, влево, вверх, вниз. На перекрестке робот может выполнить команду "взять почту" и серию команд "опрос ящика i". а) Составить алгоритм движения робота. б) Запрограммировать этот алгоритм. ---------282.PAS--------- Задача 2. Укажите законы, которым должен подчиняться робот-таксист, работающий в городе (один из законов - выполнение всех правил дорожного движения). ---------283.PAS--------- Задача 3. ЭВМ обслуживает кассу продажи билетов на междугородние автобусы. Со станции отправляется 10 рейсов по 65 мест в каждом автобусе. Известно время отправления каждого рейса. На любом известном Вам языке программирования напишите программу обслуживания пассажиров, запрашивающую время отправления и нужное количество мест. Программа должна напечатать номера мест, номер рейса и время отправления. (Программа может запросить текущее время в момент покупки билетов). Задача 4. Составить набор тестов, позволяющих проверить работу программы для задачи 3. ---------285.PAS--------- 1. N точек на плоскости, не лежащие на одной прямой, заданы своими координатами. Составить алгоритм нахождения трех таких точек из числа заданных, что треугольник с вершинами в этих точках не содержит ни одной точки из оставшихся. ---------287.PAS--------- 3. Расстановка скобок называется правильной, если за каждой открывающей скобкой следует своя закрывающая скобка и каждой закрывающей скобке предшествует своя открывающая скобка. Составить алгоритм определения правильности расстановки скобок. Примеры Правильные расстановки Неправильные расстановки () () ( () ( () () ) )( (((()())())()) (()(()()) ---------288.PAS--------- 1. Послание от внеземной цивилизации представляет собой набор из N символов, каждый из которых является нулем или единицей. Число N является произведением двух простых чисел и ученые предполагают, что эта строка - закодированная прямоугольная "картинка", размеры которой - множители числа N. Составить программу, которая производит перекодировку послания и печатает картинки, заменяя каждый нуль пробелом, а единицу - звездочкой. Тестовый пример: N=55 Послание: 1010001011110100100101111010001010010010010100100010111 ---------289.PAS--------- 2. На плоскости раположены 10 точек, заданных своими координатами. Найти на оси абсцисс точку, наибольшее из расстояний от которой до выбранных точек было бы минимальным. Тестовый пример: а) (186,71) (267,41) (74,209) (266,52) (74,121) (32,-99) (81,99) (208,-159) (119,139) (179,-21) б) (196,61) (228,31) (84,219) (227,42) (84,111) (12,-109) (71,109) (228,-79) (129,149) (189,-11) в) (169,88) (216,58) (57,192) (215,69) (57,138) (66,-82) (98,82) (174,-142) (102,122) (162,-38) ---------290.PAS--------- 3 тур - отбор участников СОЮЗа-88 1. Графом называется набор точек, некоторые из которых соединены отрезками. Граф называется связным, если для любых двух его вершин существует ломаная, составленная из этих отрезков и соединяющая эти точки. Составьте алгоритм для определения связности графа. ---------291.PAS--------- 2. Даны координаты нескольких точек на плоскости. Составьте алгоритм, определяющий вершины многоугольника наименьшей площади, содержащего эти точки. ---------292.PAS--------- Натуральное число, записанное в десятичной системе счисления, называется сверхпростым, если оно остается простым при любой перестановке своих цифр. Определить, является ли данное число сверхпростым. ---------293.PAS--------- Т.9.1. Есть N контактов. Проводами соединены контакты: 1-Й со 2-м, 2-й с 3-м, 3-й с 4-м,...,N-1-й с N-м. ._______._____._____. . . . .________. 1 2 3 4 N-1 N В нескольких проводах случился обрыв. Составить алго- ритм, выясняющий за наименьшее количество проб, в каких проводах случился обрыв. Одна проба проверяет, идет ли ток между i-м и k-м контактами. Алгоритм при пробе может пользоваться вспомогательным литерным алгоритмом - функ- цией ЕСТЬТОК(i,k),принимающей значения "Да" или "Нет". ---------294.PAS--------- Т.9.2. Данa функция, аргументы которой - произвольные натуральные числа f(M-N,N), при М>N f(M,N)= N, при М=N f(N-M,M), при N>M Составить алгоритм, вычисляющий значение функции без по- мощи рекурсии. ---------296.PAS--------- Т.10.1. Написать алгоритм , отгадывающий число N, задуманное чело- веком , задавая ему "да-нет" вопросы. N может быть любым конечным натуральным числом. Алгоритм должен использовать как можно меньше вопросов при больших N. Для диалога с человеком используются вспомогательные алгоритмы ВВОД и ВЫВОД с любым количеством параметров любых типов. ---------297.PAS--------- Т.10.2. Данa функция, аргументы которой - неотрицательные целые числа M и N (M N) 1, при М=0 f(M,N)= f(M-1,N-1)+f(M,N-1), при 0 < М < N 1, при M=N Составить алгоритм, вычисляющий значение функции без по- мощи рекурсии. ---------299.PAS--------- Два человека играют в такую игру: есть электрическая схема, в которую входят батарейка, лампочки и контакты, к которым можно присоединять лю- бое количество проводов. н н н н н контакты V V V V V V V V V V V O O . . . O O лампочки V V V V V ZWЖWQWWWWQW WQWWWW[ 0 1 2 N-1 N Игроки ходят по очереди; при каждом ходе игрок соеди- няет проводом любую пару различных контактов, которая ра- нее не была соединена напрямую каким-либо игроком. Игрок, после хода которого будут гореть все лампочки, считается выигравшим. Написать пограмму, выступающую за одного из игроков и стремящуюся к выигрышу. Сопротивление всех проводов считать равным 0. ---------3.PAS--------- ЧЕТВЕРТАЯ МЕЖДУНАРОДНАЯ ОЛИМПИАДА ПО ИНФОРМАТИКЕ 12-21 июля 1992, Германия 6. Задача первого тура. Острова в море. Расположение островов в море представлено с помощью сетки размером N*N. Каждый остров обозначается символом "*" в узле этой сетки. Задача заключается в том, чтобы восстановить карту морских островов по закодированной информации о распределении островов по горизонталям и вертикалям. Для иллюстрации принципа кодирования рассмотрим следующую карту и соответствующие ей коды: * * * 1 2 * * * * 3 1 * * * 1 1 1 * * * * * 5 * * * * 2 1 1 * 1 1 1 4 2 2 1 1 2 3 2 1 Числа справа от карты на этом рисунке являются кодами и представляют порядок и размер групп островов в соответствующих горизонталях сетки. Например, цифры "1 2" в первой строке означают, что первая горизонталь содержит группу из одного острова, за которой следует группа из двух островов. Слева и справа от каждой группы островов расположено море произвольной протяженности. Аналогично, последовательность "1 1 1" в первом столбце под картой островов означает, что первая вертикаль содержит три группы островов, в каждой из которых один остров, и т.д. Постановка задачи Написать программу, которая выполняет следующие действия (шаги) до тех пор, пока данный входной файл, содержащий несколько блоков информации, не будет прочитан полностью: 1. Считывает очередной блок информации из входного ASCII файла (структура этого файла приведена в примере 1) и отображает его на экране. Каждый блок информации начинается с величины размера квадратной сетки, за которым следует кодовая информация о горизонтальном и вертикальном распределении островов. Код для каждой отдельной горизонтали и вертикали является отдельной строкой файла и представляет собой последовательность чисел, разделенных пробелами. Заканчивается каждая строка нулем. При этом сначала идет информация о всех горизонталях, а затем - о вертикалях. 2. Восстанавливает карту (или все карты в случае не единственного решения как в примере 4) и отображает ее (их) на экране. 3. Добавляет карту (карты) в конец выходного ASCII файла. Каждое пустое место в сетке должно быть представлено двумя пробелами, а каждый остров - символом "* " (звездочка и пробел). В случае неоднозначного решения различные карты должны быть отделены друг от друга пустой строкой. Если карту восстановить невозможно, в соответствующей строке выходного файла написать " no map ". Решения, относящиеся к различным блокам информации входного файла должны быть отделены в выходном файле строкой с надписью " next problem ". Технические ограничения 1. N должно быть не меньше 1 и не больше 8. 2. Результирующая программа должна быть помещена в текстовый ASCII файл с именем "C:\IOI\DAY-1\413-PROG.xxx". Расширение .xxx для PASCAL - .PAS, для C - .C, для BASIC - .BAS, для LOGO - .LOG. 3. Имя входного ASCII файла должно быть "C:\IOI\DAY-1\413-SEAS.IN". Пример 1 6 1 2 0 <-- строка для первой горизонтали 3 1 0 1 1 1 0 5 0 2 1 1 0 1 0 1 1 1 0 <-- строка для первого столбца 1 2 0 4 0 2 3 0 2 0 1 2 0 Пример 2 Блок входной Решение: информации 4 Столбцы 1 2 3 4 0 Строка 1 1 0 Строка 2 * 2 0 Строка 3 * * 0 Строка 4 0 1 0 2 0 0 Пример 3 2 0 0 2 0 2 0 Для этих данных не существует карты. Пример 4 2 1 0 1 0 1 0 1 0 Этим данным удовлетворяют две различные карты. ---------300.PAS--------- Т10.1 Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из n его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) Составить алгоритм, определяющий, побывал ли король дважды на одном и том же поле за минимальное возможное при заданном n количество вычислений. ---------302.PAS--------- Т10.3 Заданы Nъ чисел {1,2,...,Nъ} (N>2). Составить алгоритм, который расположит эти числа в N групп так, что одновременно будут выполняться следующие условия: 1) Каждая группа содержит N чисел 2) Каждое число принадлежит только одной группе 3) Суммы чисел во всех группах одинаковы. ---------304.PAS--------- Т11.2 Задан массив чисел A[1:N, 1:M, 1:L], упорядоченный по убыванию по каждому измерению, т.е.: A[I,J,1] Ж A[I,J,2] Ж ... Ж A[I,J,L] (при всех I,J) A[I,1,K] Ж A[I,2,K] Ж ... Ж A[I,M,K] (при всех I,K) A[1,J,K] Ж A[2,J,K] Ж ... Ж A[N,J,K] (при всех J,K). Найти элемент массива, равный заданному числу и напечатать его индексы (I,J,K). Напечатать слово "нет", если такого элемента не окажется. Решение необходимо найти за CхLх(M+N), а не за CхLх(MхN) операций, где C - константа, не зависящая от N,M и K. ---------305.PAS--------- T11.3 Составить алгоритм, определяющий последовательность выполнения N работ, если для каждой работы задан список работ, результаты которых она должна непосредственно использовать: этот список может быть пустым. Напечатать соответствующее сообщение, если последовательность работ нельзя определить. Наилучший алгоритм определяет порядок за K*(D+N) операций, где D - размер всех списков; K - константа, не зависящая от N и D. ---------306.PAS--------- Составить и реализовать на ЭВМ программу, распознающую шестизначный почтовый индекс за наименьшее количество запросов. При одном запросе программа должна указывать человеку требуемый отрезок сетки и получать ответ, входит ли он в состав изображения цифры. ---------307.PAS--------- Т1. Пусть массив A состоит из N различных элементов. Составить алгоритм, который находит K-й элемент по порядку убывания. ---------308.PAS--------- Т2. Выпуклый многоугольник задается координатами (X1,Y1), (X2,Y2), ..., (XN,YN) его N вершин. Координаты вершин являются элементами соответствующих массивов X и Y. Триангуляцией выпуклого N-угольника называется произвольное его разбиение на N-2 треугольника с помощью N-3 непересекающихся диагоналей. Стоимостью триангуляции называется сумма длин N-3 проведенных диагоналей. Составить алгоритм поиска триангуляции наименьшей стоимости заданного многоугольника. Для упрощения длиною диагонали, соединяющей вершины (XI,YI) и (XJ,YJ), можно считать число VXI-XJV + VYI-YJV. ---------309.PAS--------- П1. Русский текст зашифрован с помощью некоторого ключевого слова таким образом: 1) Буквы ключевого слова пишутся много раз над буквами исходного текста; 2) К алфавитному порядковому номеру каждой буквы текста прибавляется алфавитный порядковый номер соответствующей буквы ключевого слова; 3) Если результат превышает 32, из него вычитается 32; 4) Полученное число задает порядковый алфавитный номер буквы в зашифрованном тексте. Например, исходные данные: КЛЮЧК ЛЮЧ КЛЮЧКЛЮЧКЛ "ФРАЗА ДЛЯ ШИФРОВАНИЯ" (КЛЮЧ - ключевое слово) дадут следующий результат: "ЯЬЯЯЛ РКЧ ГФУИЩОЯЕУЛ". Буквы е и е совпадают, все буквы строчные, латинские заменены русскими с тем же написанием, знаки препинания не преобразуются, длина ключевого слова равна 4. Зашифрованный текст содержит условие второй задачи. 1. Расшифровать текст, если ключевое слово неизвестно. При расшифровке рекомендуется использовать компьютер. Решение должно содержать метод расшифровки с описанием использования ЭВМ, ключевое слово и расшифрованный текст. 2. По желанию участник может попросить ключевое слово и расшифровать текст. При это максимальное количество баллов за практический тур уменьшается таким образом: если ключевое слово было получено в течение 1-го часа, участник получает до 10% баллов, в течение 2-го часа - 20%, в течение 3-го - 30%, 4-го - 40%. 3. Используя компьютер, решить вторую задачу. Задача П2 была предложена в 4-х вариантах: П2. Вариант 4: ШХСЯВъЛ УРКЧЙЖД М, ТЮНССЦЙЕБП У ГЙБОЧ, Й Т, ъъЕХЩТБЙЙЛ Н ЗСЭЖЫ. ЦМРШъМУМ ШЬПУЩМНЬЬ, ЦПВЧЬБП ЛОПФСЮ ОРАМММЦЗЖ ЧЦМШХЦФА ВЙНМШЯ М Й Т С УБЯСЭЬТЙСУ Т ЫМВЫСВФ Б ЛЭЖ ВЙЦЙХ АФТЫЙ, ЦПВЧЬЬХ ъъЕХЩТБВъЛ Г Р С ЩЖ БЧРЖАПМУБИ О Г. ЭСЦБъСС ИЭЙГЖЭСЛ ЮЫОШЖЭЫъГ Б ЦС ЕЮФТОЛ ъъГЯЙРБВЕ РСГМ Э ЕАЬППЬ. ---------310.PAS--------- 1. Фирма осуществляет производство коробок, используя в качестве сырья квадратные стальные листы со стороной а .Для изготовления коробки из листа по его углам вырезают одинаковые квадраты , из полученной крес- товидной заготовки сгибанием и свариванием получают готовое изделие. Ос- тавшиеся квадратные куски металла можно затем либо продать, либо исполь- зовать на новом этапе для изготовления коробок по-меньше и т.д.. Доход от продажи квадратного листа металла равен q*s , где s - площадь листа; доход от продажи одной коробки равен p*v-l*x-m*y, где v,x,y - соответственно об'ем, сторона основания и высота коробки; q,p,l,m - заданные неотрицательные коэффициенты. Как фирме следует распорядиться исходным листом, чтобы суммарный доход от продажи коробок и металл был наибольшим? Каков будет доход? 1) а = 40 , p = 1000 , q = 1, m = l = 0.1; 1) а = 100, p = q = 10 , m = l = 0.1; 1) а = 40 , p = 1 , q = 10, m = l = 0.1; 1) а = 100, p = q = m = l = 0 coryright : Н.Н.Красовский , 1989 ---------311.PAS--------- 2. В одной из книг по фотографии приведен рецепт удивительного проявителя Р-6726, повышающего светочуствительность пленки в 200 раз. К сожалению , авторы , подробно описав свойства Р-6726 , не опубликовали его приготовления, указав лишь, что проявитель - водный раствор перечис- ленных фотореактивов, и дали расход каждого из реактивов на литр прояви- теля. Попытка растворения компонент Р-6726 в воде в выбранной наугад последовательности показала, что все не так просто: в жидкости образовал- ся бурый осадок и началось обильное газоотделение. Поиски в спецлитературе привели к некоторому успеху. В одном из химических справочников в разделе "водные растворы" для некоторых из ком- понент Р-6726 давался список веществ, которые должны непременно быть в растворе при растворении данной компоненты ( эти вещества оказались реак- тивами из рецепта Р-6726). Кроме того, для некоторых компонент приводился перечень веществ (ряд из них были компонентами Р-6726 ), присутствие ко- торых в растворе при растворении данной компоненты недопустимо. Вероятно, нарушение каких-то из этих условий (отсутствующее при фирменном способе изготовления Р-6726 ) и привело к неудаче эксперимента. Заметим, что для каждого процеса растворения приводился рекомендуемый диапазон температур раствора, однако все эти диапазоны включали температуру 60 градусов Цель- сия, при которой проводился эксперимент. а) Разработайте математическую модель задачи определения способа приготовления Р-6726, удовлетворяющего приведенным в найденной литературе требованиям. б) Разработайте алгоритм опрределения допускаемой справочником последовательности растворения реактивов для приготовления Р-6726. в) Что означает ответ алгоритма пункта в) о невозможности выпол- нения всех требований справочника, ведь авторы как-то изготовляют Р-6726 ? coryright В.В.Прохоров, 1989. ---------313.PAS--------- 1. Некоторый измерительный прибор имеет для вывода показаний подключенный к встроенному микропроцессору цифровой индикатор. Этот индикатор, аналогичный используемым в микрокалькуляторах, позволяет выдавать в каждом из N разрядов стилизованные изображения десятичных цифр, символ десятичного порядка "Е", символ "-", десятичную точку или вообще ничего не высвечивать. Специфика прибора такова, что диапазон значений подлежащих индикации величин весьма широк - несколько порядков. Понятно, что ввиду ограниченности числа разрядов индикатора ими хочется распорядиться так, чтобы для любого значения измеренной величины точность представления ее на индикаторе была бы наилучшей (для каких-то значений число можно выдавать в форме без десятичного порядка, для каких-то - в экспоненциальной форме, жертвуя цифрами мантиссы ради изображения порядка числа, иногда, быть может, и как целое.) То есть, можно говорить о некоем оптимальном для данного индикатора формате представления данного числа. Итак,требуется разработать алгоритм определения для произвольного заданного N и для произвольного значения, подлежащего индикации, таких цифр и знаков для каждого разряда индикатора (т.е. формата вывода), которые давали бы наилучшую точность считывания результата. Отладку алгоритма необходимо провести на ЭВМ, написав программу на произвольном доступном Вам языке и "прогнав" примеры для всех характерных на Ваш взгляд ситуаций. ---------316.PAS--------- 2. Введение. Язык аборигенов острова Виртландия содержит около 1000 слов. Для записи текстов виртландцы используют заглавные буквы латинского алфавита. Текст состоит из предложений, каждое из которых заканчивается точкой. Внутри предложения могут встречаться запятые. Слова разделяются по крайней мере одним пробелом. Точка и запятая ставятся непосредственно за словом и отделяются от следующего слова хотя бы одним пробелом. Самое длинное виртландское слово - ABRAKADABRA - состоит из 11 букв. Дано. 1. Текстовый файл GLOSSARY содержит упорядоченный по алфавиту словарь. Каждое слово записано в отдельной строке без пробелов. 2. Текстовый файл TEXT содержит пример текста на языке виртландцев. Длина строк не превышает 60 символов. В тексте имеются орфографические и синтаксические ошибки. Задача. Написать программу, которая проверяла бы текст и по возможности исправляла бы его. Требования к программе: программа должна считывать исходный текст из файла TEXT, а результирующий записывать в файл TEXT.1. Если ошибку в тексте удается исправить, то в TEXT.1 записывается исправленный текст. Если ошибку не удается исправить, то часть текста, сродержащая ошибку, выделяется слева и справа знаком * (звездочка). Пример. Пусть в исходном тексте имеется строка: ABBA RANDO ASCII ,USSR но в словаре нет слова RANDO, тогда соответствующая строка в результирующем тексте может выглядеть так: ABBA *RANDO* ASCII, USSR . Проверка производится тестированием программы (исполнением на ЭВМ). Будут учитываться количество ошибок, которое программа обнаружит или исправит в предложенном тестовом тексте. Отдельно будут отмечены лучшие программы по длине кода и скорости работы. ---------319.PAS--------- Строка-образец M содержит символы из множества ABC U {?, *}, где ABC={A, B, C}. Строка S, содержащая символы из множес- тва ABC называется соответствующей образцу M, если она может быть получена из M такими подстановками: 1. На место вопросительного знака подставляется любой символ из ABC; 2. На место звездочки подставляется любая последователь- ность символов из ABC (возможно, пустая). Задания: 1. Задано число N. Написать программу, строящую все су- щественно различные (неравные) строки из N символов, соответс- твующие образцу M. 2. Написать программу, определяющую для заданной строки S ее подстроку минимальной длины, соответствующую образцу M. 3. Заданы строки S и T. Написать программу, определяющую образец M с минимальным количеством символов, которому соот- ветствует S и не соответствует T. ---------359.PAS--------- 1. (Представлена Китаем) Дана последовательность из 2N ячеек. Две соседние из них - пустые, а остальные содержат N-1 символов A и N-1 символов B. Пример для N = 5: A B B A A B A B Правила перемещения: Содержимое любых двух соседних непустых ячеек можно, сохраняя их порядок, пересылать в пустые ячейки. Цель: Используя правило пе- ремещения, достичь конфигурации, в которой все символы A располо- жены левее всех символов B. Местоположение пустых ячеек после пе- ремещений не имеет значения. Задание: Написать программу, которая: 1. Вводит с клавиатуры начальную конфигурацию в виде последова- тельности символов A, B и нулей для пустых ячеек, а также модели- рует перемещения. 2. Для заданной начальной конфигурации определяет по крайней ме- ре один план перемещений, с помощью которого можно достичь цели, или сообщает, что такого плана не существует. Вывод должен содер- жать начальную конфигурацию, промежуточные конфигурации после каждого шага, а также заключительную конфигурацию. 3. Находит план достижения цели за минимальное число шагов. Результаты: Представить по крайней мере хотя бы одно решение для примера, приведенного выше. ---------360.PAS--------- Задана таблица размером 4x4, в каждой клетке которой, кроме двух, содержится одно из чисел от 1 до 14 (все числа разные). Оставшие- ся две клетки - пустые. (Пример - таблица 1.) Таблица 1 Таблица 2 7 3 5 14 1 2 3 4 4 9 13 5 6 7 8 1 2 10 9 10 11 12 11 8 12 6 13 14 Правила перемещения. Число из любой клетки может быть перемеще- но по горизонтали или по вертикали в любую незанятую соседнюю клетку. Клетка, в которой ранее размещалось число, становится пустой. Цель. Необходимо с помощью указанного правила выполнить по шагам преобразование произвольной исходной таблицы в конечную таблицу 2. Задание. Написать программу, которая: 1) осуществляет ввод с клавиатуры исходной таблицы и вывод ее на экран (пустые клетки могут быть закодированы нулями); 2) выполняет преобразование введенной таблицы в таблицу 2; 3) на каждом шаге выводит на экран слева вариант таблицы до это- го хода, справа - вариант таблицы после хода и указывает номер хода (1,2,3 и т. д.) так, что в конце работы программы будет по- казано полное число сделанных ходов; 4) минимизирует число ходов, необходимых для решения задачи. ---------361.PAS--------- 3. Задача второго тура. В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием сторожа называется мно- жество пар [T1(i), T2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0; EndTime]. Для заданного расписания стражи требуется: а) проверить, в любой ли момент времени в галерее находится не менее двух сторожей. Если условие а) не выполняется, то: б) перечислить все интервалы времени с недостаточной охраной (ме- нее двух сторожей); в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписа- ние (удовлетворяющее условию а)); г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать время дежурства каждого сторожа с сох- ранением времени его дежурства; д) при положительном ответе на пункт г) составить расписание с наименьшим числом сдвигов. Входные данные (все моменты времени задаются в целых минутах): EndTime - момент окончания стражи (мо- мент начала - 0); N - число сторожей; T1(i), T2(i), i = 1,...,N - моменты начала и окончания дежурства i-го сторожа. Length - дли- тельность дежурства каждого дополнительного сторожа. Выходные данные: 1) ответ на пункт а) в форме да/нет; 2) при ответе "нет" на пункт а) - список пар (k,l) - начал и кон- цов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1); 3) число дополнительных сторожей и моменты начала и окончания де- журства каждого дополнительного сторожа; 4) ответ на пункт г) в форме да/нет; если "да", то номера сторо- жей, смена которых сдвигается, и значения сдвигов; 5) ответ на пункт д) - наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов. Примечание. Программа должна допускать независимое тестирование пунктов в), г), д). ---------362.PAS--------- 19-24 мая 1991, Греция 4. Задача первого тура (автор Мария Кадзураки, Греция). Пронумеровать позиции в матрице (таблице) размером 5x5 следующим образом. Если номер i (1<=i<25) соответствует в матрице позиции с координатами (x,y), то номер i+1 может соответствовать позиции с координатами (z,w), вычисляемыми по одному из следующих правил: 1) (z,w) = (x+-3,y); 2) (z,w) = (x,y+-3); Внимание: плюс/минус 3) (z,w) = (x+-2,y+-2). Требуется: A. Написать программу, которая последовательно нумерует позиции матрицы 5x5 при заданных координатах позиции, в которой простав- лен номер 1 (результаты должны быть выведены в виде заполненной матрицы); Б. Вычислить число всех возможных расстановок номеров для всех начальных позиций, расположенных в правом верхнем треугольнике матрицы, включая ее главную диагональ. Пример. Если в качестве начальной позиции в матрице выбрана позиция с координатами (2,2), то на данном шаге координаты позиции с номером 2 в соответствии с представленными правилами могут быть (2,5), (5,2) или (4,4). ---------363.PAS--------- 5. Задача второго тура (автор С.Захос, Греция). S-терм - это последовательность символов S и скобок, определяе- мая рекурсивно следующим образом: символ S есть S-терм; если M и N - S-термы, то выражение (MN) есть также S-терм. Пример S-терма: ((((SS)(SS))S)(SS)). Правые скобки не несут информации и могут опускаться. В этом случае вышеприведенный S-терм выглядит так: ((((SS)(SS))S)(SS. 1. Напишите процедуру "gensterm" для порождения S-термов. Она должна для заданного n заполнять n текстовых файлов (n = длина = число символов 'S'), каждый из которых содержит все S-термы дли- ны n = 1,2,...,n соответственно. Внутри файла S-термы разделяют- ся символом ';'. В конце каждого файла должен стоять символ '.' (точка). Напишите программу, которая по заданному целому n (n <= 10) выполняет описанную выше процедуру и выдает на дисплей все сгенерированные S-термы. Рассмотрим вычисление S-термов. Един- ственное алгебраическое правило (S-правило), которое может быть использовано, состоит в следующем: любой подтерм S-терма, имею- щий вид (((SA)B)C), где A, B, C - также S-термы, может быть пере- писан как ((AC)(BC)), то есть Context1(((SA)B)C)Context2 -> Context1((AC)(BC))Context2. Применение этого правила к S-терму называется редукцией S-терма. Возможны разные способы (стратегии) выбора подтермов для применения S-правила. Последовательное при- менение S-правила к S-терму до тех пор, пока это возможно, назы- вается редукцией S-терма. Возможны разные способы (стратегии) вы- бора подтермов для применения S-правила. Последовательное приме- нение S-правила к S-терму до тех пор, пока это возможно, назы- вается Пример цепочки редукции S-терма: Пример цепочки редукции S-терма: ((((SS)(SS))S)(SS)) -> (((SS)((SS)((SS)S))(SS)) -> -> ((S(SS))(((SS)S)(SS))) -> ((S(SS))((S(SS))(S(SS)))). 2. Предложите эффективную структуру данных для представления S-термов, облегчающую применение S-правила. Напишите две процеду- ры: "readterm" и "printterm". Первая из них преобразует S-термы в Вашу структуру данных из формы, порождаемой процедурой "gens term "; вторая преобразует S-термы из Вашей структуры в форму, порож- даемую процедурой "gensterm". Ваша программа должна демонстриро- вать эти преобразования. 3. Напишите процедуру "reduce", выполняющую один шаг редукции в соответствии с S-правилом над заданным подтермом S-терма в Вашем представлении. Программа должна демонстрировать это. 4. Напишите процедуру "normalize", которая в заданном S-терме должна последовательно выбирать подтермы и применять S-правило до тех пор, пока дальнейшии редукции станут невозможными, либо чис- ло шагов не достигнет некоторого максимума, например 30. Ваша программа должна демонстрировать это. 5. Объедините все процедуры в одну программу, которая: а) запрашивает у пользователя длину n; б) порождает с помощью процедуры "gensterm" S-термы заданной дли- ны; в) преобразует все S-термы в Ваше представление; г) нормализует их (если это возможно); д) выводит в качестве результата нормализованные S-термы; е) выводит последовательно число шагов редукции, совершенных над каждым S-термом, либо сообщение "not normalized", если нормализа- ция требует более 30 шагов. ж) Выводит число ненормализованных термов и общее число всех S-термов заданной длины n. ---------365.PAS--------- 7. Задача второго тура. Покорение вершины. Клуб альпинистов состоит из P членов, с номе- рами от 1 до P. Каждый альпинист поднимается в гору с одной и той же скоростью, а скорость подъема не отличается от скорости спус- ка. Альпинист с номером i расходует C(i) единиц ресурсов в день как при подъеме, так и при спуске, и может нести в каждый момент времени не больше S(i) таких единиц. Все C(i) и S(i) - целые чис- ла. Предполагается, что альпинист может достичь вершины за N дней при полной обеспеченности ресурсами как для подъема, так и для спуска. Гора может быть так высока, что один альпинист не может изначально нести все необходимые для подъема и спуска ресурсы. Поэтому группа альпинистов стартует в одном и том же месте и в одно и то же время, чтобы обеспечить восхождение. Альпинист мо- жет начать спускаться, не достигнув вершины, отдав при этом все ненужные ему для спуска ресурсы другим альпинистам, которые дол- жны быть в состоянии их взять. Альпинисты не отдыхают в течение экспедиции. Задача состоит в составлении расписания восхождения для клуба альпинистов. По крайней мере один альпинист должен дос- тичь вершины горы и все альпинисты, включенные в группу восхожде- ния, должны возвратиться в начальную точку. Постановка задачи На- писать программу, которая выполняет следующее: 1. Вводит с клавиатуры число дней N, требуемое для достижения вершины горы, число P членов клуба и числа S(i), C(i), для всех i от 1 до P. Предполагается, что все входные данные целочисленные. Отвергнуть (повторить запрос) на ввод данных, которые не имеют смысла. 2. Определяет расписание для восхождения, а также номера альпи- нистов a(1), a(2),..., a(k), образующих группу для восхождения, и числа M(j) (для всех j от 1 до k), которые обозначают количество единиц ресурсов, взятых каждым a(j) альпинистом на старте. Соо- бщает, если нельзя составить такого расписания для заданных N, S(i) и C(i). 3. Выводит следующую информацию на экран: а) число k альпинистов, действительно участвующих в восхождении (размер группы восхождения); б) необходимое для этого общее количество единиц ресурсов; в) номера участвующих в восхождении альпинистов a(1),a(2),..., a(k); г) для каждого а(j) (1<=j<=k) какое количество единиц ресурсов он возьмет с собой со старта; д) для каждого a(j) количество дней, через которое он начнет спускаться. 4. Расписание является оптимальным, если: а) число участвующих в восхождении альпинистов, необходимое для достижения вершины одним из них, минимально. б) среди всех расписаний для групп, удовлетворяющих условию а), общее количество единиц ресурсов, взятых с собой со старта, - ми- нимально. Пытается найти почти оптимальное расписание. Технические огра- ничения 1. Поместите вашу результирующую программу в текстовый ASCII файл с именем "C:\IOI\DAY-2\422-PROG.xxx". Расширение.xxx для PASCAL -.PAS, для C -.C, для BASIC -.BAS, для LOGO -.LOG. 2. Программа должна отвергать входные данные, если N<1 или N>100, а также если P<1 или P>20. Пример: Возможен следующий диалог с вашей программой. Число дней, необходимое для достижения вершины - 4 Число альпинистов в клубе - 5 Максимальный ресурс для альпиниста 1 - 7 Ежедневный расход ресурса для альпиниста 1 - 1 Максимальный ресурс для альпиниста 2 - 8 Ежедневный расход ресурса для альпиниста 2 - 2 Максимальный ресурс для альпиниста 3 - 12 Ежедневный расход ресурса для альпиниста 3 - 2 Максимальный ресурс для альпиниста 4 - 15 Ежедневный расход ресурса для альпиниста 4 - 3 Максимальный ресурс для альпиниста 5 - 7 Ежедневный расход ресурса для альпиниста 5 - 1 2 альпиниста требуется для покорения вершины. 10 единиц ресурса в целом для этого необходимо. Взбираться будут альпинисты 1,5. Альпинист 1 возьмет 7 единиц ресурса и начнет спускаться через 4 дня. Альпинист 5 возьмет 3 единиц ресурса и начнет спускаться через 1 день. Хотите спланировать восхождение для другого альпинистского клуба? (Y/N) - Y. Число дней, необходимое для достижения вершины - 2 Число альпинистов в клубе - 1 Максимальный ресурс для альпиниста 1 - 3 Ежедневный расход ресурса для альпиниста 1 - 1 Восхождение невозможно. Хотите спланировать восхождение для другого альпинистского клуба? (Y/N) - N. До свидания. ---------370.PAS--------- 11. Задача 4 теоретического тура. 3 000 000 человек с различными фамилиями выстроились в затылок друг другу. Каждый, кроме первого, написал на листке бумаги фами- лию стоящего перед ним и свою фамилию. Все 2999999 листков бума- ги перемешали и информацию (упорядоченные пары фамилий) записали на магнитную ленту. Как возможно быстрее узнать фамилию 1234567-го человека? В вашем распоряжении ЭВМ с небольшой опера- тивной памятью (64 Кбайт) и ограниченным количеством магнитофо- нов (<= ---------371.PAS--------- 12. Задача 1 машинного тура. Последовательность натуральных чисел a0,a1,a2,... строится так: если an четно, то an+1 = an/2; если an нечетно, то an+1=3an+1. Найти минимальное n, для которого an = 1, если а) a0 = 27; б) a0 = 2000007. ---------381.PAS--------- 22. Задача первого тура (авторы А.И.Грудев, Ф.Л.Черноусько). На координатной плоскости задан робот-манипулятор, состоящий из двух последовательно соединенных звеньев длиной L1 и L2. Первое звено шарнира закреплено в начале координат, второе шарнирно соединено с первым. Робот управляется путем поворота звеньев в первом и втором шарнирах с угловыми скоростями, по абсолютной величине не превышающими W1 и W2 соответственно. Робот предназначен для обра- ботки деталей, расположенных в точках (X1,Y1), (X2,Y2),..., (XN,YN). В начальный момент первое звено направлено вдоль положи- тельной полуоси OX, а второе звено образует угол Q, отсчитывае- мый от оси OX против часовой стрелки. Врем я обработки деталей фиксировано и равно Р. Требуется составить программу, которая: а) выдает какую-либо последовательность обработки деталей и тре- буемое для этого время; б) выдает последовательность обработки деталей за минимальное по возможности время; в) для заданного интервала времени (0,T) выбирает максимальное количество обработанных деталей. Примечания. 1. Все исходные данные целочисленные. 2. Программа должна осуществлять ввод данных либо из входного файла (A:\ROBOT.DAT), либо с клавиатуры в виде последовательнос- ти: L1, L2, W1, W2, Q, T, P, N, X1, Y1,..., XN, YN. ---------382.PAS--------- 23. Задача второго тура (автор И.А.Волков). Задается множество различных слов A = (a1,a2,...,ak), k <= 10. Из слов множества A составляется зашифрованный текст - последова- тельность слов, записанных без разделителей-пробелов. Слова пред- ставляют собой непустые последовательности не более восьми заг- лавных латинских букв и могут встречаться в тексте произвольное количество раз. Необходимо дешифровать текст, то есть разбить его на слова множества A. В дешифрованном тексте слова следует раз Написать программу, которая: а) определяет, существует ли для заданного множества A такой текст, который дешифруется не единственным образом; б) если такой текст существует, то исключает из множества A мини- мальный набор слов так, чтобы любой текст дешифровывался одноз- начно, и печатает исключаемые слова (если такой исключаемый на- бор не единственный, то выводит все варианты); в) для введенного текста производит его дешифровку, используя первоначально введенное множество A, и если дешифровка не един- ственная, то выводит все варианты. Последовательность операций ввода/вывода: ввод множества A: "введите k" "введите a1" . . . . . . . . . . "введите ak" вывод сообщения: "неодноз- начно дешифруемый текст существует" или "не существует" если текст существует, то вывод сообщения: "выбросить <список слов> ввод текста длиной не более сорока символов в виде: "текст" <текст> вывод результатов дешифровки: <текст> --> <дешифрованный текст>. Примеры: 1) A = (B, C) - любой текст дешифруется однозначно. 2) A = (A, B, BC) - существует текст, который дешифруется двумя способами: BBC --> B BC или BBC --> B B C. ---------383.PAS--------- 24. Задача первого тура (автор Ю.В.Корженевич) В прямоугольной (0,1)-матрице, размером NxM (N - число строк, M - число столбцов; N = 1,2,...,15; M = 1,2,...,15) подсчитать число изолированных 0-областей, т.е. областей, состоящих из одних нулей, имеющих со- седние нули по горизонтали, вертикали или диагонали. 0-область может состоять только из одного нулевого элемента. Например, для (0,1)-матрицы вида: 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 число изолированных 0-областей равно 3. ---------384.PAS--------- 25. Задача второго тура (автор Ю.В.Корженевич). На острове Новой Демократии каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что к всеобщему удивле- нию даже в самой малочисленной партии оказалось не менее двух че- ловек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предпологалось по Конституции ос- трова, президенты всех партий. Посовещавшись, Островитяне решили, что будет достаточно, если в парламенте будет хотя бы один пред- ставитель от каждой партии. Помогите островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий. Исходные данные: каждая партия и, соответственно, ее президент имеют одинаковый порядковый номер от 1 до N (4<=N<=150). Вам даны списки всех N партий острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров его членов. Например , для четырех партий: Президенты Члены партий 1 - 2, 3,4 2 - 3 3 - 1, 4, 2 4 - 2 Список членов парламента: 2 (состоит из одного члена). Примеча- ние. Получить список одного, как можно более малочисленного на Ваш взгляд парламента. ---------391.PAS--------- 32. Задача 1 теоретического тура. На двумерной плоскости задано N точек с координатами (X1,Y1), (X2,Y2),..., (XN,YN). Построить алгоритм, позволяющий из этих то- чек выделить вершины квадрата, содержащего максимальное число за- данных точек. Примечание: предполагается, что точки, расположен- ные на сторонах квадрата, принадлежат ему. ---------392.PAS--------- 33. Задача 2 теоретического тура. На входное устройство компьютера в произвольном порядке посту- пают цифры 1, 2 или 3, образуя последовательность. Признаком окончания последовательности служит число 0. Построить алгоритм, определяющий наличие во введенной последовательности трех рядов одинаковых цифр, состоящих только из единиц, только из двоек и только из троек, и имеющих длину, равную заданной. Примечание: Последовательность может быть настолько длинной, что она целиком не помещается в памяти компьютера. ---------393.PAS--------- 34. Задача 3 теоретического тура. В городе имеется n автобусных остановок, обозначенных числами 1,2,3,...,n. Проложено r автобусных маршрутов, заданных последо- вательностями соседних остановок при движении автобуса в одном направлении: M1 = (i11, i11, ... , i1m1), M2 = (i21, i22, ... , i2m2), ........................., Mr = (ir1, ir2, ... , irmr), где ijk из множества чисел от 1 до n. Построить алгоритм, который по заданным номерам остановок i и j определяет наиболее быстрый путь перемещения пассажира от оста- новки i до остановки j с использованием имеющихся маршрутов авто- бусов и при условии, что время движения между соседними останов- ка ми у всех маршрутов одинаково и в 3 раза меньше времени однок- ратного изменения маршрута. Кроме того, автобусы движутся в обоих направлениях. ---------394.PAS--------- 35. Задача 4 теоретического тура. На квадратном поле размером 3x3 с помощью датчика случайных чи- сел расставлены 8 фишек с номерами от 1 до 8 (рис.35-1). Пос- троить алгоритм расстановки фишек по возрастанию их номеров так, как показано на рис.35-2. Передвигать фишки можно только на сосе- днюю свободную позицию. 1 7 3 1 2 3 6 5 2 4 5 6 8 4 7 8 Рис.35-1 Рис.35-2 ---------395.PAS--------- 36. Задача 1 практического тура. Задано 121 натуральное число - 1,2,3,...,121. Составить програм- му, которая расположит эти числа в 11 групп так, что одновремен- но будут выполняться следующие условия: 1) каждая группа содержит точно 11 чисел; 2) каждое число принадлежит только одной группе; 3) сумма чисел в каждой отдельной группе одинакова для всех групп. ---------396.PAS--------- 37. Задача 2 практического тура. Составить программу, которая в полной записи числа 77! (77 факто- риал) укажет в порядке убывания номера разрядов, содержащих циф- ру 7. Примечание: разряды числа нумеруются в следующем порядке: разряд единиц имеет номер 1, десятков - 2, сотен - 3 и т. д. ---------397.PAS--------- Черный ящик. На вход черного ящика подается любая таблица, содер- жащая символы латинского алфавита. На выходе получается 3 строки результата. Например: а) S T E P "E" R E A D ------> (1;3), (3;3) O P E N 2 P L A Y б) A G A T отсутствуют N E X T ------> отсутствуют S U R A 0 C R A Y в) R E D U C E P R O L O G "G" S I M U L A ------> (2;6) M O D U L A 1 T U R B O C R A P I R A Опишите алгоритм, по которому мог бы работать этот "черный ящик". ---------405.PAS--------- 44. Задача первого тура (автор В.В.Прохоров). Ломка. Пусть W - множество всех замкнутых односвязных ломаных на координатной плоскости XOY, удовлетворяющих условиям: а) ломаная ломается только под прямым углом; б) звено ломаной параллельно одной из осей координат; в) отсутствуют самопересечения или самокасания ломаной; г) (x1,y1),..., (xn,yn) - целочисленные координаты всех точек, где ломаная претерпевает излом (порядок нумерации произволен и неизвестен), N - количество изломов. Трубуется: А: написать по-возможности оптимальные (по времени исполнения) программы (с обоснованием алгоритмов), которые по задаваемым N и (x1,y1),...,(xn,yn) выдавали бы и отображали на экране монитора: 1) какую-либо ломаную из множества W; 2) ломаную из множества W, имеющую наибольшую длину, и значение этой длины; 3) ломаную из множества W, ограничивающую наибольшую площадь, и значение этой площади; 4) количество ломаных в множестве W. Б: решить задачу А, исклю- чив пункт (б) из определения W. Примечание: Односвязной называет- ся ломаная, из любой точки которой можно попасть в любую другую ее точку, двигаясь по этой ломаной. ---------406.PAS--------- 45. Задача второго тура (авторы Е.В.Андреева, А.П.Марченко). Компостер. В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал на него несколько раз. Контролеру требуется определить могло ли быть получено за данное расположение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые отверстия не выходят за пределы билета. В билете было пробито N (N < 10) отверстий. Требуется: А. Для компостера с двумя штырями (S=2) составить программу, ко- торая: 1. Определяет можно ли получить заданным компостером требуемое расположение отверстий в билете. Если это возможно, то изобра- жает вид билета после каждого нажатия компостера. В противном случае, выводит соответствующее сообщение. 2. Определяет количество K различных компостеров, каждым из кото- рых можно пробить заданную конфигурацию. 3. При K=0 (см.п.2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий. 4. Находит минимальное число нажатий, требуемое для пробивки за- данной конфигурации отверстий, для каждого компостера из пункта 2. Б: Решить задачу А для компостеров с числом штырей S (S>2). Примечания. Все исходные данные - натуральные числа. Компостеры, дающие при однократном нажатии совпадающие конфигурации отвер- стий, считаются одинаковыми. Относительное расположение отвер- стий в билете и штырей в компостере вводятся либо с клавиатуры, либо из файла с именем COMP.DAT. Cтруктура вводимой информации: {N, x1, y1... , xn, yn, S, u1, v1,..., us, vs, где xi, yi - коор- динаты отверстий в билете, ui, vi - координаты штырей в компосте- ре. Нажатие компостера (см.п.1) моделировать клавишей "Пробел". При выводе конфигурации на экран (см. п.п.1,3) изображать коорди- натную сетку. При этом программа должна осуществлять подходящее масштабирование. ---------407.PAS--------- (Д.Я.Шараев) Число п (=3.1415926535...) можно определить как пре- дел отношения периметра правильного многоугольника, описанного вокруг произвольной окружности, к ee диаметру при стремящемся к бесконечности количестве сторон многоугольника. Напишите основанную на этом свойстве программу для прибли- женного определения числа п для конкретного ВNА. Попробуйте по- лучить число п с как можно более высокой точностью, делая вычис- ления с все большим N. Объясните возникающую при этом неприят- ность. УКАЗАНИЕ. Воспользуйтесь формулой для вычисления длины сто- роны 2N-угольника через длину стороны N-угольника, описанных вок- руг окружности. ---------410.PAS--------- 1. (А.П.Суетов.) На квадратном участке местности размером 1км  1км решено построить завод. Участок (мысленно) разбили на квадраты со сторонами 100 метров, параллельными сторонам участка. Для каждого квадрата определили, нужен он для завода или нет (см. пример на рисун- ке). 1 2 3 4 5 6 7 8 9 10 1 АИЖИЖИЖИЖИЖИЖИЖИЖИЖИБ АИБ И нужный для завода квадрат 2 ДИКИКИКИКИКИКИКИКИКИЕ ВИГ 3 ДИКИКИКИКИКИКИКИКИКИЕ 4 ДИКИКИКИКИКИКИКИКИКИЕ АИБ И не обязательный для завода 5 ДИКИКИКИКИКИКИКИКИКИЕ ВИГ квадрат 6 ДИКИКИКИКИКИКИКИКИКИЕ 7 ДИКИКИКИКИКИКИКИКИКИЕ 8 ДИКИКИКИКИКИКИКИКИКИЕ 9 ДИКИКИКИКИКИКИКИКИКИЕ 10ДИКИКИКИКИКИКИКИКИКИЕ ВИЗИЗИЗИЗИЗИЗИЗИЗИЗИГ Завод требуется огородить забором. Плата за 1м забора равна 1 бу- казоид, а 1ма2А земли, попавшей за забор, стоит тоже 1 буказоид. Напиши- те программу, которая по нужным для завода квадратам определяет линию, вдоль которой надо построить забор, учитывая, что желательно, чтобы общая плата за забор и за землю была наименьшей. Линия является ломаной с вершинами в точках пересечения верти- кальных и горизонтальных линий. Требования к вводу И выводу. Считается, что каждый квадрат, нужный заводу, задается парой чи- сел: номерами по горизонтали и по вертикали. Программа должна запрашивать пары целых чисел. Признаком конца ввода является пара (-1, -1). Время счета программы И не более 1 мин, после чего программа либо останавливается сама, либо может быть остановлена нажатием на кнопку N. Результат выдается на печать в виде: последовательность целых пар координат вершин ломаной. Если ломаная состоит из нескольких ком- понент, то соответствующие последовательности должны быть разделены парой (-1, -1). Пример: (1,1) (1,4) (3,4) и т.д. ---------418.PAS--------- И3.А Имеется следующее описание языка PROLAN/F, предназначенного для работ со строками символов и логическими величинами. Программа на PROLAN/F - последовательность разделенных запяты- ми определений функций и запросов значений этих функций для конкретных значений фактичкеских параметров (строковых или логических). В языке имется несколько встроенных функций: АИИИИИИИИИИИИИЖИИИИИИИИИИИИИИИЖИИИИИИИИИИИИИИЖИИИИИИИИИИИИИИИИИИИИИИБ Й Обращение Й Аргументы ЙТип значения Й Чему равно значение Й Й Й Й Й функции Й ДИИИИИИИИИИИИИКИИИИИИИИИИИИИИИКИИИИИИИИИИИИИИКИИИИИИИИИИИИИИИИИИИИИИЕ Й пусто(х) Й х - строка Й логический Й"да", если "х"- пустаяЙ Й Й Й Й строка Й Й Й Й Й Й Й консим(х) Й х - непустая ЙодносимвольнаяЙпоследнему символу "х"Й Й Й строка Йстрока(символ)Й Й Й Й Й Й Й Й начстр(х) Й х - непустая Й строка Й строке, получающейся Й Й Й строка Й Й отбрасыванием у "х" Й Й Й Й Й последнего символа Й Й Й Й Й Й Й симрав(х,y) Йx, y - символы Й логический Й "да", если "x" и "y" Й Й Й Й Й равны Й ВИИИИИИИИИИИИИЗИИИИИИИИИИИИИИИЗИИИИИИИИИИИИИИЗИИИИИИИИИИИИИИИИИИИИИИГ Определения новых функций имеют вид: <Имя определяемой функции> ( <список формальных параметров> ) = = <Условное значение> Здесь <список формальных параметров> - последовательность разделенных запятыми идентификаторов формальных параметров. <Условное значение> имеет вид: (<Условие> - <значение>, <условие> - <значение>, . . . иначе - <значение>) <Условное значение> полагается семантически эквивалентным первому из <значений>, для которых истинно записаное перед ним <условие>, если же все <услович> ложны - то <значению>, записанному после "иначе" <Усло- вия> и <значения> в <Условном значении> могут быть константами (логи- ческими для <условий> и логическими или условными для <значений> или обращениями к функциям (в том числе рекурсивными). Такими же могут быть и фактичесие параметры упоминаемых в <Условном значении> функций. Заметим, что в языке PROLAN/F нет таких понятий, как цикл, оператор присваивания и т.п., что делает программирование на нем не очень скучным. В описании приведен пример программы на PROLAN/F: И(x,y) = (x - y, иначе - нет), ИЛИ(x,y) = (x - да, y - да, иначе - нет), НЕ(x) = (x - нет, иначе - да), НЕ ( И (да, ИЛИ (да, нет))), И (нет, НЕ (нет)) и ее результат " нет,нет". Требуется дать на PROLAN/F определения: а) логической функции "страв(x,y), равной "да", если аргументы- строки x и y равны; б) логической функции "подстрока (x,y), равной "да", если строка x яв- ляется подстрокой строки y; в) какой-либо функции, определение которой на этом языке кажется Вам интересным и поучительным. Coryright: ИВ.В.ПрохоровА, 1989 И4.А Разработайте программу - интерпретатор программ, написанных на языке PROLAN/F (транслятор с PROLAN/F). ---------419.PAS--------- 1. Одной из очень важных задач практической информатики яв- ляется проблема архивной обработки текстов. Часто требуется тек- сты, заносимые в архив, преобразовать таким образом, чтобы для их хранения требовалось как можно меньшее количество памяти. В то же время следует сохранить возможность восстановления архивных тек- стов до исходного состояния. Требуется составить две программы, соответственно, программу-архивариус и программу-дезархивариус, выполняющие указанные процедуры с текстами, которые представляют собой последовательности строк, содержащих строчные и прописные буквы (латиницы и кириллицы), цифры, пробелы и знаки препинания: "." , "," ":", ";", "!", "?", "-", "<кавычки>", "(" и ")". Качество программ при их работоспособности оценивается по длине тестового текста, обработанного таким образом: чем он будет короче, тем выше качество программы-архивариуса. к.ф.м.н А.А.Орехов, ИК АН УССР (Киев) ---------422.PAS--------- 4. Исполнитель "Робот" умеет перемещаться по координатному полю, выполняя лишь четыре команды: "шаг_вверх", "шаг_вниз", "шаг_вправо" и "шаг_влево". Допустимы операторы типа "цикл_для", "цикл_пока", переменные целого типа и логическая конструкция, позволяющая определить достигнуто ли препятствие или нет. На ко- ординатном поле имеется некоторый замкнутый участок, составленный из соответственно перпендикулярных отрезков-стен целочисленной ненулевых длин, через которые, естественно, "Робот" проходить не может. Известно, что начальное положение его у стены. Составить алгоритм-программу, позволяющий определить, внутри или снаружи этого участка находился "Робот". 4а. Дополнительно к условию 4. определить площадь указанного участка. к.ф-.м.н. А.Г.Кушниренко, к.ф-м.н. Г.В.Лебедев МГУ (Москва) ---------423.PAS--------- * 5. Задана последовательность из единиц и нулей длины n. Составить алгоритм подсчета числа m-значных чисел, входящих в указанную последовательность (mf(x-h) и f(x)>f(x+h). Функция f(х)=sinx + x╜/1О, a=-2, b=5, h=О.2. ---------504.PAS--------- 1. Дана прямоугольная доска размером M\N клеток. Часть клеток доски заштрихованы. Составить алгоритм нахождения кратчайшего, не содержащего заштрихованных клеток пути из левого верхнего в правый нижний угол доски. Движение осуществляется из клетки в клетку по ве- ртикалям и горизонталям. ---------505.PAS--------- 2. Схема дорог между населенными пунктами представлена цело- численной таблицей А[1:n, 1:m]. Элемент таблицы A[i,j]=1, если суще- ствует дорога между i-м и j-м населенными пунктами, и A[i,j]=O, ес- дороги нет. Составить алгоритм, проверяющий существует ли хотя бы два населенных пункта между которыми нет пути (проходящего, быть мо- жет, через несколько других населенных пунктов). ---------506.PAS--------- 3. Детям нужно определить ведущего в некоторой игре. Для этого они, став в круг и определив первого, начинают считать с помощью "считалки", содержащей M слов. Тот, на ком заканчивается "считалка", выходит из круга. После этого "считалка" повторяется, причем с пер- вого участника. Если после очередного круга "считалки" первый участ- ник выбыл, то счет начинается со следующего за ним участника. Соста- вить алгоритм, позволяющий определить порядковый помер того из N иг- роков (N;<Фрагмент2> б) развилку вида "if" <Условие> "then" <Фрагмент1> "else" <Фрагмент2> "fi" или "if" <Условие> "then" <Фрагмент> "fi" в) цикл вида "while" <Условие> "do" <Фрагмент> "od" ДЗапись алгоритма на языкеА Д BА является последовательностью команд, разделенных символом ';'. Некоторые из команд могут быть иметь метки вида <Имя метки>: <Команда> Команды алгоритма на языке B - это либо элементарные коман- ды исполнителю, либо команды управления "if" <Условие> "goto" <Имя метки> и "goto" <Имя метки> Требуется написать для ЭВМ программы: И(а)А преобразователь записей произвольных алгоритмов на язы- ке A в записи эквивалентных алгоритмов на языке B; И(б)А преобразователь записей произвольных алгоритмов на язы- ке B в записи эквивалентных алгоритмов на языке A, который пре- образовывал бы по крайней мере те алгоритмы на языке B, которые получаются в п.(а). И(в)А то же, что и в п.(б), но по возможности для наибольшего количества классов программ на языке B. Эти классы должны быть указаны. ТРЕБОВАНИЯ К ВВОДУ ДАННЫХ Текст исходного для преобразования алгоритма должен вво- диться из файла A.PRG для языка A или из файла B.PRG для языка B. Допускается также ввод с клавиатуры. ТРЕБОВАНИЯ К ВЫВОДУ ДАННЫХ И1. АВ случае ввода записей исходных алгоритмов, синтаксичес- ки неверных или невозможных для преобразования разработанными в п.п.(а), (б), (в) программами, пользователю должны выдаваться наиболее понятные диагностические сообщения. И2. ААлгоритмы, получаемые после преобразования, должны выда- ваться на экран в наиболее удобном для пользователя виде. ПРИМЕЧАНИЯ И1. АНаличие пробелов и позиций переводов строк не играет ни- какой роли в обоих языках. И2. АЭлементарные команды исполнителю и условия имеют в обоих языках вид последовательностей символов, не содержащих '"' и ';'. И3. АИмена меток - последовательности букв и цифр, начинающи- еся с буквы. ---------536.PAS--------- Дана программа на языке, содержащем только следующие конструкции: <число> - целое число (в тексте исходной программы могут встречаться только целые от 0 до 9) <переменная> - заглавная буква латинского алфавита <объект> - это <переменная> или <число> <выражение> - это <объект>, или <объект> + <объект>, или <объект> - <объект> <условие> - это <объект> = <объект> или <объект> > <объект> и операторы: - присваивание: <переменная> := <выражение> например: Х := 7 + Y - вывод: PRINT <переменная> - ветвление: IF <условие> например: IF A>7 <оператор> B := A-7 . . . PRINT B необязател.V ELSE ELSE часть V <оператор> PRINT 7 V . . . ENDIF ENDIF - цикл: WHILE <условие> например: WHILE A>7 <оператор> A := A + 1 . . . END ЕND Операторы располагаются на отдельных строках без разделителей, пробелы игнорируются. Написать программу, которая по введенному тексту на входном языке выдает текст программы, приводящей к тому же результату, проводя следующие виды оптимизации: а) исключение константных присваиваний и константных выражений: пример: A := 7 -> заменить далее по тексту (где можно) A на 7, A := 7 + 8 -> аналогично заменить A на 15; б) исключение несущественных присваиваний: пример: А := Y + 1 - это присваивание несущественно, A := 8 если новое значение не используется; в) исключение неисполняемых циклов и ветвей: пример: IF 7>5 - условие всегда истинно ... ELSE V - часть ELSE никогда не исполняется ... V ENDIF г) составление и выдачу списка неинициализированных переменных; д) исключение операторов и их фрагментов, не участвующих в вычислении значений выводимых переменных; е) определение выводимых значений (если это возможно); Программу вводить в диалоге. Результатом должен быть текст преобразованной программы. Контроль корректности ввода не про- водить. Примечание: реализация пунктов б) и в) должна включать реа- лизацию пунктов а) и а),б) , соответственно. ---------543.PAS--------- 1. Определить, является ли данная двумерная таблица магическим квадратом. ---------223.PAS--------- 3. Заданы n точек на плоскости с координатами (x[1], y[1],..., (x[n], y[n]). Построить алгоритм соединения их непересекающейся незамкнутой ломаной. В результате его выполнения должна быть получена таблица i[1],...,i[n], указывающая порядок соединения точек. ---------547.PAS--------- 4. Ввести положительные числа A1, ... , AN (NЖ100). Составить из них последовательность наибольшей возможной длины, в которой каждое следующее число делится на предыдущее. (Например, в случае 3,2,4,8,4,1 получим последовательность 1,2,4,4,8). ---------549.PAS--------- 2. (7 баллов). На квадратном листе клетчатой бумаги размером NxN в каждой клетке записано число от 0 до 7. Если числа в двух клетках с общей стороной отличаются ровно на 1, то в обе клетки записывается большее из них. На каждом шаге производится сравнение ровно двух клеток, начиная с верхней левой клетки. а) Разработать алгоритм, который осуществляет описанную процедуру до тех пор, пока это возможно (4 балла). б) Зависит ли результат от порядка перебора клеток ? ( 1 балл) в) Конечен ли этот процесс ? ( 2 балла) ---------551.PAS--------- 3. Торт(6 баллов). На квадратном торте стоит N свечей. Можно ли одним прямолинейным разрезом разделить его на две равные по площади части, одна из кото рых не содержала бы ни одной свечи ? Свечи считать точками, каждая из которых задана парой целочисленных координат относительно центра торта. Разрез не может проходить через свечу. ---------552.PAS--------- 4. Сложение с помощью логических операций(8 баллов). Составить программу, которая выполняет сложение двух пятиразряд ных двоичных чисел, пользуясь операциями "И", "ИЛИ", "НЕ" и "СДВИГ ВЛЕВО"(на один разряд), которые выполняются так: 1) С=A переменной С присваивается значение числа А, в котором нули заменяются на 1, а единицы на 0(Операция "НЕ"). 2) С=АvВ поразрядная операция, результат выполнения которой оп ределяется таблицей 1(Операция "ИЛИ"). ТАБЛИЦА 1 0v0=0 0v1=1 1v0=1 1v1=1 3) С=А^В поразрядная операция, результат выполнения которой оп ределяется таблицей 2(Операция "И"). ТАБЛИЦА 2 0^0=0 0^1=0 1^0=0 1^1=1 4) С=<-A поразрядный сдвиг влево, т.е., i-тый разряд С получает значение i+1-го разряда числа А, 5-тый(младший) разряд С становится равным 0. Каждое из исходных чисел меньше 100002 ---------553.PAS--------- 5. (6 баллов). F(x)- процедура, вычисляющая значение непрерывной функции, кото рая определена на всей действительной оси, убывает при всех х, мень ших некоторого числа х0, и возрастает при всех х, больших, чем х0. Составить алгоритм, который определяет х0 с заданной точностью Е. ---------555.PAS--------- 7. (5 баллов). Дан выпуклый N-угольник координатами своих вершин. Найти наиболь шую по длине диагональ и напечатать вершины, которые она соединяет. ---------557.PAS--------- 9. "Болезнь ЭВМ"(2 балла). Доказать, что в 16-разрядной ЭВМ с объемом ОЗУ 192 Кбайт в любой момент времени t существуют две ячейки, содержащие одинаковые числа. ---------558.PAS--------- 1. Прямоугольники(14 баллов). Написать программу, отвечающую на вопрос, можно ли из N данных прямоугольников сложить один большой прямоугольник данного размера. Решить задачу отдельно для: 1) N=2 (2 балла) 2) N=3 (4 балла) 3) N=4 (8 баллов) ---------559.PAS--------- 2. Последовательность(5 баллов). Имеется последовательность из n неповторяющихся чисел. Она вво дится с клавиатуры в виде всевозможных пар соседних чисел в произ вольном порядке. Например, для пoследовательности 6,3,5,1,4,2 ввод может быть в таком порядке: (5,1), (4,2), (1,4), (6,3), (3,5). Написать программу, которая читает пары и печатает исходную пос ледовательность. ---------560.PAS--------- 3. Криптограмма(10 баллов). Текст закодирован с помощью сетки, представленной на рис 1. Для того, чтобы раскодировать сообщение, нужно наложить на текст сетку так, чтобы в отверстия можно было видеть символы криптограммы, на которую наложена сетка. Первый раз сетка накладывается так, чтобы сторона, отмеченная знаком "+", была верхней, затем сетка поворачи вается по часовой стрелке на 90 градусов, читается следующий набор символов, и т.д. до полного оборота на 360 градусов. ---------562.PAS--------- Задача 2.(1987) а). На станцию, изображенную на рисунке, прибывает поезд. Его ва- гоны пронумерованы в произвольном порядке. Требуется составить алгоритм, располагающий вагоны в порядке убывания номеров. В тупик помeщается то- лько один вагон или тепловоз. Предполагается, что диспетчер, управляющий маневрами, видит номе- ра всех вагонов поезда. Разрешается передвигать тепловозом вперед и на- зад любое количество вагонов, расцеплять и сцеплять соседние вагоны и тепловоз с вагоном, переводить стрелку. б). Решить ту же задачу, предполагая, что диспетчер видит номера только двух ближайших к стрелке вагонов и вагона в тупике. Номера ос- тальных вагонов диспетчер не запоминает. ЫЫЫ - вагон, ЫЫ- тепловоз ААААААААА ИААААААА \ ААААААААААА АААААААААААААААААААААААААААА\А\АААААААААААААААААА АААЫЫЫАЫЫЫА АЫЫЫАЫЫЫАЫЫАААААААААААААААААААААААААААААААААААА ---------563.PAS--------- Города некоторого государства имеют такой вид: в городе есть нес- колько площадей, каждая из них попарно соединена улицами с другими. Из каждой площади выходит четное количество улиц. С любой площади можно прийти на другую по цепочке улиц. Для каждой площади известен список площадей, связанных с ней улицами. Написать алгоритм, строящий маршрут, который позволяет обойти все улицы города, пройдя по каждой из них ров- но один раз. ---------564.PAS--------- Задача 4.(1987) Рощу ценных деревьев следует оградить забором, имеющим вид одной замкнутой линии. Известны координаты всех деревьев. Описать алгоритм для ЭВМ с графопостроителем, рисующий план рощи с забором минимальной длины. Деревья изображаются точками. Забор может проходить вплотную к деревьям. Графопостроитель может выполнять команды Нанеститочку(X,Y) и начертитьотрезок(X1,Y1,X2,Y2), где (X,Y) - координаты точки, (X1,Y1) и (X2,Y2) - координаты концов отрезка. ---------567.PAS--------- Задача 7.(1987-горОНО) В пробирке живут бактерии трех видов - А, В и С. Бактерии А пита- ются бактериями В, бактерии В - бактериями С, бактерии С - бактериями А. С какой-либо бактерией А за единицу времени может произойти одно из трех событий: 1). Бактерию А съедает какая-нибудь бактерия С; 2). Если бактерию А не съели, то она съедает Кав бактерий В и ста- новится сытой; 3). Если бактерий В не хватило для бактерии А (их количество ока- залось равным О), то А остается голодной. На этом же отрезке времени количество сытых бактерий А увеличива- ется в Lа раз,при этом они становятся голодными. Аналогичные события происходят в каждую единицу времени с бактери- ями В: 1). Бактерию В съедает какая-нибудь бактерия А; 2). Если бактерию В не съели, то она съедает Квс бактерий С и ста- новится сытой; 3). Если бактерий С не хватило для бактерии В (их количество ока- залось равным О), то В остается голодной. На этом же отрезке времени количество сытых бактерий В увеличива- ется в Lв раз,при этом они становятся голодными, и бактериями С: 1). Бактерию С съедает какая-либо бактерия В; 2). Если бактерию С не съели, то она съедает Кса бактерий А и ста- новится сытой; 3). Если бактерий А не хватило, С остается голодной. Количество сытых бактерий увеличивается в Lс раз, при этом они становятся голодными. Все события в данную единицу времени происходят одновременно. Написать программу, вычисляющую по количествам бактерий в началь- ный момент времени А(О), В(О), С(О) их количества в моменты времени от 1 до Т. Предполагается, что вычисляются средние количества бактерий, то есть они могут выражаться действительными числами. ---------569.PAS--------- Задача 9.(1986) Программа"Лабиринт" В программе реализована математическая модель лабиринта.Программа управляет подпрограммой школьника, имитирующей человека в лабиринте. Размеры лабиринта:по горизонтали - 20, по вертикали - 24. Задача 1. Пройти из левого верхнего угла в правый нижний. Задача 2. Выйти из заранее известной точки лабиринта в правый нижний угол. Задача 3. Выйти из заранее неизвестной точки лабиринта в правый нижний угол. Задача 4. Исследовать лабиринт - определить наличие проходов или стенок во всех возможных местах. Задача 5. Человек помещается в неизвестную точку. Сделав наимень- шее количество ходов, определить свое местоположение. Можно пользовать- ся результатами задачи 3. Задача 6. Известны начальное и конечное положения человека в ла- биринте. Требуется пройти из начальной точки в конечную по кратчайшему пути. Считается, что схема лабиринта известна после решения задачи 3. В каждой задаче подсчитывается число вызовов подпрограммы (ходов) и общее время работы подпрограммы. Результат оценивается по количеству ходов. Программа школьника записывается с адреса 5000. Школьникам запре- щается пользоваться именами, начинающимисмя с Q. Программа получает от подпрограммы школьника следующие параметры: VO$ - запрос о направлении хода VO$="с","ю","з","в" RE - сообщение о готовности результата;RE=0(не готов),1(готов) Программа передает подпрограмме школьника параметр OT - ответ о возможности хода. ОТ=1(можно), 0(нельзя). При ОТ=1 программа перемеща- ет человека в требуемом направлении. Кроме того,в задаче 4 передаются параметры X и Y - полученные ко- ординаты человека. Начало координат - левый верхний угол, его координа- ты (1,1), ось Х направлена вправо, ось Y - вниз. Можно использовать параметры ZA - номер задачи и SH - номер шага. ---------571.PAS--------- Задача 11. (Лгр) Написать программу, которая получает на входе число N и печатает на выходе фразу "N ворон",записывая числительные словами. 0 N 9999. Примеры: Вход Выход 1 одна ворона 3 три вороны 8 восемь ворон 55 пятьдесят пять ворон 200 двести ворон 1234 одна тысяча двести тридцать четыре вороны ---------572.PAS--------- 1. Дана таблица A[1:N]. Написать алгоритм для выяснения, существует ли элемент A[I], совпадающий со средним арифметическим всех остальных элементов таблицы. ---------574.PAS--------- 3. Заданы N точек на плоскости с координатами (X[1],Y[1]), ..., (X[N],Y[N]). Написать алгоритм для выяснения, могут ли эти точки (в данной последовательности) служить вершинами выпуклого многоугольника. ---------575.PAS--------- 4. Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящую в другие города. Стоимость такой дороги A[I,J] рублей, вне городов дороги не пересекаются. Написать алгоритм для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой. Результат задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить. ---------576.PAS--------- 1. Составить программу нахождения площади части, общей для всех N введенных пользователем прямоугольников (1ЖNЖ20). Стороны прямоугольников параллельны осям x и y. Пользователь вводит N, потом задает каждый из прямоугольников координатами его противоположных вершин (другими словами - концов одной из его диагоналей): (X1(1),Y1(1)), (X2(1),Y2(1)), ............................. (X1(N),Y1(N)), (X2(N),Y2(N)). ---------578.PAS--------- 3. Последовательность 011212201220200112200200120010... строится так: сначала пишется 0, затем повторяется такое действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2 и 2 на 0, т.е. 0 W> 01 W> 0112 W> 01121220 W> ... Составить программу, которая для введенного пользователем N (1ЖNЖ1000000) печатает N-й член последовательности. ---------579.PAS--------- 1. Составить программу для определения числа бутылок "Пепси", которые можно купить за данное количество денег. Пустые бутылки сдаются, вырученные деньги опять используются на покупку "Пепси". ---------580.PAS--------- 2. Найти 10 простых чисел, каждое из которых меньше 3000, которые составляют арифметическую прогрессию. ---------581.PAS--------- 3. Найти наименьшее число, пятая степень которого оканчивается тремя одинаковыми ненулевыми цифрами. ---------584.PAS--------- 3. Даны целые числа A(0), A(1), ... , A(5). Найти корни уравнения 5 4 3 2 А(5)x + A(4)x + A(3)x + A(2)x + A(1)x + A(0), если известно, что все корни - вещественные целые числа. ---------585.PAS--------- 4. Даны обозначения двух полей шахматной доски (например, a5 и c2). Найти минимальное число ходов, которое нужно шахматному коню для перехода с первого поля на второе. ---------586.PAS--------- 2. Составить алгоритм работы автомата, производящего расчет минимальным количеством купюр. ---------589.PAS--------- 3. Ввести вещественные числа A,B,C,U,V. Найти наибольшее и наименьшее значение функции y=axъ+bx+c на отрезке [u,v]. ---------591.PAS--------- 1. Даны координаты 3 точек плоскости. Проверить, образуют ли они прямоугольный треугольник. ---------592.PAS--------- 2. Дано предложение, в котором слова написаны заглавными латинскими буквами и отделены друг от друга одним или несколькими пробелами; в конце точка. Найти максимальную длину слова. ---------596.PAS--------- 2. Дано расписание движения поездов через некоторую станцию, в котором указаны номер поезда, время его прибытия и отправления. Составить алгоритм определения минимального числа путей, необходимых для размещения поездов на станции в соответствии с расписанием. ---------603.PAS--------- УСЛОВИЕ ОТ 10.1 Даны таблицы X[1:100] и Y[1:100]. Записать алгоритм, меняю- щий последовательно местами значения элементов X[k] и Y[k] этих таблиц для k=1,2,...,100, не используя промежуточных величин для хранения значений элементов таблиц. ---------605.PAS--------- УСЛОВИЕ ОТ 10.3 Составить алгоритм, подсчитывающий для текста, заданного в виде литерной переменной, частоты вхождения всех букв русского алфавита. ---------607.PAS--------- УСЛОВИЕ ОТ 10.5 В некотором городе все улицы проходят с севера на юг и с запада на восток. На некоторых перекрестках установлены телефо- ны-автоматы. Для каждого такого перекрестка заданы его коорди- наты X[i], Y[i] и количество телефонов на нем T[i],i=1,2,...,N. Написать алгоритм, определяющий координаты АТС:XАТС и YАТС, при которых сумма длин проводов, идущих от АТС к каждому автомату, минимальна. Провода разрешается прокладывать только вдоль улиц (то есть с севера на юг или с запада на восток). Если оптимальных точек несколько, достаточно найти любую. ---------610.PAS--------- УСЛОВИЕ РТ9.3 Последовательость 1.0,0,1,0,1,1,0,0,1,1,0,1,0,... строится так: первый ее элемент равен 1, остальные получаются из элемен- тов с меньшими номерами с помощью операции отрицания: 1, если x=0 NOT (x)= 0, eсли x=1 Второй элемент равен отрицанию первого, то есть 0 ; третий и четвертый равны отрицанию первого и второго соответственно; элементы с пятого по восьмой равны отрицаниям элементов 1-4 со- ответственно, и т.д.; элементы с номерами 2^k +1 ,..., 2^(k+1) равны отрицаниям элементов с номерами 1,2,...,2^k соответствен- но. Составить программу, вычисляющую N-й член описанной после- довательности по заданному N. ---------612.PAS--------- УСЛОВИЕ РТ 10.2 Два человека играют в "алгоритмическую игру". Игровое по- ле - лист бумаги в линейку, содержащий 20 строк. Игроки по оче- реди вписывают в любую незанятую строку по одному из операторов вида: 1. А:=1-А 2. В:=1-В 3. ЕСЛИ А=1 ТО В:=1-В ВСЕ 4. ЕСЛИ А=0 ТО В:=1-В ВСЕ 5. ЕСЛИ В=1 ТО А:=1-А ВСЕ 6. ЕСЛИ В=0 ТО А:=1-А ВСЕ Когда все строки заполнены, переменным А и В присваиваются значения из множества {0,1} (например, А:=1, В:=1 или А:=0, В:= 1) и выполняются все операторы в той последовательности, в ко- торой они записаны. Если в результате значения А и В различны, побеждает первый игрок, если равны - второй игрок. Есть ли у кого-либо из игроков стратегия, гарантирующая выигрыш независи- мо от начальных значений А и В? ---------614.PAS--------- УСЛОВИЕ РП 1.1 Дан список всех 64 полей шахматной доски 8х8 в виде число- вых координат. Написать алгоритм, устанавливающий, является ли этот список маршрутом ферзя по всем полям доски, то есть списком клеток, на которые последовательно становился ферзь. ---------618.PAS--------- 1. Дана таблица из чисел, расположенных по неубыванию. Расширить таблицу, добавив в нее заданное число, сохранив упорядочение. ---------622.PAS--------- 3. Дана таблица из N целых чисел. Составить алгоритм проверки, есть ли в таблице хотя бы одна пара рядом стоящих одинаковых чисел. ---------263.PAS--------- 2. Какое минимальное количество (p,q)-коней требуется для контроля: а) ограниченной шахматной доски размером m x n клеток; б) бесконечной полосы шириной m клеток; в) бесконечной плоскости. Примечаение 1. (P,Q)-конь - фигура, которая за один ход перемещается на p клеток по горизонтали и q клеток по вертикали или на q клеток по горизонтали и p - по вертикали. Например, (1,2)-конь - это обычный шахматный конь. Примечание 2. Фигура или группа фигур контролирует поле, если каждая клетка поля доступна за ноль, один или несколько ходов хотя бы одной фигуре. Например, для контроля стандартной доски размером 8х8 требуется два (1,1)-коня. ---------256.PAS--------- М2. Для каждого целого положительного числа n будем рассматривать всевозможные его представления в виде суммы одного или нескольких целых положительных слагаемых. Составить таблицу, в которой для каждого n указано число таких представлений (без учета порядка, так что, например, представления 3=2+1 и 3=1+2 считаются одинаковыми. Например, для n=4 таких представлений 5 (4, 3+1, 2+2, 2+1+1, 1+1+1+1). (Чем дальше будет заполнена таблица, тем выше будет оцениваться работа). ---------258.PAS--------- 2. Структура простого предложения имеет вид: [ определение 1 ] Подлежащее Сказуемое [ определение 2 ] [ дополнение ] [ обстоятельство ], члены в квадратных скобках могут отсутствовать. Сформулировать правила составления простого предложения и пред- ложить алгоритм, генерирующий по ним все простые предложения из заданного Вами словаря. Словарь состоит из 4-х групп слов (в каждой группе не менее двух слов): существительных, глаголов, прилагательных, наречий. ( Ю.С. Завальский ) ---------255.PAS--------- М1. Последовательность целых положительных чисел a , 0 а , а , ... строится так: если a четно, что a =a /2; если 1 2 n n+1 n an нечетно, что a = 3Ga + 1. n+1 n Найти минимальное n, для которого a =1, если n a) a = 27 0 б) а = 2 000 027. 0 ---------239.PAS--------- 1. На интервале (1000;9999) найти все простые числа, каждое из которых обладает тем свойством, что сумма первой и второй цифры записи этого числа равна сумме третьей и четвертой цифр. ---------236.PAS--------- 6. Задан массив чисел A[1:N,1:M], упорядоченный по убыванию по строкам и столбцам, т.е: A[I,1] Ж A[I,2] Ж ... для любого I A[1,J] Ж A[2,J] Ж ... для любого J. Найти элемент массива, равный заданному числу и отпечатать его индексы I,J. Напечатать слово "нет", если такого элемента не окажется. Решение необходимо найти на (M+N), а не за (M*N) циклов. ---------32.PAS--------- 3. Два робота приземляются с парашютом на числовую прямую, а в голове у них написанная Вами программа. Робот видит только то, что находится на его клетке (то есть может обнаружить свой или чужой парашют на месте приземления) и может перемещаться в соседние клетки. Роботы встречаются, когда они попадут в одну клетку. Написать алгоритм для встречи роботов. ---------171.PAS--------- Два робота-парашютиста одновременно десантируются на пря- мую линию в точки с целочисленной координатой. Оставив парашюты в точках приземления, они начинают двигаться, переходя в каждый момент времени на один шаг вперед или назад. Предложите инструкцию действий, одинаковую для обоих роботов, следуя кото- рой они смогли бы соединиться в отряд. ---------235.PAS--------- 5. Сообщество роботов живет по следующим законам: - один раз в начале года они объединяются в группы по три или пять роботов; - за год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых; - роботы собираются так, чтобы собрать за год наибольшее количество; - каждый робот живет три года после сборки. Известно начальное количество роботов К и все они только что собраны. Сколько роботов будет через N лет? ---------234.PAS--------- 4. Вывести в порядке возрастания все обыкновенные несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают числа 15. Массив при этом заводить не следует. ---------233.PAS--------- 3. Задана матрица M[1:N,1:K]. Определить, какие элементы M[I,J] совпадают со средним арифметическим элементов этой матрицы, получаемых вычеркиванием I-ой строки и J-го столбца. ---------232.PAS--------- 2. На олимпиаду по информатике приехало N школьников. N1 школьников знакомы между собой. Определить, при каких соотношениях между N и N1 можно опосредованно перезнакомить всех школьников между собой (незнакомые участники олимпиады могут познакомитьтся только через общего знакомого). ---------231.PAS--------- 1. Несамопересекающийся замкнутый контур на плоскости (многоугольник) образован 88 звеньями длины 2, соединяющими точки с четными значениями координат и параллельными координатным осям. Контур задан массивом X[1:88], Y[1:88] координат середин звеньев (не обязательно в порядке следования). Требуется по четным числам X0, Y0 определить, находится ли точка с такими координатами внутри контура или нет. ---------227.PAS--------- 2. Написать на алгоритмическом языке программу, которая находит и выводит на печать все четырехзначные числа abcd, для которых выполняются следующие условия: 1) a, b, c, d - разные цифры 2) ab-cd=a+b+c+d ---------225.PAS--------- 2. Последовательность 1001011001101001... строится так: сначала пишется 1, затем повторяется такое действие: уже написанную часть приписывают справа с заменой 0 на 1 и наоборот, т.е. 1WWe 10WWe 1001WWe10010110WWe ... Составить программу, вычисляющую n-ный член этой последовательности по заданному n. ---------77.PAS--------- 2.0 Заданы N точек на плоскости с координатами (X(1),Y(1)), ..., (X(N),Y(N)). a) Разработайте алгоритм соединения их непересекающейся ломаной замкнутой линией (если это возможно). В результате его выполнения должна быть получена таблица: I(1), ..., I(N), указывающая порядок соединения точек. б) Не забудьте показать, что Ваш алгоритм дает правильное решение. (12 очков = 7+5). ---------206.PAS--------- 4. Посередине клетчатого листа бумаги нарисована замкнутая несамопересекающаяся ломаная, звенья которой идут по сторонам клеток. Муравей может переходить на одну из четырех соседних клеток, отмечать клетки, где он уже был. Муравей видит, пересек ли он линию и вышел ли он на край листа. Написать алгоритм, который определяет, где находится муравей: внутри области, ограниченной ломаной, или снаружи ее. ---------207.PAS--------- 1. Даны две строки a,b. Составьте алгоритм, который определит, можгно ли из букв, входящих в строку a, составить b? ---------208.PAS--------- 2. На зимних Олимпийских играх в мужской лыжной эстафете 4x10 км стартовало N команд. В игровом протоколе имеются составы всех команд с указанием расстановки участников по этапам и время, показанное каждой командой на отметках 10, 20, 30 и 40 км. Составить алгоритм упорядочения всех лыжников в соответствии с показанным временем. ---------209.PAS--------- 3. Плюшкин не хочет выбрасывать календарь. Когда н снова пригодится в зависимости от номера года? ---------210.PAS--------- 4. Программа выводит на экран значение c. Чему будет равно c при k=1991; при k=1992? Придумайте программу для вычисления c, в записи которой не используются команды ветвления и цикла. 5 INPUT K 10 C=0: A1=1: A2=-1: M=1 20 IF M>=K THEN 90 30 IF A1>0 THEN 50 40 C=C-M: GOTO 60 50 C=C+M 60 A1=A1+A2: A2=A1-A2: A1=A1-A2 70 M=M+1 80 GOTO 20 90 PRINT C ---------211.PAS--------- 5. Даны две таблицы a[1:M] и b[1:N]. Определить максимальное число k такое, что путем вычеркивания некоторых элементов из a и b можно получить одинаковые последовательности чисел длины k. ---------214.PAS--------- 3. Составить алгоритм, который заносит в таблицу первые 1000 натуральных чисел, делящихся на 13 или 17. ---------213.PAS--------- 2. Упростить фрагмент программы на Бейсике 110 I=0 120 I=I+1 130 J=0 140 J=J+1 150 S(I,J)=0 160 K=0 170 K=K+1 180 S(I,J)=S(I,J)+(2*I+7)/(J-5)+3*K-4 190 IF K<=20 THEN 170 200 IF J<=5 THEN 140 210 IF I<=50 THEN 120 ---------205.PAS--------- 3. Составить алгоритм, который заносит в таблицу первые 1000 натуральных чисел, делящихся на 13 или 17. ---------203.PAS--------- 1. На избирательном участке в списке из 100 избирателей указываются фамилия и название улицы, на которой проживает избиратель. Определить, сколько избирателей живет на улице Тверской. ---------200.PAS--------- 5. Даны вещественные числа a1, ..., an. Известно, что среди них есть отрицательные. Пусть первый среди отрицательных членов имеет номер ak+1. Вычислить a1 + 2a2 + 2a3 + ... + 2ak-1 + ak. ---------199.PAS--------- 4. Даны натуральное n и вещественное a. Вычислить 1 1 1 W + WWWWW + ... + WWWWWWWWWWWWW a a(a+1) a(a+1)...(a+n) ---------196.PAS--------- 1. В таблице a[1:100] записаны нули и единицы. Заменить 0 на 1, а 1 на 0 ---------195.PAS--------- 6. Новобранцы выстроились в ряд и старшина скомандовал "направо", после чего каждый повернулся в произвольном направлении на 90 градусов. Тот, кто увидел лицо соседа, повернулся на 180 градусов. Определить, перестанут ли они вертеться? ---------193.PAS--------- 4. Числа a1, a2, ..., a30 - целые. Получить в порядке возрастания все целые числа из интервала (m,M), которые не входят в последовательности a1, ..., a30. ---------192.PAS--------- 3. Найти все делители натурального числа n. ---------191.PAS--------- 2. n - натуральное, a1, a2, ..., an - целые. Заменить все большие 7 члены последовательности числом 7. Найти количество таких членов. ---------190.PAS--------- 1. l и n - натуральные числа, lЖn. Натйи среднее арифметическое чисел a1, ..., al-1, al+1, ..., an (всех, кроме al). ---------188.PAS--------- 5. Написать программу для решения уравнения xy+x+y=1000 в целых числах. ---------187.PAS--------- 3. Даны действительные числа a1Жa2Ж...Жan и P, натуральное число kЖn. Удалить из последовательности число ak и вставить число P в полученную последовательность таким образом, чтобы сохранить порядок. ---------186.PAS--------- 2. Даны действительные числа x1, x2, ..., x17. Найти сумму значений V xi - xj V, 1 Ж i < j Ж 17. ---------185.PAS--------- 6. Дано натуральное n. Сколько различных цифр встречается в его десятичной записи? ---------184.PAS--------- 5. Дано натуральное число N. Вычислить произведение первых N сомножителей. 2 2 4 4 6 W G W G W G W G W G ... 1 3 3 5 5 ---------183.PAS--------- 4. Вычислить 1 WWWWWWWWWWWWWWWWWWWWWWW 1 1 + WWWWWWWWWWWWWWWWWWW 1 3 + WWWWWWWWWWWWWWW 1 5 + WWWWWWWWWWW . . . 1 101 + WWW 103 ---------182.PAS--------- 3. Пусть D - заштрихованная часть плоскости (верхний полукруг радиуса 0.6 с центром в точке O, из которого вырезана правая верхняя четверть круга с тем же центром радиуса 0.3). Функция определяется следующим образом: U = x+y, если (x,y),D; U= x-y в противном случае. Даны числа x,y. Найти U. ---------179.PAS--------- 1. Хлестакова пригласили управлять департаментом. В первый день ему прислали 1000 курьеров, а в каждый следующий - в 2 раза больше, чем в предыдущий. Хлестаков согласился, когда прислали 30000 курьеров. На какой день это произошло? (Учесть, что Хлестаков слаб в умножении и делении). ---------176.PAS--------- Двоичным деревом называется такое, из каждой вершины кото- рого исходит не более двух дуг. Обход такого дерева (порядок, в котором перечисляются все его вершины) можно задавать следующи- ми способами: ЛКП - для каждой вершины сначала обходится ее ЛЕВОЕ подде- рево, потом КОРЕНЬ (сама эта вершина), потом ПРАВОЕ поддерево; КЛП - сначала КОРЕНЬ, потом ЛЕВОЕ поддерево, потом ПРАВОЕ поддерево (тоже для каждой вершины); ЛПК - сначала ЛЕВОЕ поддерево, потом ПРАВОЕ, потом КОРЕНЬ. Например для дерева D / \ B E / \ \ A C G / F имеем: ЛКП=ABCDEFG, ЛПК=ACBFGED, КЛП=DBACEGF. Написать программу, которая по заданным представлениям КЛП и ЛКП одного и того же дерева вычисляет и печатает его пред- ставление ЛПК. Исходные представления вводятся как строки сим- волов, обозначающих вершины: сначала в представлении КЛП, затем в КЛП (длина этих строк не превосходит 100 символов). ---------175.PAS--------- Задача 3 (Разгадка шифра) Один из способов шифровки текста состоит в использовании некоторой перестановки букв алфавита: каждая буква сообщения заменяется на ту, которая ей соответствует в данной перестанов- ке. Однако, частота использования отдельных букв в текстах не одинакова: буква т, например, встречается в русских текстах го- раздо раньше, чем к. Написать программу, которая вводит два текста - один в обычном виде и по нему определяет частоту ис- пользования различных букв, другой - зашифрованный, который за- тем расшифровывается с помощью частот, вычисленных по первому тексту. ---------174.PAS--------- Задача 2 (Переписка с римским императором) Король Артур послал римскому императору срочное сообщение, в котором содержатся числа, записанные арабскими цифрами. Напи- сать программу, которая поможет императору понять сообщение пу- тем преобразования входного потока в идентичный выходной с пе- реводом всех чисел в римскую систему счисления. (Примечание: в сообщении встречаются только положительные целые числа, не пре- восходящие 4000). ---------173.PAS--------- Задача 1 (телефонные номера для шахматистов) Для представления телефонных номеров членам шахматного клуба телефонная компания решила выяснить, сколько различных 'шахматных номеров' имеется в ее распоряжении. Телефоный номер состоит из 7 цифр и не может начинаться с 0 и с 8. Написать программу, вычисляющую количество различных таких номеров, которые можно набрать на кнопочном телефонном аппарате ходом различных фигур: а) коня; б) слона; в) ладьи; г) ферзя; д) короля. Цифры на кнопочном телефонном аппарате имеют следующее расположение: 1 2 3 4 5 6 7 8 9 0 ---------172.PAS--------- Написать программу, которая находит как можно более длин- ную по числу ходов партию в игре "королевский квадрат", в кото- рой каждый ход приводит к появлению слова из заранее заданного множества слов. Правила игра. Имеется поле размером 5x5 клеток. В среднюю строку из пяти клеток вписано некоторое начальное слово из за- данного множества, по одной букве в каждую клетку. Каждый ход игры состоит в том, что в свободную клетку, примыкающую ка- кой-нибудь стороной к уже заполненной, ставится буква так, что- бы какая-набудь цепочка букв, образующаяся при чтении заполнен- ных клеток сверху-вниз слева-направо и проходящая через толь- ко что заполненную клетку, составляла какое-нибудь слово из за- данного заранее множества слов, в предыдущих ходах не встречав- шееся. Множество допустимых слов задается в виде текстового фай- ла, в котором слова разделены пробелами и переходами на новую строку, а после последней строки стоит признак конца файла. Результат работы программы должен выглядеть как последова- тельность строк, в каждой из которых печатается следующая ин- формация: номер хода, добавляемая буква, координаты клетки, но- вое слово. ---------170.PAS--------- Каждый из N участников бесконечно продолжающегося чаепития из сказки "Алиса в стране чудес" имеет свой строго определенный период пребывания за столом в течение суток (например, Заяц - с 23:00 до 8:00). Считается, что момент окончания чаепития для участника не входит в период его пребывания за столом. (такой промежуток в математике обозначается так: [23:00, 8:00) ). На- писать программу, которая по заданным периодам определяет время суток, в течение которого за столом одновременно находятся все участники чаепития. ---------30.PAS--------- Ленинградская городская олимпиада по информатике, 1991 г. 10 класс, теоретический тур. 1. Есть три кувшина с емкостью A,B,C, (A,B,C0) и неисчерпаемый бассейн с водой. Можно ли с помощью этих трех кувшинов отмерить D литров воды (D>0)? ---------169.PAS--------- Даны 3 пустых сосуда емкостью A, B и C литров и бассейн с водой. Написать программу, которая выясняет, можно ли, путем доливания воды в кувшин из бассейна, выливания воды в бассейн из кувшина и переливания воды из одного кувшина в другой отме- рить в одном из кувшинов ровно D литров воды? (A,B,C и D - це- лые числа). ---------168.PAS--------- На двух клечатых листах бумаги размером 8x8 закрашено по фигуре, состощей из 8 клеток. Фигуры задаются координатами зак- рашенных клеток. Написать программу, которая проверяет а) совпадают ли эти фигуры при переносах; б) совпадают ли эти фигуры при поворотах; в) конгруэнтны ли эти фигуры. ---------167.PAS--------- Имеется N спортсменов. Написать программу, которая находит все различные составы команд из K спортсменов, где K <= N. ---------166.PAS--------- Для задания больших наборов чисел, в которых много нулей, их переводят в плотное представление: из набора удаляют нули, после каждого ненулевого элемента вписывают его номер в исход- ном наборе, в конце приписыают нуль. Так набор { 0, 7, 0, 0, 0, 8 } перейдет в { 7, 2, 8, 6, 0 }. Написать программу, которая для наборов A={a1} и B={b1}, заданными плотными представлениями, вычисляет сумму a1*b1+a2*b2+..., не восстанавливая исходных наборов. ---------165.PAS--------- Имеется квадратная площадка размером 10х10 клеток. В пра- вом верхнем углу плошадки расположена вертикальная перегородка длиной в 3 клетки. В двух различных клетках площадки расположе- ны робот и контейнер. Робот исполняет 4 команды: СЕВЕР,ЮГ,ЗА- ПАД,ВОСТОК, соответствующие передвижению робота с клетки (x,y) на клетки (x,y+1), (x,y-1), (x-1,y),(x+1,y). Напишите программу, которая по начальным координатам робо- та и контейнера выдает по возможности кратчайшую последователь- ность команд управления роботом для перемещения контейнера на клетку (10,10). Или печатает, что переместить контейнер невоз- можно. ---------164.PAS--------- Новый микрокалькулятор "олимпиада-90" может оперировать только с целыми числами. Он имеет три регистра: A, B, C и умеет выполнть шесть команд: ВВОД - вводит число с клавиатуры в регистр A. ВЫВОД - выводит на индикатор регистр B и останавливает- ся. НУЛЬ - записывает нуль в регистр B. ПЛЮС - прибавляет к A содержимое B, B не изменется. СДВИГ - циклически пересылает значения между регистра- ми: A --> B --> C --> A БОЛЬШЕ N - если A > C, переходит к команде с номером N,команды в программе занумерованы с единицы. Требуется написать программу для калькулятора, решающую следующую задачу: с клавиатуры вводится последовательность чи- сел (не меньше двух). Последний член последовательности равен нулю. Известно, что больше в ней нулей нет. Вывести на индика- тор наибольшую сумму двух рядом стоящих чисел. ---------163.PAS--------- Имеются две строки: одна состоит из букв A и B, вторая - из цифр 0 и 1. Алгоритм должен определять, можно ли из перовой строки получить вторую, используя следующие операции: рарешает- ся заменять любую букву A на непустую последовательность цифр 0, а любую букву B - либо на непустую последовательность цифр 0, либо на непустую последовательность цифр 1. ---------162.PAS--------- Числа Фибоначчи U[1], U[2], ... определяются начальными значениями и соотношением: U[1] = 1 ; U[2] = 2 U[N] = U[N-1] + U[N-2] Рассмотрим систему счисления с двумя цифрами 0 и 1, в ко- торой в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа фибоначчи 1,2,3,5,8,13... . В этой системе счисления каждое положительное целое число единственным способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом. Даны две строки, представляющие числа A и B. Найти строку, представляющую число A+B. Пример. Исходные строки "10101" и "100" представлют числа 8+3+1=12 и 3. Ответом является строка "100100", представляющая число 13+2=15=12+3 Примечание. Строки могут быть столь длинны, что числа А и B превысят максимально допустимое в вашем компьютере целое чис- ло. ---------160.PAS--------- Задача 2 Для надежности некоторый текст был передан по линии связи трижды, но каждый раз ровно один символ был принят в искаженном виде. Требуется по трем полученным текстам восстановить исход- ный текст, или установить, что сделать это невозможно. ---------159.PAS--------- Задача 1 Известно, что значением переменной М является положитель- ное число. Требуется узнать, имеет ли оно симметричную десятич- ную запись. Примечание. Допускаются записи, начинающиеся с одного или нескольких нулей, так что при М=5, М=1100, М=13231 ответ должен быть утвердительным, а при М=246, М=5515 - отрицательным. ---------158.PAS--------- Практический тур Даны натуральные числа N и K. Требуется написать выраже- ние, которое вычисляет K**N. Можно пользоваться операциями * и ** (возведение в степень), круглыми скобками и переменной K. Рабочих переменных заводить нельзя. Умножение считается одной операцией, возведение в степень Q считается Q-1 операцией. Най- ти минимальное количество операций для данного N. Пример: для N=5 - три операции: (K*K)**2*K Окончательная формулировка: вывести как можно больше чле- нов последовательности OP(N) - минимальное количество операций для возведения в N-ную степень. ---------157.PAS--------- Задача 3 Были написаны вспомогательный алгоритм ОБМЕН и основной алгоритм СРЕДНЕЕ, который среди пяти попарно различных чисел находит такое, что два числа из оставшихся больше него, а два других - меньше. В момент, когда тексты алгоритмов распечаты- вались, печатающее устройство сломалось и стало печатать вместо всех цифр цифру 0. Замените эту цифру на 1, 2, 3, 4 или 5 так, чтобы получился правильный алгоритм СРЕДНЕЕ. Procedure ОБМЕН ( Var A,B : Integer ) ; Var W : Integer ; Begin W := A ; A := B ; B := W End ; Function СРЕДНЕЕ ( M1,M2,M3,M4,M5 : Integer ) : Integer ; Begin If M0 > M0 Then ОБМЕН ( M0,M0 ) ; If M0 > M0 Then ОБМЕН ( M0,M0 ) ; If M0 > M0 Then Begin ОБМЕН ( M0,M0 ) ; ОБМЕН ( M0,M0 ) ; End ; If M0 > M0 Then ОБМЕН ( M0,M0 ) ; If M0 > M0 Then Begin ОБМЕН ( M0,M0 ) ; ОБМЕН ( M0,M0 ) ; End ; If M0 > M0 Then ОБМЕН ( M0,M0 ) ; СРЕДНЕЕ := M0 ; End ; ---------156.PAS--------- Задача 2 Вдоль кольцевой дороги расположено М городов, в каждом из которых открылась кооперативная парикмахерская. Известна сто- имость СТРИЖКА[К] стрижки в городе К и стоимость ПРОЕЗД[К] про- езда по отрезку дороги, соединющей К-ый и (К+1)-ый города (ПРО- ЕЗД[М] - стоимость проезда между первым и М-ым городом). Для жителей каждого города определить КУДА[К] - город, куда им сле- дует съездить, чтобы подстричься самым дешевым образом, и КАК[К] - "по часовой стрелке" или "против часовой стрелке" (го- рода пронумерованы по часовой стрелке). ---------155.PAS--------- Задача 1 Пропала связь между роботом-разведчиком и космическим ко- раблем, совершившим посадку в бескрайней марсианской пустыне. В такой ситуации робот переходит на выполнение алгоритма АВАРИЙ- НЫЙ. При этом робот может исполнять следующие вспомогательные алгоритмы: СЕВЕР - продвижение на 30 метров на север ЮГ - продвижение на 30 метров на юг ВОСТОК - продвижение на 30 метров на восток ЗАПАД - продвижение на 30 метров на запад ОСТАВЬ - втыкание в песок специального флажка ВОЗЬМИ - взятие флажка Последнее действие возможно не всегда, а только тогда, когда флажок находится рядом с роботом. Для того, чтобы прове- рить возможность взятия флажка, робот может проверить выполне- ние условия РЯДОМ. В одном месте можно воткнуть только один флажок. Перед началом работы у робота всего три флажка. Исполнение алгоритма автоматически прервется, как только робот попадет в зону посадки космического корабля, имеющей фор- му круга диаметром 50 метров. Управляющее устройство робота не имеет оперативной памяти, поэтому никаких величин в алгоритме использовать не разрешает- ся. Разработайте алгоритм АВАРИЙНЫЙ, гарантирующий возвращение робота в зону посадки с любого расстояния. Поверхность марса считать плоской. ---------154.PAS--------- Задача 8 (2 балла) Сформулировать, что делает данный фрагмент программы: А := А + В В := В - А А := А + В В := -В ---------152.PAS--------- Задача 6 (5 баллов) На клетчатой бумаге нарисован замкнутый прямоугольник. В нем закрашена некоторая связная область, состоящая из клеток. Робот находится в левом верхнем углу. Он имеет бортовой вычислитель, и должен вычислить длину границы закрашенной области. Робот может перемещаться в этом замкнутом прямоугольнике и выполнять следующие команды: шаг на север, шаг на юг, шаг на запад, шаг на восток, + 1 (в счетчик бортового вычислителя), - 1 (в счетчик бортового вычислителя), сброс счетчика, показать значение счетчика. Робот умеет вычислять логические функции: на севере свободно, на севере закрашено, на юге свободно, на юге закрашено, на западе свободно, на западе закрашено, на востоке свободно, на востоке закрашено. Можно также конструировать сложные логические функции с помощью операций И, ИЛИ, НЕ. При составлении алгоритма для робота можно использовать команды ЕСЛИ и ПОКА. ---------151.PAS--------- Задача 5 (5 баллов) На клетчатой бумаге нарисовали окружность целого радиуса R с центром на пересечении линий. Найти К - количество клеток, целиком лежащих внутри этой окружности. ---------150.PAS--------- Задача 4 (8 баллов) Цифры двух положительных двоичных чисел хранятся в двух линейных таблицах. Получить третью таблицу, хранящую их произведение. ---------149.PAS--------- Задача 2 (10 баллов) В русском тексте на 1000 букв в среднем приходится: а - 62 б - 14 в - 38 г - 13 д - 25 е,е - 72 ж - 7 з - 16 и - 62 й - 10 к - 28 л - 35 м - 26 н - 53 о - 23 р - 40 с - 45 т - 53 у - 21 ф - 2 х - 9 ц - 4 ч - 12 ш - 6 щ - 3 ъ,ь- 14 ы - 16 э - 3 ю - 6 я - 18 _ - 174 (знак _ означает пробел между словами) Придумать кодирование букв последовательностями из 0 и 1 так, чтобы: - сообщение однозначно раскодировалось; - имело минимальную длину. ---------148.PAS--------- Переславль-Залесский. Городская олимпиада по программированию 1 9 8 9 г. Т Е О Р Е Т И Ч Е С К И Й Т У Р Задача 1 (10 баллов) Множество К строится следующим образом: 1) Два натуральных числа a, b включены в множество К. 2) Для любых x, y, входящих в К, число x + y + x*y включается в К. 3) Других элементов в К нет. Составить алгоритм, определяющий, является ли z элементом множества К, если заданы числа a, b. ---------146.PAS--------- 7. Снежинка (Ukr'88). Предположим, что снежинка образуется так: из центра вырас- тает 6 кристалликов - отрезков длины L, углы между соседними отрезками равны 60В; из их "свободных" концов вырастает по 5 отрезков; соседние отрезки образуют углы по 60В, длины этих от- резков в K раз меньше L; из их "свободных" концов аналогично вырастает по 5 новых отрезков, длина которых еще в К раз меньше, и так растет N "уровней" снежинки. Длина кристаллика на каждом уровне в K раз меньше длины кристаллика на предыдущем уровне. Написать алгоритм, рисующий снежинку для любого L, K, N. ---------140.PAS--------- 1. Обобщенные счастливые билеты (USSR'89). Написать программу определения количества билетов с 2n-значными номерами, у которых сумма первых n десятичных цифр равна сумме n последних десятичных цифр; при этом n - произ- вольное натуральное число. Программа должна вывести на экран последовательность ис- комых количеств для n = 1,2,3,... . При оценке программы учи- тывается количество выведенных чисел (количество обработанных n ). ---------138.PAS--------- 32. Домино (Ukr'89) Набор обобщенного домино состоит из М костей, на каждой кости нанесены два целых числа от 0 до N; любая пара чисел мо- жет встречаться в наборе 0, 1 или несколько раз. Значения кос- тей заданы в таблице ДОМИНО[1:M,1:2]. Составить алгоритм, оп- ределяющий, можно ли построить из всех костей набора цепь по правилам домино. ---------129.PAS--------- 23. Связность графа (ИК'86) В Антарктиде расположены N метеoрологических станций. Каж- дая станция соединена с другими станциями линиями связи. Из-за стихийного бедствия многие линии связи оказались нарушенными. Написать алгоритм, определяющий, между какими парами станций связь невозможна даже через цепочки других станций. Исправность линии связи между I-той и K-той станцией можно выяснить с помо- щью логической функции ЕСТЬСВЯЗЬ(I, K). ---------121.PAS--------- 15. K-е размещение Составить алгоритм, получающий на входе число K и выдающий на выходе К-тое по порядку четырехзначное число, у которого ни- какие две цифры не равны между собой. Первым таким числом явля- ется 0123. ---------118.PAS--------- 12. Поиск числа Дана упорядоченная по возрастанию линейная таблица нату- ральных чисел А[1] <...< A[N]. Найти наименьшее натуральное чи- сло, не представимое в виде суммы некоторых чисел из таблицы. Сумма может состоять и из одного слагаемого; каждый элемент та- блицы может входить в нее не более одного раза. Приемлемое решение должно укладываться в С*N действий, где С - постоянная, не зависящая от N. ---------115.PAS--------- 9. Драконова ломаная (Ukr'88) Возьмем полоску бумаги, согнем ее пополам К раз следующим образом: и развернем полоску так, чтобы углы на всех сгибах стали равны 90В . Посмотрев на торец полоски, увидим ломаную, которая назы- вается "драконовой ломаной К-го порядка": К=0 К=1 К=2 К=3 Написать алгоритм, который, получая на входе числа K и L, рисует драконову ломаную К-го порядка с длиной одного звена, равной L. ---------110.PAS--------- 4. Поиск палиндромов Символьная строка содержит последовательность слов, раз- деленных пробелами. Найти все палиндромы - слова, которые чи- таются слева направо так же, как и справа налево. ---------109.PAS--------- 3. Римские цифры. а). Переводчик, работающий с древней рукописью, в которой встречается много натуральных чисел в римской записи, хочет для перевода их в арабскую систему счисления пользоваться ЭВМ. Опи- шите алгоритм, который по записи числа, меньшего 3000, в рим- ской системе счисления строит его запись в арабской системе. б).Решите обратную задачу - опишите алгоритм, переводящий запись натурального числа до 3000 из арабской системы в римскую. Цифры римской системы: 1 - I 5 - V 10 - X 50 - L 100 - C 500 - D 1000 - M Число определяется из записи как сумма значений цифр, взя- тых со знаком "+" или "-" по такому правилу: значение цифры имеет знак "-" тогда и только тогда, когда рядом с ней справа есть цифра с большим значением. Слева от большей цифры может стоять не более одной меньшей. Справа от большей цифры может стоять не более 3 одинаковых меньших цифр. Цифры V, L, D не мо- гут стоять слева от больших цифр. Цифры I, X, C могут стоять слева от цифр со значением, певосходящим их значение не более, чем в десять раз. Примеры : 1987 = МCMLXXXII 999 = CMXCIX 28 = XXVIII 49 = XLIX ---------108.PAS--------- 2. Счастливые билеты (Лен.) Написать программу определения количества билетов с 6-значными номерами, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр. ---------107.PAS--------- 1. Часы с календарем (ИК-87) Написать алгоритм , обеспечивающий работу часов с календа- рем. Предполагается, что алгоритм запускается устройством, вы- дающим команду запуска каждую секунду; на входе у алгоритма - дата (год, месяц, число, день недели) и время (часы, минуты, секунды) в предыдущую секунду, алгоритм должен вычислить дату и время в текущую секунду. До первого запуска может быть установ- лена любая дата и время. Високосным считается год, номер кото- рого удовлетворяет одному из двух условий: 1) делится на 4 и не делится на 100; 2) делится на 400. ---------106.PAS--------- Двумерная таблица Р[1:M,1:N] заполнена нулями и единица- ми. Цепочкой будем называть последовательность единичных элемен- тов таблицы, в которой последовательно расположеные пары элемен- тов таблицы являются соседними по горизонтали, вертикали или ди- агонали. Смыкаясь концами друг с другом и с краями таблицы, це- почки делят таблицу на участки, заполненные нулями. Написать ал- горитм, заполняющий единицами участок таблицы, в котором нахо- дится заданный элемент, например: ............ ............ .11......... .11......... .1.11111.... .1111111.... .1......1... .11111111... .1..11.*.1.. .111111111.. .1.1.1....1. .111.111111. .1..11.1111. >---> .1111111111. .1.....1.... .1111111.... .1..1..11... .11111111... .1.1.1..1... .111.1111... .11...11.... .11...11.... ............ ............ На рисунке нулевые элементы обозначены точками, задан- ный элемент - звездочкой. Если заданный элемент окажется единичным, то алгоритм должен закончить работу, не преобразуя таблицы. Таблица зада- ется двумерным массивом. ---------104.PAS--------- В некотором государстве имеется N городов, некоторые из них соединены дорогами, грузоподъемность мостов на которых огра- ничена. Для каждого города задан список городов, связанных с ним дорогой, и список максимальных значений весов,которые можно про- везти по соответствующим дорогам. Между любыми городами есть хо- тя бы одна цепочка дорог. а) Выделены два города. Написать алгоритм, определяющий путь между этими городами (в виде последовательности городов),по которому можно перевезти груз максимального веса. б) Написать алгоритм, определяющий максимальный вес ав- томобиля, способного проехать из любого города в любой другой. ---------102.PAS--------- Грузовой автомобиль курсирует между N городами; в каждом городе его ожидают М отправителей грузов, стоящих в очереди. Оказавшись в очередном городе, водитель берет груз у первого по очереди отправителя и перевозит его в требуемый город; оставив там груз, берет в этом же городе следующий груз и т.д. , пока в очередных городах есть грузы. Отправитель, сдавший груз, выходит из очереди. В каждый город должно прибыть М грузов. Грузовик на- чинает движение с заданного города. Составить алгоритм, выясня- ющий, сможет ли грузовик перевезти все грузы без холостых пробе- гов. ---------101.PAS--------- 123 2. Найти все цифры числа 7 . ---------99.PAS--------- 3. Последовательность содержит n различных целых чисел. Требуется выкинуть минимальное возможное количество чисел так, чтобы оставшиеся шли в порядке возрастания. Результат - список номеров вычеркнутых чисел. ---------98.PAS--------- 2. Даны n точек на плоскости и число R > 0. Найти круг радиуса R, содержащий наибольшее число точек этого множества. ---------97.PAS--------- 11 класс 1. Определить, явялются ли два заданных натуральных числа двумя последовательными числами Фибоначчи. ---------96.PAS--------- 3. n!! - произведение всех натуральных чисел, меньших n и имеющих ту же четность, что и n. Найти последние k цифр числа n!!. ---------95.PAS--------- 2. Таблица содержит n натуральных чисел. Найти наименьшее число, которого нет в таблице. ---------94.PAS--------- Одесская областная олимпиада по информатике 1991 год Теоретический тур. 10 класс 1. Даны числа x1, y1, x2, y2, x3, y3 - координаты трех вершин прямоугольника. Найти координаты четвертой вершины. ---------93.PAS--------- Практический тур. 11 класс. 1. Дана прямоугольная таблица размером 2Nx2N (N>1), состоящая из нулей и единиц, причем нулей и единиц поровну. Изменять таблицу разрешается только одним способом, "вращая" четверку стоящих рядом элементов против часовой стрелки: A B B D WW> C D A C Требуется все единицы переместить в строки с номерами, большими N. ---------92.PAS--------- 3. В трехмерном пространстве задано множество материальных точек. Каждая из точек с максимальной массой исчезает, теряя десятую часть своей массы и раздавая оставшуюся массу поровну всем остальным, более легким, точкам. Определить суммарную массу множества материальных точек в тот момент, когда все оставшиеся в нем точки имеют одинаковые массы. ---------91.PAS--------- 2. N прямоугольников, стороны которых параллельны осям координат, заданы координатами концов своих диагоналей: (A1,B1), (C1,D1); (A2,B2), (C2,D2); ..., (An,Bn), (Cn,Dn). Определить, имеют ли эти прямоугольники общую часть. ---------90.PAS--------- 11 класс. 1. В предложении все слова начинаются с разных букв. Переставить, если можно, слова предложения в таком порядке, чтобы последняя буква каждого слова совпадала с первой буквой следующего слова. ---------89.PAS--------- 3. Задана матрица М*N, состоящая из единиц и нулей. Найти прямоугольник с наибольшей площадью, состоящий из нулей и с вершиной в клетке матрицы (1,1), если известно, что в клетке (1,1) находится 0. ---------88.PAS--------- 2. Написать программу, которая вычисляет значение выражения: T12 1 1 n 1 1- W + W -...-(-1) * W 2 3 n p Ответ представить в виде несократимой дроби WWW, где qT24 p и q - натуральные числа. ---------85.PAS--------- Задача 1. (100 баллов) Множество жильцов дома задано их возрастами в годах. Определить число и возраст самых молодых и число и возраст самых пожилых жильцов. Входные данные: возраст каждого человека в годах вводит- ся по отдельному запросу и занимает ровно две позиции. Приз- нак конца ввода - число 0 (оно не входит в список возрастов). Пример работы программы участника N 12: .RUN A12 Возраст 1-го человека: 91 Возраст 2-го человека: 5 Возраст 3-го человека: 5 Возраст 4-го человека: 0 2 человека возраста 5 лет 1 человек возраста 91 год . ---------84.PAS--------- Тур 2 Задача (60 баллов). В множестве из N различных целых чисел найти максимальное подмножество последовательно идущих чисел. Пример 1. (1,4,-4,9,5,2,3) Ответ: 1,2,3,4,5. Пример 2. (8,100,9,101,-5,7,6,102,104) Ответ: 6,7,8,9. Входные данные. Вначале программа должна ввести N - коли- чество элементов множества (0 < N < 100). Затем вводятся N це- лых чисел от -1000 до 1000. Выходные данные. Программа печатает значения входных дан- ных, затем размер найденного подмножества и его элементы. Пример: Количество чисел = 9 8 100 9 101 -5 7 6 102 104 Размер = 4 6 7 8 9 ----------------------------------------------------------- ---------83.PAS--------- 4. Сколько колец на шахматной доске. (40 баллов). На шахматную доску положили несколько тонких колец. При этом выполнен ряд условий: 1) диаметр колец больше размера клетки; 2) кольца не пересекаются; 3) кольца не пересекают углы клеток; 4) в клетке может находиться не более одной дуги одного кольца. Написать алгоритм, подсчитывающий число колец. Шахматная доска представляется квадратной таблицей, со- держащей числа от 0 до 6. Ноль означает, что клетку не пере- секает ни одно кольцо, а цифры с 1 до 6 обозначают варианты пересечения кольцом сторон клетки. 1 2 3 4 5 6 XWW*WWWY XWW*WWWY XWWWWWWY XWW*WWWY XWWWWWWY XWWWWWWY V * V V * V V V V * V V V V V V **** V * V V *** *** V ******** *** V V V V * V V * V V V V V V * V ZWWWWWW[ ZWW*WWW[ ZWWW*WW[ ZWWWWWW[ ZWWWWWW[ ZWW*WWW[ ---------82.PAS--------- 3. Значение функции. (20 баллов). Чему равно значение функции Ф(1989), вычисляемой по следу- ющему алгоритму ? Придумайте алгоритм для вычисления этой функции, в записи которого не используются команды ветвления и цикла. ЦЕЛ АЛГ Ф( ЦЕЛ К ) НАЧ ЦЕЛ С,М,А1,А2 С:=0; А1:=1; А2:=-1; М:=1 ПОКА М < К НЦ ЕСЛИ А1 > 0 ТО С:=С+М ИНАЧЕ С:=С-М ВСЕ А1:=А1+А2 А2:=А1-А2 А1:=А1-А2 М:=М+1 КЦ ЗНАЧ:=С КОН ---------81.PAS--------- 2. Сколько щупальцев у осьминогов. (10 баллов). Высадившись на планете Альфа, населенной разумными "осьми- ногами", космонавты увидели написанную на стене близлежащего строения формулу: 99 * 99 = 1210 Сколько щупальцев было у населявших планету Альфа осьминогов ? ---------80.PAS--------- 1. Найти квадрат. (10 баллов). Какое из нижеперечисленных чисел может быть квадратом целого числа: 508127128464 934541256800 308127128464 182398736658 129712121212 281894523765 ---------79.PAS--------- Написать программу, которая из букв А, В и С построит слово длины N, в котором два любых стоящих рядом подслова различны. Например: слово АВСАВА - составлено правильно; слово САВАВС - составлено неправильно. ---------78.PAS--------- 3.0 Вы организуете кооператив "Книгообмен" и имеете в своем распоряжении ЭВМ с достаточно большой памятью и богатым выбором языков программирования. Создайте систему по обслуживанию клиентов, т.е. людей, которые имеют 1 книгу, а хотят получить за нее какую-нибудь другую из желаемых. На вход системы поступают данные о клиенте, его книге и его пожелания, после чего он ставится на очередь. Клиент платит только тогда, когда найден прямой или промежуточный обмен. Некоторые клиенты требуют немедленного обмена. Для них, при невозможности обмена, система предлагает информацию о всех возможных обменах его книг и книг, им заказаных. Для создания системы Вы должны выполнить работу в следующем порядке: 1). Продумайте и опишите Ваш диалог с системой и все ее реакции (т.е. внешние спецификации). 2). Опишите внутреннее представление (т.е. структуру) данных. 3). Разработайте алгоритм поиска по различным запросам (например, по названию книги, ее автору, году издания, по автору книги и году издания и т.д.) 4) Напишите собственно программу, под управлением которой функционирует система. (20 очков = 10+5+3+2). ---------75.PAS--------- 1.0 Предлагается алгоритмический язык "Кобра". В языке разрешены переменные и константы двух типов: натуральные и булевские, которые объявляеются в начале процедуры, например, NAT(I,J,K) и BOOL(LOG,F) объявляют натуральные I,J,K и булевские LOG и F. Единственный выполняемый оператор - вызов процедуры по имени. Главная программа заканчивается оператором END. Имеется 4 стандартных процедуры: 1) IF(P,S1,S2) - если P, то S1, иначе S2. Здесь P - булевская переменная, а S1 и S2 - вызовы процедур. 2) INC(A) - увеличение натуральной переменной A на 1. 3) MOVE(A,B) - присваивание переменной А значения переменной B, если они одного типа. 4) EQU(A,B,C) - присваивание булевской переменной C значения "TRUE", если A=B и "FALSE" в противном случае. Пользователь может вводить свои процедуры, начинающиеся с заголовка PROC ИМЯ(СПИСОК ПАРАМЕТРОВ) и допускающие рекурсию. Все переменные - локальные, все имена - произвольные последовательности латинских букв. Пример: Процедура PLUS складывает A и B, помещая результат в C. PROC PLUS(A,B,C) NAT(A,B,C,D) BOOL(FLAG) MOVE(C,A) MOVE(D,0) EQU(B,0,FLAG) IF(FLAG,MOVE(C,A),INCREASE(C,D,B)) END PROC INCREASE(C,D,B) NAT(C,D,B) BOOL(LOG) INC(C) INC(D) EQU(D,B,LOG) IF(LOG,MOVE(C,C),INCREASE(C,D,B) Требуется: реализовать на языке "Кобра" процедуры вычитания, умножения, деления с остатком и возведения в степень для переменных типа "натуральный". (6 очков) ---------74.PAS--------- 5. Обнуление. В заданном двумерном массиве A[1:M,1:N] замените нулями элементы, стоящие в строках или столбцах, где имеются нули. Условие: Можно завести вспомогательный одномерный массив, но нельзя заводить вспомогательного двумерного. ---------73.PAS--------- 4. Оптовая покупка. Пара носков стоит 1.05 р.; связка (12 пар) стоит 10.25 р., а коробка (12 связок) стоит 110 р. Составьте программу, которая по числу M пар носков, которые хочет купить покупатель, вычисляет числа M1, M2, M3 коробок, связок и пар носков, которые ему следует купить. Пояснение: вместо 11 пар носков следует, например, покупать связку - это обойдется дешевле. ---------72.PAS--------- 3. Простые делители. Задано натуральное число N. Найти и напечатать все его простые делители. ---------71.PAS--------- 2. Многочлен. Вычислить коэффициенты A[1], A[2], ...,A[N] многочлена n n-1 P(x) =x + A[1]*x +...+ A[N-1]*x + A[N] с заданными действительными корнями X[1], X[2], ..., X[N]. ---------70.PAS--------- 1. Правый сосед. Задан массив положительных чисел A[1:N]. Заменить значение каждого элемента А[I] значением ближайшего элемента A[J], следующего за ним и большим его. Если такого элемента А[J] не найдется, то заменить A[I] нулем. Обязательное условие: Задача должна выполняться в C*N действий (а не C*Nъ). Можно завести вспомогательные массивы. Пояснение: Так, например, массив 1, 9, 8, 5, 9, 3, 4, 5, 2 должен замениться таким: 9, 0, 9, 9, 0, 4, 5, 0, 0 ---------69.PAS--------- 2. На планете Тетрона живут гуманоиды-тетрики. Глаза у тетриков - ромбовидные, вокруг ромбовидных зрачков - несколько точек. Специалисты по тетрофориентации установили связь между расположением точек и склонностями юных тетриков. Так, если в левой верхней четверти глаза точек больше, чем в других четвертях - это будущий программист-компьютетроник, максимум в правой верхней части выдает прирожденного специалиста по выращиванию съедобной тетравы, в левой нижней - будущего педагога-тетренера, в правой нижней - врача-тетрапевта. Если же точек везде поровну - быть тетрику специалистом по тетрофориентации. Смоделировать таинство тетрофориентации, генерируя случайное расположение точек. Оценить, какую долю населения Тетроны составляют специалисты по тетрофориентации. ---------68.PAS--------- 2 тур. 24.01.90 1. Дано арифметическое выражение, состоящее из букв, цифр, знаков арифметических операций и скобок, записанное в общепринятой форме. Составить программу, удаляющую из выражения лишние пары скобок, не влияющие на порядок выполнения операций, например: ((6/2)*А+(8-5))/(E) => (6/2*A+8-5)/E ---------67.PAS--------- 5. На разбитом на клетки и ограниченном сплошной линией прямоугольном поле неизвестных размеров имеется робот, способный понимать и исполнять следующие команды: - сделать шаг (в соседнюю клетку), - шагать до упора, - повернуть налево/направо, - повернуть на север/юг/запад/восток, - впереди/слева/справа свободно, - впереди/слева/справа занято. Две последние команды проверяют выполнение указанных условий и отвечают "да" или "нет". Попытка выполнить команду "сделай шаг" при наличии перед роботом стены или препятствия приведет к аварии. На роботе также есть счетчик, выполняющий команды: - установить ноль, - добавить единицу, - выдать результат. В поле расположено неприлегающее к стенам препятствие Г-образной формы. Ориентация его неизвестна. Путник находится в одной из пустых клеток. Используя команды управления роботом и счетчиком и управляющие конструкции если-то-иначе, выбор, пока, цикл N раз, составить алгоритм определения периметра препятствия. ---------66.PAS--------- 4. Упорядочить по алфавиту большой набор русских слов. Рассмотреть варианты: а) весь набор помещается в оперативной памяти ЭВМ; б) набор размещен во внешней памяти и целиком в оперативной памяти не помещается. ---------65.PAS--------- 3. Длины сторон прямоугольника - целые числа. Из одной вершины проводится линия - биссектриса, достигнув стороны прямоугольника, линия изламывается на 90 градусов, у другой стороны снова изламывается и т.д., пока не достигнет одной из вершин прямоугольника (подобно движению шара по биллиардному столу). Составить программу для определения числа точек излома и всей длины ломаной. ---------64.PAS--------- 2. Два N-угольника заданы координатами вершин. Найти расстояние между ними. ---------63.PAS--------- 4-я миасская олимпиада по информатике. 1. Вокруг считающего N человек, занумерованные по часовой стрелке. Считающий ведет счет до M, начиная с первого. Человек, на котором остановился счет, выходит из круга, счет продолжается со следующего. При этом выбывшие не считаются. И так до тех пор, пока не останется один человек. Определить его начальный номер. ---------62.PAS--------- 5. Смоделировать работу лифта в 9-этажном здании: а) Лифт в жилом доме. Вместимость - 4 человека независимо от веса. Пассажиры появляются случайным образом, чтобы подняться с 1-го этажа или опуститься на 1-й. На каждом этаже - одна кнопка вызова. Занятый лифт не реагирует на вызов. (20) б) Лифт в учреждении. Грузоподъемность - 500 кг, пассажиры массой от 50 до 100 кг появляются случайным образом, чтобы переместиться с любого этажа на любой. На 1-м и 9-м этажах - одна кнопка вызова, на других - по две - "вверх" и "вниз", и лифт останавливается, чтобы взять попутных пассажиров. (30) в) Рядом два лифта типа Б с общими кнопками вызова (40). ---------61.PAS--------- 4. Смоделировать блуждания слепого, стремящегося выйти из квадратной комнаты, имеющей одну прикрытую, но не запертую дверь в середине стены (15). ---------60.PAS--------- 3. Составить программу, которая по восьми введенным числам - координатам вершин четырехугольника - определяет: а) выпуклый ли он б) какова его площадь (12) ---------59.PAS--------- 2. Составить кратчайшую (по числу символов) программу, изображающую на графическом или текстовом экране лист тетради в косую линейку (10). ---------58.PAS--------- 1. Составить программу, изображающую на графическом или текстовом экране Ваш портрет или компьютер (7). ---------57.PAS--------- 12. (25) Промоделировать простейшую дорожную ситуацию: - по каждой стороне участка дороги с двусторонним движением движется не более одной машины; - имеется один пешеходный переход, оснащенный светофором, где иногда появляется не более одного пешехода, желающего перейти дорогу; - пешеход начинает двигаться только на зеленый свет. ---------56.PAS--------- 11. (20) Числа 46816(М) и 160125(N) представлены в разных системах счисления с неизвестными основаниями MЖ10 и NЖ10. Существуют ли такие M и N, что эти числа равны? ---------55.PAS--------- 10. (15) Найти наименьшее число K элементов, которые надо выкинуть из данной последовательности A(1), ..., A(1000), чтобы осталась возрастающая последовательность. ---------1.PAS--------- 1. Тройка чисел (T1,M1,C1) задает стартовое время, а тройка (T2,M2,C2) - финишное время участника лыжной гонки 30 км (часы, минуты, секунды). Проверить корректность данных и найти результат участника. ---------2.PAS--------- Заданы две таблицы А[1:N] и В[1:N]. Построить таблицу натуральных чисел С[1:N] такую, чтобы сумма А(1)*В(С(1)) + А(2)*В(С(2)) + ... + А(N)*В(С(N)) была бы минимальной. ---------54.PAS--------- 9. (12) Напечатать 16-ричную таблицу умножения, так же как печатают обычную на обложке тетради. ---------53.PAS--------- 8. (10) Разместить N*N чисел в квадратной таблице амфитеатром, в центре - наименьшие, а по краям - наибольшие. ---------52.PAS--------- 7. (10) Даны 2 текста. Найти: а) Одно из общих слов, встречающихся в текстах; б) самое длинное общее слово. ---------51.PAS--------- 6. (8) Написать для троллейбусного депо программу, которая к 1 апреля напечатает все 6-значные счастливые талоны. ---------50.PAS--------- 5.(7) Оптимизировать, т.е. изменить для уменьшения времени счета следующий фрагмент программы на Бейсике или Рапире: - Бейсик - 110 I=0 120 I=I+1 130 J=0 140 J=J+1 150 S(I,J)=0 160 K=0 170 K=K+1 180 S(I,J)=S(I,J)+(2*I+7)/(J-5)+3*K-4 190 IF K<=20 THEN 170 200 IF J<=5 THEN 140 210 IF I<=50 THEN 120 - Рапира - 11 1 W> I 12 ПОКА I<= 50 :: 13 I+1 W> I ; 1 W> J; 14 ПОКА J<=5 :: 15 J+1 W> J ; 0 W> S[I,J]; 1 W> K; 16 ПОКА К<=20 :: 17 К+1 W> К; 18 S[I,J]+(2*I+7)/(J-5)+3*K-4 W> S[I,J] 19 ВСЕ 20 ВСЕ 21 ВСЕ ---------49.PAS--------- 4.(7) Написать программу, заполняющую экран текстом по спирали - скручивающейся или раскручивающейся. ---------48.PAS--------- 3.(7) Напечатать все 4-значные десятичные числа, у которых все цифры разные. Обобщить на N-значные числа. ---------47.PAS--------- 2.(7) Смоделировать работу табло типа "БЕГУЩАЯ СТРОКА", т.е. однострочного дисплея (или линейной таблицы), где символы текста печатаются справа и исчезают слева. ---------46.PAS--------- г. Миасс , 2-ая олимпиада по информатике 1988 г. 1.(5) В таблице А[1:100] подсчитать количество таких N, что A(N) не меньше всех предыдущих элементов A(K), K0 THEN 30 70 PRINT "S= ";S 80 END б/ 10 S=0 20 N=1 30 INPUT X 40 S=(S+X)/N 50 N=N+1 60 IF X<>0 THEN 30 70 PRINT "S= ";S 80 END ---------12.PAS--------- 2. Школьник написал программу "Модель жизни". В некоторых клетках поля М x N живут организмы; задается их расположение в начальный момент времени, например, Если в текущий момент времени по соседству с организмом (по горизонтали,вертикали и диагонали) есть два или три организма,он будет жить и в следующий момент времени; если по соседству с организмом меньше двух или больше трех организмов, в следующий момент времени он умрет или от одиночества или от перенаселения. Если рядом с пустой клеткой находится ровно три организма, в следующий момент времени в ней появится новый организм. Пример последовательных состояний поля: Программа вычисляет положение организмов для Т моментов времени. Найти и исправить ошибки и недочеты в программе: 10 READ M,N,T. 20 DIM P(M,N) 30 FOR I=1 TO M 40 FOR J=1 TO N 50 READ P(I,J) 60 NEXT I, J 70 FOR I=1 TO T 80 FOR J=1 TO M 90 FOR K=1 TO N 100 S=0 110 FOR L=J-1 TO J+1 120 FOR R=K-1 TO K+1 130 S=S+P(L,R) 140 NEXT R,L 150 IF P(J,K)=1 THEN IF S<3 OR S>4 THEN P(J,K)=0 ELSE IF S=3 THEN P(J,K)=1 160 LOCATE J,K 170 IF P(J,K)=1 THEN PRINT "*" ELSE PRINT " " 180 NEXT K,J,I 190 END ---------13.PAS--------- 2.а/ Два человека играют в такую игру: имеется поле MxN(M и N нечетные),игроки по очереди ставят на поле по одному шахматно му королю. Короля можно ставить на любую клетку,которая не за- нята и не находится под боем какого-либо короля, поставленно- го раннее любым из игроков. Игрок, который не сможет сделать очередной ход, считается проигравшим. Написать программу, выступающую за игрока,имеющего выигрыш ную стратегию. б/ Задача аналогична задаче 2.а/, но на поле выставляются ферзи. ---------15.PAS--------- П.1. Дана программа упорядочения строк 2-х мерного массива А(М,N) по возрастанию k-й строки. Найти и исправить ошибки в прог- рамме, внеся в нее как можно меньше изменений: 10 DIM A(M,N) 20 FOR I=0 TO M 30 FOR J=0 TO N 40 READ A(I,J) 50 NEXT J 60 NEXT I 70 READ K 80 FOR I=0 TO M 90 FOR J=0 TO N-1 100 MIN=J+1 110 FOR L=J+2 TO N 120 IF A(K,L) < A(K,MIN) : MIN=L 130 NEXT L 140 B=A(I,J) 150 A(I,J)=A(I,MIN) 160 A(I,MIN)=B 170 NEXT J 180 NEXT I 190 FOR I=0 TO M 200 FOR J=0 TO N 210 PRINT A(I,J) 220 NEXT J 230 PRINT 240 NEXT I ---------16.PAS--------- П.2. Написать программу-определитель, задающую человеку вопросы о внешнем виде растений(размере, цвете цветка, форме листьев и плодов и т.п) и определяющую растение из следующего списка: ромаш- ка, роза, земляника, яблоня, липа,дуб, береза, сосна, ель, свекла, морковь, капуста, картофель, подсолнечник, тыква, кра- пива. Программа должна обходиться как можно меньшим количеством вопросов. Вопросы с названиями растений задавать запрещается. ---------18.PAS--------- 1. Написать алгоритм выплаты заданной суммы копеек, меньшей 30, минимальным количеством монет. ---------19.PAS--------- 2. Все стены дома имеют длину 5 м. Северная и южная стены - белые, западная и восточная - синие. Человек прошел от юго-восточного угла дома А метров на юг, В метров на восток и С метров на север и посмотрел на свой дом. Написать алгоритм, который определяет, что увидит человек. ---------20.PAS--------- 3. Алгоритм обрабатывает некоторые сочетания букв В, П, М. Например, алгоритм переводит слово ПВПВМВ в слово ПВ, МВМВПВМВ W> МВМВ, ПВПВ W> ПВПВ, МВПВПВПВ W> ПВПВ, МВПВПВМВПВ W> ПВ. Для некоторых слов, например: ППВ, МВМП, ВВ, ПВПМПВ алгоритм дает сообщение "ОШИБКА". а) опишите такой алгоритм. б) какой смысл можно придать такому алгоритму? ---------21.PAS--------- 4. Что делает данный алгоритм на языке Бейсик? 10 M=1 20 K=1 30 P=0 40 IF K>3*M THEN 60 45 IF K*K<3*M*M THEN P=P+1 46 K=K+1 50 GOTO 40 60 PRINT P 70 M=M*10 80 GOTO 20 Как можно ускорить его работу (возможно, путем усложнения записи)? ---------22.PAS--------- I группа (7-9 классы), II тур (за дисплеем). 1. Написать и отладить программу, которая по заданным трем числам определяет, является ли сумма каких-нибудь двух из них положительной. ---------23.PAS--------- 2. Автомат проводит кистью по отрезку [19,88] от точки A до точки B, а потом от точки C до точки D. Написать и отладить программу, которая определяет, какая часть отрезка окрашена. ---------24.PAS--------- II группа (10 класс), I тур (письменный). 1. Написать алгоритм выплаты заданной суммы копеек, меньшей 50, минимальным количеством монет. ---------25.PAS--------- 2. Тонкая синяя стена высотой 3 м и длиной 6 м (ось X) и тонкая зеленая стена высотой 3 м и длиной 3 м (ось Y) образуют прямой угол. Что увидит человек, стоящий в точке с целочисленными координатами X м и Y м и смотрящий в сторону угла (начала координат)? ---------26.PAS--------- 3. Алгоритм обрабатывает некоторые сочетания букв. Например, алгоритм переводит слово ПВПВМВ в слово ПВ, ПКПВМК W> ПВ, ПУМУМУМУ W> МУМУ, ПСМК W> ПСМК, ПДПДПДМВМДМД W> ПДМВ, ПТПСМТМТ W> ПСМТ. Для некоторых слов, например, ППВ, МВМП, КВПВ, ПКПМПВ алгоритм дает сообщение "ОШИБКА". а) опишите такой алгоритм. б) какой смысл можно придать такому алгоритму? ---------27.PAS--------- 4. а) Что делает данный алгоритм на языке Бейсик? б) Как можно ускорить его работу (возможно, путем усложнения записи)? 10 M=1 20 P=0 30 FOR K=-2*M TO 2*M 45 FOR T=-2*M TO 2*M 50 IF K*K+T*T <= M*M THEN P=P+1 60 NEXT T: NEXT K 70 PRINT P 80 M=M*10 85 GOTO 20 ---------28.PAS--------- II группа (10 класс), II тур (за дисплеем). 1. Написать и отладить программу, которая по заданным пяти числам определяет, является ли произведение каких-нибудь двух из них отрицательным. ---------29.PAS--------- 2. Задан массив A(1), ..., A(5) целых чисел. Для каждого из значений K=1, ..., 5 на прямой автомат красит точки A(K), A(K)+1, A(K)+2. Сколько всего точек будет покрашено? ---------31.PAS--------- 2. N господ периодически (с периодом 1 день) в определенные часы пьют чай. Найти время, когда они пьют чай одновременно. ---------33.PAS--------- ЛЕТНЯЯ ШКОЛА ЮНЫХ ПРОГРАММИСТОВ ЛИТВЫ (1986 ГОД) 1. Существуют числа, обладающие свойствами: - число делится на все свои цифры; - число, полученное из данного записью цифр в обратном порядке, тоже делится на все свои цифры. Примером такого числа является 216. Составить программу для печати всех трехзначных чисел, обладающих этими свойствами. Числа с одинаковыми первой и последней цифрой не печатать. ---------34.PAS--------- 2. Дана функция FUNCTION F(X:INTEGER); INTEGER; BEGIN IF X>=101 THEN F:=F-10 ELSE F:=F(F(X+11)) END; Какое значение принимает F(95)? ---------35.PAS--------- 3. Составить программу для печати чисел из интервала [1,N], являющихся одновременно треугольными и квадратными. ---------36.PAS--------- 4. Написать программу, которая определяет, каким числом нулей оканчивается N!. ---------37.PAS--------- 5. Даны координаты поля на шахматной доске, на котором находится конь. Напечатать координаты всех полей, куда конь может пойти. ---------38.PAS--------- 6. В интервале от 1 до N найти все числа М такие, что М нацело делится на М1, где М1 - число М, записанное в обратном порядке. ---------39.PAS--------- 7. Известно, что некоторые бактерии размножаются каждые три минуты, разделяясь на две. Однако, не все бактерии доживают до трехминутного возраста. Каждую минуту треть всех бактерий погибает. Составить программу, которая печатает число бактерий через N минут, если в начале было К только что родившихся бактерий (N и К - целые числа). A*.FRM*.MAC<БA*.FRM