ЗАДАЧИ IX ГОРОДСКОЙ ОЛИМПИАДЫ

ПО ИНФОРМАТИКЕ 1997-98 уч.года.


Участники и победители

Архив решений

Теоретический тур :

  1. Задача на системы счисления -2 балла
  2. Триггерная схема сложения двух чисел - 10 баллов
  3. Лабиринт-алфавит - 8 баллов
  4. Принцесса или тигр - 4 балла
  5. Задача на доказательство - 6 баллов
Практический тур :
  1. Определить длину периода десятичной записи дроби 1/n (n>1) - 8 баллов
  2. Сквэрворд - 6 баллов
  3. Слово - 12 баллов
  4. Взаимодействие веществ - 4 балла

Условия задач теоретического тура.


 
1. Чему равно 84 в десятичном представлении, если 8*8=54 ?

(2 балла)
2. Триггерная схема сложения двух чисел.
Триггер - это электронный прибор, который принимает и посылает электрические сигналы (импульсы).
Проследим, как будет работать триггер, если к нему подвести один за другим несколько электрических импульсов. Триггер может находиться в двух состояниях: в состоянии 0, либо  в состоянии 1. Пусть первоначально триггер находился в состоянии 0. После первого импульса триггер переключается в
состояние 1. При этом ответного импульса с триггера не поступает. После второго импульса триггер снова попадет в состояние 0. Однако при этом триггер подаст ответный импульс. Последовательно соединенная цепочка триггеров “считает” поданные извне сигналы и своеобразным образом “записывает” число этих сигналов, причем в двоичной системе. Триггерные схемы позволяют также производить действия над числами.
Предлагается составить триггерную схему, которая бы позволяла осуществить сложение двух чисел.
 
                      - первое слагаемое
 
                      - второе слагаемое
 
     - сумма
Стрелочками укажите необходимый порядок соединения триггеров.
Триггеры, соответствующие сумме, имеют исходное состояние 0. Каждый триггер слагаемых находятся в состоянии 1 или 0. Инициализация операции сложения происходит при поступлении импульсов на  триггеры слагаемых (на каждый триггер поступает только по одному импульсу). Одновременная подача нескольких сигналов на триггер не допускается, что обеспечивается специальной задержкой.
(10 баллов)
3. Лабиринт-алфавит.
Во все 64 клеточки квадрата 8 на 8 вписаны все буквы русского алфавита с повторениями и в беспорядке. Сформулируйте положения, руководствуясь которыми можно было бы провести не самопересекающуюся ломанную, начиная с буквы А в верхнем левом углу , которая проходила бы ровно через 33 буквы алфавита
(без повторений и необязательно по порядку) и заканчивалась в нижнем правом углу квадрата на букве Я.
При этом ломанная должна пересекать стороны клеток, но не проходить через их вершины.
Рекомендуется букву, через которую проходит ломанная, называть включенной, а через которую
не проходит - не включенной.
(8 баллов)
4. Принцесса или тигр.
     В одном королевстве всякому узнику, осужденному на смерть, давали последний шанс выкарабкаться. Предлагалось угадать, в какой из двух комнат находится тигр, а в какой - принцесса. Если узник укажет на одну комнату, то  его (вполне возможно) растерзает тигр, но если на другую - то  достанется принцесса. Причем может оказаться, что в обеих комнатах находятся принцессы или в обеих комнатах сидят тигры. Тогда в первом случае узнику очень повезло, чего нельзя сказать о втором случае.
     Кроме того, король решил на дверях каждой комнаты повесить по табличке, а заключенному кое-что сказать о них. Если на плечах у него голова, способная рассуждать логически, он сумеет сохранить себе жизнь и в придачу получить прелестную невесту. А если носит под шляпой качан капусты, его откусит тигр... Необходимо определить в какой комнате находится принцесса в каждом из приведенных ниже случаях.
Случай первый:
 
1. В этой комнате находится принцесса, кроме того в одной из комнат сидит тигр 2. В одной из комнат находится принцесса, а в другой комнате сидит тигр
 
Известно, что на одной табличке точно правда, а на другой - нет.
Случай второй:
 
1. По крайней мере в одной из этих комнат находится принцесса 2. Тигр сидит в другой комнате
 
Может, обе таблички чистую правду говорят, а может, обе лгут напропалую.
Случай третий:
 
1. В обеих комнатах находятся принцессы 2. В обеих комнатах находятся принцессы
 
Если в первой комнате находится принцесса, то утверждение на табличке истинно, если же тигр, то ложно. Во второй же комнате все наоборот: утверждение на табличке ложно, если в комнате находится принцесса, и истинно, если в комнате сидит тигр.
Случай четвертый:
Узнику были предложены на выбор три комнаты, в одной из которых находилась принцесса, а в двух других сидели тигры.
 
1. Тигр сидит в комнате 2. 2.Тигр сидит в этой комнате 3. Тигр сидит в комнате 1.
 
Табличка на двери, за которой находится принцесса говорит правду, а из двух других надписей по меньшей мере одна является ошибочной.
(4 балла)
5. Задана таблица чисел. Алгоритм на каждом шаге выбирает в этой таблице строку (или столбец), сумма элементов которой (или которого) меньше нуля, и умножает все эти элементы на (-1).Алгоритм работает до тех пор, пока такие строки (столбцы) встречаются. Доказать, что алгоритм не может работать бесконечно долго.   (6 баллов)

Условия задач практического тура.


 
1. Дано натуральное число n>1. Написать программу, которая бы определяла длину периода десятичной записи дроби 1/n.

(8 баллов)
2. Сквэрворд. Дан квадрат, разделенный на клеточки, с записанными в нем определенным образом словами (в одной клеточке хранится только одна буква). При этом большая часть клеточек пуста.

Задача состоит в том, чтобы написать программу заполнения этих пустых клеточек буквами из числа имеющихся так, чтобы в каждом горизонтальном, вертикальном ряду и в диагоналях квадрата не было бы двух одинаковых букв, т.е. каждая буква встречалась бы по одному разу.
Ввод содержимого клеточек исходного квадрата производить построчно. Если в клеточке нет буквы, то вводить “пробел”. Результат работы программы - вывод на экран заполненного  буквами квадрата :
 

  исходный                             заполненный
 
с  л  е  з  а    с  л  е  з  а 
            а  е  з  с  л 

  л  е  с    з  а  л  е  с 
            л  з  с  а  е 
            е  с  а  л  з 

(6 баллов)
3. Слово. Задается некоторое слово. Из всех его букв составляются различные другие слова, возможно, бессмысленные. Написать программу, которая по заданному слову из этого набора строит следующее за ним по алфавиту слово из этого же набора.
(12 баллов)
4. Взаимодействие веществ. Задано N веществ и таблица их взаимодействий, т.е. a[i,j]=0, если i-ое вещество не взаимодействует с j-ым веществом  и a[i,j]=k, (1<=i, j, k<=N), если при их взаимодействии получается k-ое вещество. В пробирку одно за другим засыпаются вещества. Оказавшись рядом, они могут вступить в реакцию. Вновь образованное вещество, возможно, реагирует с ниже лежащим и т.д. Известно, что реакция взаимодействия происходит только между двумя соседними слоями. Составьте программу, определяющую по заданной последовательности какие вещества окажутся в пробирке.
(4 балла)

 
 
Члены жюри : Алешина А.А.(председатель жюри), Сузи Р.А., Дуплихин М.Ю., Дьяконов М.В.,
Леонтьев А.А., Кириленко А. Н.
 
Председатель оргкомитета : Рузанова Н. С.
В начало данной страницы                       На начальную страницу