Задача 1.
В моем классе учится один парень - Ариф, который часто занимается на уроках математики в общем то математикой, но не совсем той, которой надо: то он выписывает в столбик квадраты всех чисел, то все степени двойки, то таблицу умножения до 100*100, короче говоря, наш Ариф - <кадр> еще тот. Недавно получил 2 за контрольную, потому что на всех предыдущих уроках занимался далеко не тем, чем надо. Однажды он придумал себе новое развлечение - стал выписывать в строку (без пробелов) четвертые степени всех простых чисел подряд. У него получилась примерно такая строка:
16816252401...
Потом ему стало интересно можно ли определить, какая цифра стоит на n-ом месте в этой строке? Формулу подобрать он не смог, да наверное ее и нету. Задача состоит в том, что несмотря на отсутствие формулы, определить, какая цифра стоит на n-ом месте.
Входные данные:
Во входном файле input.txt содержится единственное число n (0 < n < 25000).
Выходные данные:
В выходном файле output.txt содержится одна цифра, которая стоит в этой строке на n-ом месте.
Пример 1:
input.txt:
1
output.txt:
1
--------------
Пример 2:
input.txt
5
output.txt
6
-------------
Задача 2.
В некотором городе есть метро, состоящее из N (1 <= N <= 1000) станций и M линий, соединяющих их. Каждая линия обеспечивает проезд между какими-то двумя станциями в обе стороны. Между любой парой станций проведено не более одной линии. Сеть метро построена таким образом, чтобы с каждой станции можно было проехать на каждую (возможно, через промежуточные станции). Назовем это свойство связностью метро.
В связи с изобретением принципиально нового вида транспорта метро стало убыточным, и его работу решили прекратить. На заседании мэрии города было постановлено закрывать каждый год по одной станции, но так, чтобы связность метро каждый раз сохранялась. При закрытии какой-либо станции, линии, ведущие из этой станции в другие, естественно, тоже перестают функционировать.
Задание. По введенной информации о сети метро разработать какой-либо порядок закрытия станций, при котором метро всегда будет оставаться связным. Например, пусть метро выглядит так, как показано на рисунке. Тогда станции можно закрывать, например, в порядке 1, 2, 4, 3, 5. А порядок 3, 1, 2, 4, 5 - не подходит, так как после закрытия 3-й станции метро распадется на четыре не связных между собой части.
Ввод. Первая строка входного файла будет содержать числа N и M. В следующих M строках находится информация о линиях. Каждая из этих строк содержит через пробел числа Ai и Bi (Ai Bi) - две станции, которые соединяет i-я линия.
Вывод. Выходной файл должен состоять из N строк. Каждая строка должна содержать одно число - номер станции. Вывести станции нужно в порядке их закрытия.
Пример
input.txt
5 4
3 1
3 2
3 4
3 5
output.txt
1
2
4
3
5
Задача 3.
Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.
После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.
Формат входных данных
Первая строка входного файла содержит целое число N - количество сообщений в форуме
(1 <= N <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке.
Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.
Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения.
Длина всех сообщений не превышает 100 символов.
Формат выходных данных
Выведите в выходной файл название темы, к которой относится наибольшее количество сообщений. Если таких тем несколько, то выведите первую в хронологическом порядке.
Пример
forum.in
7
0
Олимпиада по информатике
Скоро третья командная олимпиада?
0
Новая компьютерная игра
Вышла новая крутая игра!
1
Она пройдет 24 ноября
1
В Санкт-Петербурге и Барнауле
2
Где найти?
4
Примет участие более 50 команд
6
Интересно, какие будут задачи
forum.out
Олимпиада по информатике