ОЧНЫЙ ТУР ЛИЧНОГО ПЕРВЕНСТВА СТУДЕНТОВ УНИВЕРСИТЕТА ПО ПРОГРАММИРОВАНИЮ, 2000 ГОД.
Во всех задачах ввод данных производится из файла INPUT.TXT, а вывод результатов – в файл OUTPUT.TXT. Формат входного файла соответствует спецификации, дополнительные проверки не нужны. Строка – это последовательность из 0 или более символов, заканчивающаяся символом перехода на новую строку. Время на выполнение одного теста во всех программах – 5 секунд (для тестирующего компьютера жюри P-100МГц).
1. What’s Difference?
Сэм Боди, постоянный участник соревнований, проходящих на сайте
http://acm.fi.uva.es/problemset/, решил сравнить свои достижения с результатами другого участника: какие задачи удалось решить ему, а другой не решил, и наоборот. Для этого Сэм получил список номеров задач, которые удалось решить ему, и аналогичный список номеров для другого участника и решил писать программу, которая наглядно выведет разницу между двумя списками. Номера задач, которые встречаются в обоих списках, Сэм решил не выводить, номера задач, имеющихся только у него, выводить со знаком + (плюс), а отсутствующие у него – со знаком – (минус).Во входном файле в первой строке содержатся два числа
: N (1<=N<=1000) – число задач, решенных Сэмом, и M (1<=M<=1000) – число задач, решенных его соперником. Во второй строке находится N натуральных чисел, не превосходящих 1000 (номера решенных задач), в порядке возрастания. В третьей строке находится M натуральных чисел, не превосходящих 1000, в порядке возрастания.В выходной файл вывести разницу между списками, каждый номер задачи на отдельной строке. Номера задач должны идти по возрастанию, перед каждым номером должен стоять знак + или –. Если разницы нет, то должен быть создан пустой файл.
Пример INPUT.TXT:
OUTPUT.TXT для примера
:2. Intel-Cycle-List
Для работы с “циклическим” списком из N целых чисел имеются две операции. Операция Top переставляет первый элемент списка в конец списка, а операция Bottom переставляет последний элемент списка в начало списка. В некоторой программе всегда выполняется сначала K операций Top, а затем L операций Bottom, потом снова K операций Top, затем L операций Bottom, и так далее. Так как число выполняемых операций над списком в данной программе может быть достаточно большим, то применение стандартных подпрограмм приведет к неэффективному расходу машинного времени. К счастью, в данном случае существует достаточно простой способ ускорить определение по числу выполненных операций конечного состояния списка. Напишите программу, которая для заданного списка, K и L определяет состояние списка после X выполненных операций.
Во входном файле в первой строке содержатся натуральные числа
N, K и L (1<=N,K,L<=100). Во второй строке содержится N целых чисел (начальное состояние списка), все числа по модулю не превышают 10000. В третьей строке содержится число X (0<=X<=2000000000).В выходной файл вывести список после выполнения
X операций, разделяя числа одним пробелом.Пример INPUT.TXT:
OUTPUT.TXT для примера
:5 1 2 3 4
3. Мелом расчерчен асфальт на квадратики
Сколько различных прямоугольников можно насчитать в прямоугольнике из n на m клеток? Например в прямоугольнике 5x5 можно найти 225 различных прямоугольников (25 прямоугольников 1x1, ..., 8 прямоугольников 4x5 и 1 прямоугольник 5x5).
Во входном файле в первой строке содержатся два натуральных числа n и m (1<=n,m<=1000).
В выходной файл вывести число прямоугольников.
Пример INPUT.TXT:
OUTPUT.TXT для примера
:4. Домино на шахматной доске
Предположим, что у нас имеется шахматная доска и достаточное количество косточек домино, каждая величиной в две клетки доски (1x2).
Поставим две пешки на противоположные угловые поля. Можно ли оставшуюся часть доски покрыть косточками домино, так чтобы ни одна косточка не вылезала за пределы доски и косточки не накладывались друг на друга? (Правильный ответ: нет.)Напишите программу, которая для любого количества и расположения пешек определяет число способов замощения доски косточками домино.
Во входном файле содержится 8 строк, в каждой строке по 8 символов. Свободная клетка обозначается символом
‘.’ (точка), а занятая пешкой – символом ‘#’. Число пешек на доске не превышает 63.В выходной файл вывести число различных способов замощения доски косточками домино. Так как шахматная доска имеет обозначения горизонталей и вертикалей, то различными являются и варианты, переходящие в друг друга при поворотах и зеркальном отражении.
Пример INPUT.TXT:
OUTPUT.TXT для примера
:Пример INPUT.TXT:
OUTPUT.TXT для примера
:5. НОД
Числа, состоящие из одинаковых цифр, будем задавать, указывая число цифр и повторяющуюся цифру. Например, вместо 3333333333, будем писать 10#3. Напишите программу, которая вводит два числа из повторяющихся цифр и определяет их наибольший общий делитель (НОД).
Во входном файле содержатся две строки, в каждой строке – по одному числу из повторяющихся цифр, заданных в форме n#c (1<=n<=1000, 1<=c<=9).
В выходной файл вывести НОД этих двух чисел в обычной форме.
Пример INPUT.TXT:
OUTPUT.TXT для примера
:6. English-Number Translator (ACM486)
In this problem, you will be given one or more integers in English. Your task is to translate these numbers into their integer representation. The numbers can range from negative 999,999,999 to positive 999,999,999. The following is an exhaustive list of English words that your program must account for: negative, zero, one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand, million.
Input and Output
Notes on input:
The answers are expected to be on separate lines with a newline after each.
Sample INPUT.TXT
Sample OUTPUT.TXT