VIII Всероссийская олимпиада по информатике

тур 1

Задача 1. Пестрые числа

K-значное () число называется пестрым, если все его цифры различны. При этом ноль не может быть первой цифрой.

Требуется.

Написать программу, которая для заданного K:

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

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

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

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

Примечание.

Задача оценивается из 20 баллов.

Время тестирования программы - не более 1 мин.

Задача 2. Транслятор

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

Пример возможного перевода:

Программа на языке Beta

Одна из соответствующих ей
программ на языке Psi

10 N=5

20 SUM=SUM+N

35 N=N-1

40 IF N>0 THEN WALKTO 20

70 TYPE Sum

999 END

DEF N, Var, C;

START

Var := 0; c := 1;

WHILE c < 6 DO

IF c = 1 THEN N:= 5; c:=c+1; FI;

IF c = 2 THEN Var:=Var+N; c:=c+1;

FI;

IF c = 3 THEN N:=N-1; c := c+1; FI;

IF c = 4 THEN

IF N>0 THEN c := 1; FI; c:=c+1;

FI;

IF c = 5 THEN Print (Var);

c := c+1;

FI;

OD;

FINISH

Примечания

Текст исходной программы состоит не более, чем из 100 строк, а каждая строка содержит не более 80 символов.

В каждом из языков имена переменных не совпадают с ключевыми словами в операторах.

Текст исходной программы не содержит синтаксических ошибок.

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

Текст исходной прогаммы вводить из файла INPUT.TXT. Результат выводить в файл OUTPUT.TXT

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

Время тестирования программы ограничено.

Описание языка Beta

Программа на языке Beta состоит из последовательности операторов; каждый оператор располагается в отдельной строке и ему всегда предшествует метка (натуральное число ? 10000).

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

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

Исполнение программы начинается с первого оператора. Последним в тексте программы всегда является оператор END.

Значения переменных, константы и значения выражений в языке являются целочисленными и находятся в диапазоне от -32768 до 32767.

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

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

Операторы языка перечислены в таблице 1.

Таб.1

Название оператора

Форма записи
оператора

Комментарии

Оператор

присваивания

переменная =
выражение

Выражение - это арифметическое выражение, содержащее переменные, целочисленные константы, круглые скобки и знаки арифметических операций: +, -, *. Оператор присваивает переменной из левой части значение выражения.

Оператор перехода WALKTO метка

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

Условный оператор IF условие THEN оператор присваивания или оператор перехода

Условие - это два выражения, разделенные одним из знаков сравнения: =, <, >, <> (не равно). Оператор проверяет условие, и, если оно истинно, то выполняется оператор, следующий за словом THEN в этой же строке.

Оператор печати TYPE выражение

Оператор выводит с новой строки значение выражения.

Оператор завершения END

Всегда записывается последним оператором в программе и завершает ее исполнение.

Описание языка Psi

Программы на языке Psi состоит из описания переменных и тела программы.

Описание переменных начинается со слова DEF, за которым следуют имена всех переменных, используемых в программе. Переменные в списке разделяются запятыми и не могут повторяться, после последней переменной ставится символ ; (точка с запятой).

Тело программы состоит из последовательности операторов, заключенных между словами START и FINISH. Операторы разделяются символом ; (точка с запятой).

Понятия переменной, константы, выражения и условия совпадают с соответствующими понятиями в языке Beta.

Программа может содержать пустые строки и лишние разделительные пробелы.

Имена переменных, имена операторов, метки и константы записываются без пробелов. Переменные в начале работы программы принимают случайные значения.

Операторы языка Psi

Название операторов

Форма записи оператора

Комментарии

Оператор

присваивания

переменная := выражение

Оператор присваивает переменной из левой части значение выражения.

Условный оператор IF условие THEN оператор;...;
оператор;
FI

Оператор проверяет условие, и, если оно истинно, то выполняются операторы, находящиеся между словами THEN и FI. Между THEN и FI может находиться и один оператор.

Оператор печати

PRINT (выражение)

Выводит с новой строки значение выражения.

Оператор цикла WHILE условие DO
оператор;,...;оператор; OD

Повторяет выполнение операторов, находящихся между словами DO и OD, пока истинно условие. Между DO и OD может находиться и один оператор.

Задача 3. ШЛАНГИ

Установка состоит из устройств A и B, соединенных между собой лежащими на земле шлангами. Каждое устройство имеет N патрубков, пронумерованных от 1 до N как изображено на рис. 1. Каждый из шлангов соединяет патрубки обоих устройств с одинаковыми номерами. Шланги могут располагаться друг относительно друга произвольным образом с единственным ограничением: при перемещении точки вдоль любого шланга от А к В расстояние от нее до А только возрастает. Номер шланга совпадает с номером патрубка устройства A.

рис. A.

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

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

рис. 2.

Требуется

Написать программу, которая по заданным (считать) и произвольной последовательности пересечений шлангов определяла бы:

(а) нет ли заведомых ошибок в записи обходчика;

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

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

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

Данные во входном файле всегда соответствуют описанному формату файла INPUT.TXT.

Для рис.1 входные данные в файле INPUT.TXT имеют вид:

3

2 1 3 1 2 3 3 2 1 3 1 2

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

Результаты решения должны выводиться на экран монитора. При этом допустимы следующие сообщения:

(а) Uncorrect input data - при обнаружении заведомых ошибок в записи обходчика;

(б) Correct input data - при отсутствии заведомых ошибок в записи обходчика;

(в) Solvable - при возможности обеспечить непересечение шлангов;

(г) Unsolvable - при невозможности обеспечить непересечение шлангов.

Для приведенного выше примера файла INPUT.TXT программа должна выдать сообщения:

Correct input data

Unsolvable

Примечания

Задача оценивается из 40 баллов

Оценка осуществляется, исходя из двух уровней сложности: для N=2 и для N=3.

Время тестирования программы - не более 1 мин.

 

тур 2

Задача 4. Коллекции

В городе открылся клуб филателистов, членами которого стремятся стать M человек. На каждом заседании в клуб принимают одного нового филателиста. Чтобы быть принятым, каждый претендент должен предъявить свою коллекцию марок, в которой нет одинаковых экземпляров и которая хоть чем-то отличается от коллекций членов клуба. Для этого каждый новый претендент идет в магазин, где продаются видов почтовых марок () по ценам (, ), и покупает соответствующий набор марок, стараясь потратить минимальную сумму денег.

Например, при ассортименте из 5 марок по ценам 3, 4, 6, 10, 15 коллекционеры будут покупать их в представленном ниже порядке:

коллекционер

купленные марки

затраченная сумма денег

первый

первая

3

второй

вторая

4

третий

третья

6

четвертый

первая и вторая

3+4

пятый

первая и третья

3+6

шестой

четвертая

10

седьмой

вторая и третья

4+6

восьмой

первая, вторая и третья

3+4+6

девятый

первая и четвертая

3+10

десятый

вторая и четвертая

4+10

...

...

...

Требуется

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

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

Входные данные задаются в файле INPUT.TXT в следующем порядке: в первой строке - N, во второй - M, в последующих N строках указываются цены марок в неубывающем порядке.

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

Результат решения задачи записывается в файл с именем OUTPUT.TXT. Каждая из M строк этого файла содержит соответствующую искомую сумму затраченных денег для каждого коллекционера. Эти М сумм должны располагаться в неубывающем порядке.

Пример входного файла и соответствующего ему выходного файла приведен ниже:

INPUT.TXT

OUTPUT.TXT

5

10

3

4

6

10

15

3

4

6

7

9

10

10

13

13

14

Примечания:

1) - натуральные числа. ;

2) Тестирование задачи будет осуществляться автоматически, так что никаких отступлений от данного формата ввода/вывода быть не должно;

3) Время тестирования не более 30 сек;

4) Задача оценивается в 34 балла.

Задача 5. Детская игра со спичками

N спичек () на плоскости образует фигуру как, например, изображено на рис. 1

рис. 1

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

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

рис. 2 рис. 3

Требуется

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

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

Исходное расположение спичек задается в файле с именем INPUT.TXT. Первая строка файла содержит число N, далее следуют N строк, содержащих координаты концов каждой спички:

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

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

Например, для фигуры на рис.1 решением является фигура на рис. 2. Соответствующие им файлы INPUT.TXT и OUTPUT.TXT приведены ниже:

INPUT.TXT

OUTPUT.TXT

3

1 0 1 5

2 4 5 0

5 0 8 4

1

9 0 9 5

2 4 5 0

5 0 8 4

Примечание

  1. Заведомо известно, что координаты концов спичек исходной и результирующей фигуры - целые числа ()
  2. Время тестирования ограниченно 1 минутой.
  3. Задача оценивается в 33 балла.

Задача 6. Стена

Стена для рекламных щитов состоит из M рядов по N одинаковых кирпичей в каждом. Каждый последующий ряд смещен относительно предыдущего на 1/2 кирпича (см. рис. 1). Четные ряды сверху смещаются влево, а нечетные - вправо. Конфигурация из кирпичей является устойчивой, если каждый кирпич опирается, по крайней мере, на один кирпич в нижележащим ряду (кирпичи нижнего ряда лежат на земле). Очевидно, что из заданной конструкции можно удалить некоторые кирпичи без потери ее устойчивости. На рис. 2 изображен пример возможной конструкции для стены на рис. 1.

Требуется

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

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

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

Входной файл с именем INPUT.TXT содержит количество рядов M и ширину
стены N.

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

В выходной файл с именем OUTPUT.TXT вывести количество оставшихся кирпичей и конфигурацию стены. Оставшиеся кирпичи перечисляются начиная с верхнего ряда, слева направо в каждом ряду (нумерация в каждом ряду начинается с единицы). Список кирпичей каждого ряда должен заканчиваться числом 0. Все числа в выходном файле должны разделяться пробелами и (или) символами перевода строки.

Пример файла исходных данных INPUT.TXT для рис. 1:

4 5

 

рис. 1

Пример выходного файла OUTPUT.TXT см. рис. 2:

13

1 2 3 4 5 0

2 4 5 0

2 3 5 0

3 5 0

 

рис. 2

Примечание

Задача оценивается в 33 балла.

Программы, выдающие правильные, но не оптимальные решения также будут оцениваться.

Время тестирования ограничено 1 минутой.