ВУЗ:
Составители:
Рубрика:
1 0 0 0 0 0
1 1 1 1 1 1
Задача 5 (6 баллов)
Машиной с неограниченным числом регистров (МНР) называется гипотетическое устройство, состоящее из бесконеч-
ного числа регистров (ячеек), в которые можно записывать целые числа. МНР – алгоритмы записываются с помощью сле-
дующих четырех команд:
Z(n) – запись в n-й регистр;
S(n) – увеличение содержимого n-го регистра на 1;
T(m,n) – копирование m-го регистра в n-ый регистр;
J(m,n,k) – переход к команде с номером k, если содержимое m-го и n-го регистров совпадает. В противном случае пе-
реход на следующую команду.
МНР–программа – это последовательность команд перечисленных выше типов.
Предполагаем:
а) перед началом программы задана начальная конфигурация регистров (начальные значения регистров);
б) результат программы помещается в регистр с номером 1;
в) программа останавливается при переходе к команде, номер которой больше номера последней команды;
г) после выполнения команд Z(n), S(n), T(m,n) осуществляется переход к следующей команде.
Определить значение, вычисляемое данным алгоритмом.
Входной файл INPUT.TXT содержит:
а) число регистров, используемых МНР – программой;
б) массив целых чисел – начальные значения регистров;
в) МНР – программу, т.е. последовательность команд.
Выходной файл OUTPUT.TXT:
содержит число – значение первого регистра.
П р и м е р
Входной файл INPUT.TXT
3
2 0 0
J(1,2,4)
S(2)
T(2,1)
Выходной файл OUTPUT.TXT:
1
Задача 6 (4 балла)
Телефонный номер называется "шахматным", если его цифры набираются на телефонном кнопочном номеронабирателе
ходом шахматного коня. Написать программу, подсчитывающую, сколько можно набрать различных семизначных "шахмат-
ных" номеров, начинающихся с заданной цифры:
1 2 3
4 5 6
7 8 9
0
Технические требования:
Входной файл: INPUT.TXT содержит число [0..9].
Выходной файл: OUTPUT.TXT должен содержать единственное число – решение задачи.
Задача 7 (5 баллов) ("Минимальное покрытие")
Среди заданного множества отрезков прямой с целочисленными координатами концов [Li, Ri] необходимо выбрать
подмножество наименьшей мощности, целиком покрывающее отрезок [0, M], где М – натуральное число.
Ограничения: 1≤М≤5000; |Li|, |Ri|≤5000; I≤10000.
В первой строке входного файла INPUT.TXT указана константа М. В последующих строках перечислены пары чисел (L
i
,
R
i
), каждая пара чисел начинается с новой строки. Числа в парах отделены друг от друга одним или несколькими пробелами. Спи-
сок завершается парой чисел (0, 0).
Программа должна формировать в первой строке выходного файла OUTPUT.TXT требуемое минимальное число отрез-
ков из исходного множества, необходимое для покрытия отрезка [0, M]. Далее должен следовать список покрывающего
подмножества, упорядоченного по возрастанию координат левых концов отрезка. Список отрезков выводится в том же фор-
мате, что и во входном файле INPUT.TXT, завершающую пару (0, 0) выводить не следует.
Если покрытие отрезка (0, M) исходным множеством отрезков (L
i
, R
i
) невозможно, то файл OUTPUT.TXT должен со-
держать единственную фразу "No solution".
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »