K-значное число (K ≤ 10) называется пестрым, если все его цифры различны. При этом ноль не может быть первой цифрой.
Написать программу, которая для заданного K:
Число вводится с клавиатуры
Результат должен быть выведен в файл с именем OUTPUT.TXT
.
Для каждой найденной цепочки выводится только первое число,
которое располагается в отдельной строке выходного файла.
Задача оценивается из 20 баллов. Время тестирования не более 1 минуты.
Рассматриваются два алгоритмических языка: 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 |
Ниже перечислены операторы языка Beta:
Название оператора | Форма записи оператора | Комментарии |
Оператор присваивания | Переменная=Выражение | Выражение - это арифметическое выражение, содержащее переменные, целочисленные константы, круглые скобки и знаки арифметических операций: +, -, *. Оператор присваивает переменной из левой части значение выражения. |
Оператор перехода | WALKTO метка | Оператор передает управление оператору, начинающемуся с указанной метки. Метка задается константой и не может содержать арифметических операций. |
Условный оператор | IF условие THEN оператор присваивания или оператор перехода | Условие - это два выражения, разделенные одним из знаков сравнения: "=", "<", ">", "<>" (не равно). Оператор проверяет условие, и, если оно истинно, то выполняется оператор, следующий за словом THEN в этой же строке. |
Оператор печати | TYPE Выражение | Оператор выводит с новой строки значение выражения. |
Оператор завершения | END | Всегда записывается последним оператором в программе и завершает ее исполнение. |
Ниже перечислены операторы языка Psi:
Название оператора | Форма записи оператора | Комментарии |
Оператор присваивания | Переменная:=Выражение | Оператор присваивает переменной из левой части значение выражения. |
Условный оператор | IF условие THEN оператор;...; оператор; FI | Оператор проверяет условие, и, если оно истинно, то выполняются операторы, находящиеся между словами THEN и FI. Между THEN и FI может находиться и один оператор. |
Оператор печати | PRINT (выражение) | Оператор выводит с новой строки значение выражения. |
Оператор цикла | WHILE Условие DO оператор;,...;оператор; OD | Повторяет выполнение операторов, находящихся между словами DO и OD, пока истинно условие. Между DO и OD может находиться и один оператор. |
Установка состоит из устройств A и B, соединенных между собой лежащими на земле шлангами. Каждое устройство имеет N патрубков, пронумерованных от 1 до N как изображено на рисунке. Каждый из шлангов соединяет патрубки обоих устройств с одинаковыми номерами. Шланги могут располагаться друг относительно друга произвольным образом с единственным ограничением: при перемещении точки вдоль любого шланга от А к В расстояние от нее до А только возрастает. Номер шланга совпадает с номером патрубка устройства A.
Для улучшения пропускной способности шлангов было решено провести переукладку шлангов так, чтобы сделать их непересекающимися (см. рисунок). Для этого обходчику поручили записать информацию о точках пересечений шлангов по направлению движения от устройства A к устройству B. Для каждого очередного пересечения обходчик записал пары чисел: номер шланга, лежащего снизу, и номер шланга, расположенного сверху, соответственно (в каждой точке пересекаются не более двух шлангов.
Написать программу, которая по заданным N (считать N ≤ 3) и произвольной последовательности пересечений шлангов определяла бы:
Входные данные располагаются в файле INPUT.TXT
.
В первой строке этого файла находится число, во второй -
записанные через пробел вышеназванные пары натуральных чисел.
Данные во входном файле всегда соответствуют описанному
формату файла INPUT.TXT
.
Для приведенного рисунка входные данные в файле
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
В городе открылся клуб филателистов, членами которого стремятся стать M человек. На каждом заседании в клуб принимают одного нового филателиста. Чтобы быть принятым, каждый претендент должен предъявить свою коллекцию марок, в которой нет одинаковых экземпляров и которая хоть чем-то отличается от коллекций членов клуба. Для этого каждый новый претендент идет в магазин, где продаются N видов почтовых марок (3 ≤ N ≤ 10000 по ценам X1 ≤ X2 ≤ ... ≤ 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.txt | output.txt |
5 10 3 4 6 10 15 | 3 4 6 7 9 10 10 13 14 15 |
N спичек (N ≤ 15) на плоскости образует фигуру как, например, изображено на рисунке:
Назовем фигуру B симметричной фигуре A, если существует такая ось симметрии, что отображая относительно ее исходную фигуру A, мы получим фигуру B. Очевидно, для любой заданной фигуры можно построить симметричную ей, переложив некоторые спички. В процессе перекладывания спички ломать нельзя. Накладывание спичек друг на друга не приводит к нарушению условия их расположения на плоскости. Например, из фигуры на вышеприведенном рисунке, могут быть получены фигуры, изображенные на следующих рисунках:
Написать программу, для определения симметричной фигуры, получающейся из исходной перекладыванием минимального количества спичек.
Исходное расположение спичек задается в файле с именем
INPUT.TXT
. Первая строка файла содержит
число N, далее следуют N строк,
содержащих координаты концов каждой спички:
(x1, y1);
(x2, y2).
Результат работы программы записывается в файл с именем
OUTPUT.TXT
, содержащий в первой строке
количество переложенных спичек, далее следуют N
строк с координатами концов спичек в результирующей фигуре.
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 |
Стена для состоит из M рядов по N одинаковых кирпичей в каждом. Каждый последующий ряд смещен относительно предыдущего на 1/2 кирпича (см. рисунок). Четные ряды сверху смещаются влево, а нечетные - вправо. Конфигурация из кирпичей является устойчивой, если каждый кирпич опирается, по крайней мере, на один кирпич в нижележащим ряду. Очевидно, что из заданной конструкции можно удалить некоторые кирпичи без потери ее устойчивости. На втором рисунке изображен пример возможной конструкции для стены на первом рисунке.
Написать программу, которая по заданным M и N (0 < M, N ≤ 1000) и находит конструкцию, получающуюся из исходной путем удаления по возможности максимального количества кирпичей, чтобы верхний ряд остался без изменения, а конструкция не потеряла устойчивость.
Входной файл с именем INPUT.TXT
содержит
количество рядов M и ширину стены N.
В выходной файл с именем OUTPUT.TXT
вывести
количество оставшихся кирпичей и конфигурацию стены.
Оставшиеся кирпичи перечисляются начиная с верхнего ряда,
слева направо в каждом ряду (нумерация в каждом ряду
начинается с единицы). Список кирпичей каждого ряда
должен заканчиваться числом 0. Все числа в выходном
файле должны разделяться пробелами и (или) символами
перевода строки.
input.txt | output.txt |
4 5 | 13 1 2 3 4 5 0 2 4 5 0 2 3 5 0 3 5 0 |