Пестрые числа
	Авторы: С.Волченков (г.Ярославль)

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

Требуется

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

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

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

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

Примечания

Задача оценивается из 20 баллов. Время тестирования не более 1 минуты.

	Транслятор
	Авторы: А.Суханов (С.-Петербург), E.Андреева (Москва)

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

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

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 состоит из последовательности операторов; каждый оператор располагается в отдельной строке и ему всегда предшествует метка (натуральное число < = 10000).
• Все метки различны и упорядочены по возрастанию, оператор отделяется от метки пробелами.
• Имя переменной состоит из одной или нескольких латинских букв (не более 8 букв), большие и маленькие буквы неразличимы. Имена переменных не могут совпадать с ключевыми словами, из которых строятся операторы.
• Исполнение программы начинается с первого оператора.
• Последним в тексте программы всегда является оператор END.
• Значения переменных, константы и значения выражений в языке являются целочисленными и находятся в диапазоне от -32768 до 32767.
• В начале работы программы значения всех переменных равны нулю.
• Программа может содержать лишние разделительные пробелы. Имена переменных, имена операторов, метки и константы записываются без пробелов.
• Текст программы не содержит пустых строк.

Ниже перечислены операторы языка Beta:

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

• Программы на языке Psi состоит из описания переменных и тела программы.
• Описание переменных начинается со слова DEF, за которым следуют имена всех переменных, используемых в программе. Переменные в списке разделяются запятыми и не могут повторяться, после последней переменной ставится символ ; (точка с запятой).
• Тело программы состоит из последовательности операторов, заключенных между словами START и FINISH.
• Операторы разделяются символом ; (точка с запятой).
• Понятия переменной, константы, выражения и условия совпадают с соответствующими понятиями в языке Beta.
• Программа может содержать пустые строки и лишние разделительные пробелы.
• Имена переменных, имена операторов, метки и константы записываются без пробелов. Имена переменных не могут совпадать с ключевыми словами, из которых строятся операторы.
• Переменные в начале работы программы принимают случайные значения.

Ниже перечислены операторы языка Psi:

	Шланги
	Авторы: В.Прохоров

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

рис.1

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

рис.2

Требуется

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

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

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

Входные данные располагаются в файле 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 мин.

	Коллекции
	Авторы: Р.Прохоров

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

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

Требуется

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

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

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

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

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

INPUT.TXT:

5 10 3 4 6 10 15  

OUTPUT.TXT:

3 4 6 7 9 10 10 13 14 15

Примечания:

1. N, M, Xi - натуральные числа, N< =M< =2**N-1, M< =15000;
2. Тестирование задачи будет осуществляться автоматически, так что никаких отступлений от данного формата ввода/вывода быть не должно;
3. Время тестирования не более 30 сек;
4. Задача оценивается в 34 балла.

	Детская игра со спичками
	Авторы: А.Овсянников, Т.Овсянникова

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

рис.1

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

рис.2	рис.3

Требуется

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

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

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

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

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

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

INPUT.TXT:

3
1 0 1 5
2 4 5 0
5 0 8 4

OUTPUT.TXT

1
9 0 9 5
2 4 5 0
5 0 8 4

Примечания

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

	Стена
	Авторы: А.Суханов (С.-Петербург), E.Андреева (Москва)

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

Требуется

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

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

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

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

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

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

4 5

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

13
1 2 3 4 5 0
2 4 5 0
2 3 5 0
3 5 0

рис.1	рис.2

Примечания

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