IV обласна олімпіада учнів 8-10 класів з інформатики Хмельницький, 1990 рік Т е о р е т и ч е с к и й т у р Задача 1. Однажды Покупатель обратил внимание, что Продавец, у которого он постоянно делал покупки, старается, давая сдачу, набрать нужную сумму денег как можно более "крупными" монетами. - Почему Вы так делаете? - спросил он Продавца. - Так проще и быстрее - ответил Продавец. - Но ведь может не найтись нужных "крупных" монет! И тогда при дется давать сдачу "мелкими" монетами. - Ну, что Вы! Среди имеющихся монет всегда найдется самая "кру пная", не полтиник, так двугривенный, не двугривенный, так пятиал тынный или какая-нибудь другая монета. - Хорошо. Но тогда Вы должны знать все способы размена любой суммы денег монетами разного достоинства, а это ведь невозможно! - Да, это невозможно, но мне это и не нужно. Я знаю алгоритм, которым пользуюсь и который ... позволяет при необходимости указать все различные варианты размена любой суммы денег монетами, достоинс твом меньше рубля. Можете ли Вы разработать такой же алгоритм? Задача 2. Когда-то очень давно в шахматном королевстве всем Фи гуры ходили так, как вздумается. Но потом Королю надоели эти "беспо рядки" и он издал Указ, по которому каждой Фигуре предписывалось хо дить определенным образом. Чтобы этот Указ строго исполнялся, Ко роль приказал каждый ход всех Фигур записывать (что сейчас и делают ют шахматисты), чтобы можно было выявить нарушителя и за неповинове ние снять с Доски. Как-то раз Король повелел проверить запись ходов Коня и доло жить, правильно ли Конь избрал свой маршрут. Но никто в шахматном королевстве проверить ходы Коня не смог - ведь ни одной из Фигур (по Королевскому Указу) не разрешалось ходить так, как Коню. Можете ли Вы, зная запись ходов Коня (в виде списка координат некоторых N полей шахматной доски размером 8 \8), разработать алго ритм, позволяющий определять, является ли эта запись разрешенным маршрутом для Коня? Задача 3. Разработать алгоритм, позволяющий разлагать любое натуральное число K (K 2 ) на простые множители. Результат решения разрешается представить одним из двух спосо бов: 1) таблицей множителей; 2) каждый полученный множитель выводить командой ПЕЧАТЬ(имя переменной) Задача 4. В некотором арифметическом выражении удалили все символы, кроме скобок. Составить алгоритм, определяющий по получен ной последовательности скобок, правильно ли они были расставлены. Задача 5. Жители некоторого племени говорят на каком-то стран ном языке: любое произносимое слово они образуют из всех букв неко торого алфавита, состоящего из n букв. Слова, в которых порядок сле дования букв совпадает, считаются одинаковыми; если же в двух словах порядок следования букв не совпадает, то такие слова считаются раз личными. Старейшины этого племени поручили самому мудрому "филологу" со ставить словарь всех слов языка, на котором они говорят. "Филолог" принялся за работу. Не прошло и 2О лет, как такой словарь был соста влен. Старейшины остались довольны, но сам "филолог" не был уверен, что все возможные слова включены в его словарь. Можете ли Вы справиться с таким же заданием, но так, чтобы на верняка в словарь племени были занесены все различные слова, упот ребляемые жителями? Примечание. При разработке алгоритма разрешается использовать специальную команду ПЕЧАТЬ(имя). По этой команде на печатающее уст ройство будет выводиться значение величины, имя которой указано в скобках. Если в скобках после имени величины поставлен символ "точка с запятой", например, ПЕЧАТЬ(А;), то после печати значения величины А повторная печать будет продолжена в той же строке. Задача 6. Дана таблица n целых чисел. Разработать алгоритм, по зволяющий найти в этой таблице "симметричную" часть наибольшей длины подряд идущих элементов. В "симметричной" части первый элемент равен последнему, второй- предпоследнему и т.д. Задача 7. На прямой окрасили n отрезков. Известны координаты L[i] левого конца и координаты R[i] правого конца i-го отрезка (i= =1, 2, ..., n). Найти сумму длин окрашенной части прямой. П р а к т и ч е с к и й т у р Вариант 1 Задача 1. Форт имеет форму четырехугольника, и в его углах и серединах сторон находятся площадки, на которых могут располагаться солдаты. Составьте алгоритм, который помог бы полковнику расставить n солдат на этих площадках так, чтобы вдоль каждой стороны находи лось k солдат или сообщил, что это сделать невозможно. Задача 2. Два человека играют в такую игру: имеется поле M \N (M и N - нечетные), на которое игроки по очереди ставят по одному шахматному королю. Короля можно ставить на любую клетку, которая не занята и не находится под боем какого-либо короля, поставлен ного ранее любым из игроков. Игрок, который не сможет сделать оче редной ход, считается проигравшим. Написать программу, выступающую за игрока, имеющего выигрышную стратегию. Вариант 2 Задача 1. Кот Матроскин и пес Шарик поехали на рыбалку и решили наловить не менее N рыбок. За первый день они выловили по одной рыб ке. Но ночью кот проголодался и половину сьел. В последующие дни Ша рику удавалось вылавливать вдвое больше, чем в предыдущий день и еще две, а Матроскин вылавливал на 5 рыбок больше, но ночью кот сьедал столько рыбы, сколько за все предыдущие ночи и еще одну. Помогите дяде Федору составить алгоритм, с помощью которого он смог бы уз нать, когда ждать своих друзей домой с рыбалки. Задача 2. Составить программу получения двоичного кода любого целого десятичного числа X (0 <= X <= 255). Связь между десятичным числом X и его двоичным представлением a a a a a a a a описывает 7 6 5 4 3 2 1 0 ся следующей формулой: 7 6 5 1 0 X = a a a a a a a a = a G2 + a G2 + a G2 + ... + a G2 + a G2 7 6 5 4 3 2 1 O 7 6 5 1 0 (a = 0 или 1, i = O, 1, ..., 6, 7), например, 35 = ОО1ООО11. i