Задачи личного первенства УрГУ - 2000

Ограничения времени 5 секунд на каждый тест. Входной файл всегда input.txt, выходной файл - output.txt. В строках входных файлов отсутствуют ведущие и концевые пробелы, (кроме последней задачи), размеры входного и правильного выходного файла не будут превышать 500кБ. Первый тест совпадает с примером к задаче.

Задача A. Проблемы массовой информации. Пусть среди студентов УрГУ есть N программистов, которые никогда не читают объявлений и не смотрят новости на сервере acm.usu.ru. Назовем таких программистов ленивыми. Ленивые программисты всегда обмениваются новостями со своими знакомыми ленивыми программистами и не общаются ни с кем другим. Стас Васильев хочет, чтобы все они узнали о готовящемся личном первенстве по программированию. Ему известно, кто с кем знаком и, разумеется, не хочется бегать за каждым ленивым программистом отдельно.

В первой строке файла input.txt содержится число N (1 <= N <= 1000) - число ленивых программистов. Далее следуют N строк, в i-той строке через пробел перечислены номера знакомых i-того ленивого программиста. Все знакомства взаимны. Если знакомых нет, то строка будет пустой. Вывести в файл output.txt единственное число - минимальное количество ленивых программистов, которым Стас Васильев должен сообщить информацию о готовящемся первенстве.

Пример файла input.txt

6
3 5
3 6 5
1 2

2 1
2

Пример файла output.txt

2

Задача B. Инверсия последовательности.

Назовем инверсией последовательности чисел a₁, ... ,a_N последовательность чисел b₁, ... ,b_N, где b_i = | { j | j < i, a_j > a_i } |, т.е., каждое число b_i из новой последовательности равно количеству чисел старой последовательности, которые больше чем a_i, но имеют меньший номер (стоят перед a_i).

В файле input.txt содержится N (1 <= N <= 1000) чисел, являющихся инверсией некоторой перестановки отрезка ряда натуральных чисел от 1 до N. Вывести в файл output.txt исходную перестановку. Числа во входном файле разделены пробелами, ввод корректен, т.е. искомая перестановка существует. Если искомых перестановок несколько, то достаточно вывести любую из них.

Пример файла input.txt

0 1 2 0 1

Пример файла output.txt

3 2 1 5 4
 

Задача C. Улитка. Дана таблица размером N*N, где N - нечетное число не больше 199, клетки которой заполнены натуральными числами в естественном порядке, т.е. в верхнем левом углу стоит число 1, правее 2, еще правее 3 и так далее до конца первой строки. Во второй строке сначала стоит число N+1, далее N+2, в правом нижнем углу матрицы стоит число N*N. Требуется вывести элементы этой матрицы в следующем порядке: сначала центральный элемент, затем тот, который стоит над центральным, затем элемент слева и сверху от центрального, и далее все остальные элементы матрицы по раскручивающейся спирали (против часовой стрелки). В случае матрицы размером 5*5 порядок обхода (и, соответственно, вывода) элементов матрицы изображен на рисунке:

13 12 11 10 25
14 3  2  9  24
15 4  1  8  23
16 5  6  7  22
17 18 19 20 21

В файле input.txt содержится положительное нечетное число N (1 <= N <= 199). Вывести в файл output.txt элементы таблицы в указанном порядке, разделяя их одним пробелом.

Пример файла input.txt

3

Пример файла output.txt

5 2 1 4 7 8 9 6 3

Задача D. Сумма цифр.

Даны два натуральных числа b и k, 1 < b <= 10, 1 <= k < 10. Требуется найти сумму всех цифр, используемых при записи в b-ичной системе счисления всех натуральных чисел от 1 до b^k включительно.

В первой строке файла input.txt находится число b, во второй - число k.

В файл output.txt требуется вывести единственное число, представляющее собой десятичную запись искомой суммы.

Пример файла input.txt

3
2

Пример файла output.txt

19

Задача E. Ближайшее простое число.

В файле input.txt содержится одно натуральное число не больше 10000. Вывести в файл output.txt простое число, ближайшее к заданному (возможно, оно само). Если таких чисел несколько, то вывести меньшее.

Пример файла input.txt

9

Пример файла output.txt

7

Задача F. Преобразование последовательностей.

Дана последовательность из N (1 <= N <= 16000) натуральных чисел. Каждое число в последовательности не превосходит 10000. Требуется заменить каждый элемент последовательности x другим элементом y из этой же последовательности так, чтобы выполнялись условия:

а) y находится в последовательности после x;

б) y > x;

в) среди всех элементов, удовлетворяющих первым двум условиям разность номеров y и x минимальна. Если для какого-то элемента x не находится ни одного элемента, удовлетворяющего условиям а) и б), то элемент x следует заменить на 0.

В первой строке файла input.txt находится число N, затем идут члены последовательности по одному в строке.

Вывести в файл output.txt все члены преобразованной последовательности по одному в строке.

 

Пример файла input.txt

7
3
1
1
5
6
3
4

Пример файла output.txt

5
5
5
6
0
4
0

Задача G. Форматирование текста.

Некий программист старой закалки набирает свои письма прямо в редакторе Norton Commander'а. При этом он не смотрит на экран, а просто набивает текст, время от времени нажимая клавишу <Enter> между словами.

В результате он получает текстовый файл (письмо) где каждая строка может иметь длину от 1 до 500 символов, и число строчек не более 1000. В письме содержатся слова (состоящие из символов от A до Z и от a до z, точек и запятых) разделенные одним, или несколькими пробелами. Длина слова не превосходит 30 символов.

Кроме того, он любит вставлять (иногда даже вместо пробела) следующие 4 символа:

":" ")" "(" "-".

Других символов в письме нет.

Чтобы письмо выглядело прилично (по его понятиям) в окне почтового клиента, в нем не должно быть строк длиннее, чем 72 символа и, разумеется, не содержать выше перечисленных четырех символов. Вам необходимо написать программу, которая преобразует письмо программиста в приличный (по его понятиям) вид. А именно:

1. Каждая строка должна быть длиной не более чем в 72 символа (символы конца строки не учитываются)
2. Строки не начинаются и не заканчиваются пробелом.
3. Каждая строка должна содержать максимально возможное число слов.
4. Все слова в строке должны быть разделены одним пробелом.

Пример файла input.txt

Example.
 Very
  important
 letter  :-).  A word :)is the maximal sequence  of Latin - letters,
 points and commas, which -contains neither )spaces nor any other -)of the
 mentioned above four symbols. A length  of each      line ()(should not exceed 
::seventy two symbols (excluding the    :---()symbol of 
end of line). No line should start or end with a space. 
Each( line should :)(contain a :maximal -- number of(- words. 
Words  should  :(be) separated with (one) (space). We:)need.your:(help.

Пример файла output.txt

Example. Very important letter . A word is the maximal sequence of Latin
letters, points and commas, which contains neither spaces nor any other
of the mentioned above four symbols. A length of each line should not
exceed seventy two symbols excluding the symbol of end of line. No line
should start or end with a space. Each line should contain a maximal
number of words. Words should be separated with one space . We need.your
help.