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

Троицк, 1996 год

Задачи

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

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

Требуется

Написать программу, которая для заданного 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
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
            

Примечания

  1. Текст исходной программы состоит не более, чем из 100 строк, а каждая строка содержит не более 80 символов.
  2. Текст исходной программы не содержит синтаксических ошибок.
  3. Программы на языке Psi, содержащие синтаксические ошибки, на соответствие исходной программе проверяться не будут.
  4. Задача оценивается из 40 баллов. Решения задачи для случая, когда в исходной программе отсутствуют операторы WALKTO, также будут оцениваться.
  5. Время тестирования программы ограничено.

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

Ниже перечислены операторы языка Beta:
Название оператора Форма записи оператора Комментарии
Оператор присваивания Переменная=Выражение Выражение - это арифметическое выражение, содержащее переменные, целочисленные константы, круглые скобки и знаки арифметических операций: +, -, *. Оператор присваивает переменной из левой части значение выражения.
Оператор перехода WALKTO метка Оператор передает управление оператору, начинающемуся с указанной метки. Метка задается константой и не может содержать арифметических операций.
Условный оператор IF условие THEN оператор присваивания или оператор перехода Условие - это два выражения, разделенные одним из знаков сравнения: "=", "<", ">", "<>" (не равно). Оператор проверяет условие, и, если оно истинно, то выполняется оператор, следующий за словом THEN в этой же строке.
Оператор печати TYPE Выражение Оператор выводит с новой строки значение выражения.
Оператор завершения END Всегда записывается последним оператором в программе и завершает ее исполнение.

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

Ниже перечислены операторы языка Psi:
Название оператора Форма записи оператора Комментарии
Оператор присваивания Переменная:=Выражение Оператор присваивает переменной из левой части значение выражения.
Условный оператор IF условие THEN оператор;...; оператор; FI Оператор проверяет условие, и, если оно истинно, то выполняются операторы, находящиеся между словами THEN и FI. Между THEN и FI может находиться и один оператор.
Оператор печати PRINT (выражение) Оператор выводит с новой строки значение выражения.
Оператор цикла WHILE Условие DO оператор;,...;оператор; OD Повторяет выполнение операторов, находящихся между словами DO и OD, пока истинно условие. Между DO и OD может находиться и один оператор.

Задача 3. Шланги

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

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

Требуется

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

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

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

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

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

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

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

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

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

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

Correct input data
Unsolvable

Примечания

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

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

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

Требуется

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

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

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

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

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

Пример

input.txtoutput.txt
5 
10 
3 
4 
6 
10 
15
3
4 
6 
7 
9 
10 
10 
13 
14 
15

Примечания

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

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

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

Требуется

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

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

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

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

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

Пример

input.txtoutput.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

Примечания

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

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

Требуется

Написать программу, которая по заданным M и N (0 < M, N ≤ 1000) и находит конструкцию, получающуюся из исходной путем удаления по возможности максимального количества кирпичей, чтобы верхний ряд остался без изменения, а конструкция не потеряла устойчивость.

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

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

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

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

Пример

input.txtoutput.txt
4 5
13
1 2 3 4 5 0
2 4 5 0
2 3 5 0
3 5 0

Примечания