Задачи

Задача А. Код Прюфера

Пусть имеется дерево (т.е. связный граф без циклов) с N вершинами (1Ваша задача - по заданному коду Прюфера восстановить дерево, т.е. найти списки смежности для каждой из вершин.

Вход: На входе программе дается набор чисел, соответствующий коду Прюфера некоторого дерева. Числа разделены пробелами.

Выход: На выходе программа должна построить списки смежности вершин восстановленного по коду графа. Списки смежности для вершин выводятся в порядке номеров вершин. Список смежности вершины должен иметь следующий формат: номер вершины, двоеточие, пробел, и далее номера смежных вершин через пробел. Вершины в списке должны быть отсортированы по возрастанию номеров.

Пример входного файла:
2 1 6 2 6

Пример выходного файла:
1: 4 6
2: 3 5 6
3: 2
4: 1
5: 2
6: 1 2

Задача B. Местное время.

Вскоре команда УрГУ отправится в Ванкувер на финал студенческого командного чемпионата мира по программированию. От Екатеринбурга до Ванкувера им придется лететь на четырех разных самолетах!

Кстати, наша команда собирается вернуться из Ванкувера обратно, поэтому имеются билеты в обе стороны. На билетах указаны время вылета (местное время аэропорта, откуда вылетает самолет) и время прибытия (местное время аэропорта, куда прилетает самолет). Например, прямой рейс вылетает в 15.42 и прилетает в 16.23, а обратный рейс вылетает в 08.10 и прилетает в 17.51.

Ваша задача - помочь нашей команде узнать, насколько же отличается время в первом аэропорту, от времени во втором. Известно, что время в разных аэропортах отличается на целое число часов, и продолжительности полетов туда и обратно отличаются друг от друга не более чем на 10 минут.

Длительность любого полета не превосходит 6 часов, разность между временем аэропортов не больше 5 часов.

Вход: во входном файле содержится две строки. В первой строке указаны время вылета и время прилета прямого рейса, а во второй - время вылета и время прилета обратного рейса. Время вылета и время прилета разделены пробелом, минуты отделены от часов точкой.

Выход: в выходной файл надо вывести неотрицательное целое число, которое показывает, насколько время первого аэропорта отличается от времени второго аэропорта.

Пример входного файла:
23.42 01.14
08.10 17.51

Пример выходного файла:
4

Задача C. Никифор - 2.

Никифору в подарок досталось число x. Но оно ему не нужно, а нужно число y. Но Никифор не расстроился: он решил попробовать получить y, вычеркивая из числа x некоторые цифры. Но что-то не очень-то у него получается. Может быть, ему нужно правильно выбрать систему счисления, в которой это возможно?

Напишите программу, которая считывает два натуральных числа x и y и определяет минимальное основание системы счисления, в которой число y можно получить из числа x вычеркиванием некоторого набора цифр. Если это невозможно, программа должна выдавать сообщение "No solution".

Вход: единственная строка входного файла содержит два числа x и y, разделенные пробелом. Известно, что 1 <= y < x <= 1000000.

Выход: Единственная строка выходного файла содержит либо сообщение "No solution", если необходимого основания системы счисления не существует, либо натуральное число, не меньшее 2, являющееся ответом задачи.

Пример входного файла 1:
127 16

Пример выходного файла 1:
3

Пример входного файла 2:
7 4

Пример выходного файла 2:
No solution

Задача D. Маршрутизация.

Имеется сеть из нескольких компьютеров, с настроенной по правилам TCP/IP маршрутизацией. Это означает, что:

1. Каждый компьютер имеет 1 или более сетевых интерфейсов,
2. Каждый интерфейс идентифицируется IP-адресом и маской подсети - это два 4-х байтных числа, разделенные точками через каждый байт, причем в двоичном представлении маска подсети выглядит следующим образом: сначала идет k единиц, потом m нулей, k+m=8*4=32. (Например 212.220.35.77 - IP-адрес, 255.255.255.128 - маска).
3. 2 компьютера относятся к одной подсети, если (IP₁ AND NetMask₁) = (IP₂ AND NetMask₂), где IP_i и NetMask_i - IP-адрес и маска i-го компьютера, AND - побитовое умножение.
4. Пакет между компьютерами, находящими в одной подсети передается непосредственно.
5. Пакет между компьютерами, находящимися в 2-х разных подсетях, проходит через компьютеры, имеющий интерфейсы, подключенные к нескольким подсетям, причем при переходе из подсети в подсеть, компьютер, на котором осуществляется этот переход, должен иметь интерфейсы, относящиеся к обеим подсетям.

Задача состоит в том, чтобы найти кратчайший путь пакета между двумя указанными компьютерами.

Ввод: во входном файле в первой строке стоит число N (N<=90) - количество компьютеров в сети, далее идет N секций, описывающих интерфейсы каждого компьютера. В первой строке секции стоит число K (K<=5) - количество интерфейсов этого компьютера, затем K строк - это описания интерфейсов, т.е. его IP-адрес и маска подсети. В последней строке файла стоят два числа - номера компьютеров между которыми надо найти путь.

Вывод: слово Yes если путь существует, затем в следующей строке через пробел номера компьютеров, через которые проходит путь. Или слово No, если такого пути не существует.

Пример входного файла:
6
2
10.0.0.1 255.0.0.0
192.168.0.1 255.255.255.0
1
10.0.0.2 255.0.0.0
3
192.168.0.2 255.255.255.0
212.220.31.1 255.255.255.0
212.220.35.1 255.255.255.0
1
212.220.31.2 255.255.255.0
2
212.220.35.2 255.255.255.0
195.38.54.65 255.255.255.224
1
195.38.54.94 255.255.255.224
1 6

Пример выходного файла:
Yes
1 3 5 6

Задача E. Квадратная проблема. (Автор - С.Н. Васильев)

В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a² квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок.

Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1х1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. "Так мне будет легче общаться с Квадратной Налоговой Инспекцией", - сказал он.

Сделка состоялась. Найдите, какое количество квадратных свидетельств он получил.

Вход: в единственной строке находится натуральное число N<=60000 - число квадриков, которое было у жителя.

Выход: в единственной строке должно находиться число свидетельств, полученных в результате сделки.

Пример входного файла:

344

Пример выходного файла:

3

Задача F. Преобразование.

В этой задаче нет длинных историй из жизни. Нет длинных преамбул и сложных постановок. Все, что требуется для решения - прочитать из входного файла вещественное число в формате, заданном спецификацией ниже, и выдать в выходной файл это число в другом формате, о котором также будет сказано ниже.

Синтаксическое описание используемых понятий выглядит следующим образом:

<цифра> ::= 0|1|2|3|4|5|6|7|8|9
<целое без знака> ::= <цифра>|<цифра><целое без знака>
<знак> ::= +|-
<целое> ::= <целое без знака>|<знак><целое без знака>
<символ экспоненты> ::= e|E
<экспонента> ::= <символ экспоненты><целое>
<простое вещественное число без знака> ::= <целое без знака>|.<целое без знака>|<целое без знака>.<целое без знака>
<простое вещественное число> ::= <простое вещественное число без знака>|<знак><простое вещественное число без знака>
<вещественное число> ::= <простое вещественное число>|<простое вещественное число><экспонента>

Отметим, что запись "A ::= B|C|D" означает, что по определению A есть либо B, либо C, либо D.

Вход:

На входе программа получает файл, содержащий одну или несколько пар строк. Первая строка пары содержит произвольный набор символов S. Длина строки S не превосходит 100 символов. Вторая строка пары содержит целое число N (0 <= N <= 100). Файл завершается парой строк, первая строка которой содержит единственный символ#.

Выход:

Для каждой пары строк входного файла программа должна выдать в выходной файл сообщение "Not a floating point number", если строка S не является правильным <вещественным числом> в соответствии с приведенной выше спецификацией. Если же S является <вещественным числом>, то программа должна выдать в выходной файл это число в формате <простого вещественного числа> с точностью N знаков после десятичной точки. При формировании результата следует помнить о следующем:

1. Целая часть числа не должна быть пуста.

2. В ненулевой целой части числа не должно быть ведущих нулей. В нулевой - точно один ноль.

3. Дробная часть должна содержать точно N знаков.

4. Перед положительным числом не должно стоять знака '+'.

5. Округление выполнять не надо.

Гарантируется, что результат всегда будет занимать не более 200 символов.

Пример входного файла:

.04
1
-0.051e0
1
1.1e30
10
-1.1E-30
1
2468097632.1358642324268913e-2
20
e23
3
1 e3
1
#

Пример выходного файла:

0.0
0.0
1100000000000000000000000000000.0000000000
0.0
24680976.32135864232426891300
Not a floating point number
Not a floating point number

Задача G. Нитка в пространстве.

Даны три точки в трехмерном пространстве - A, B и С. Все координаты этих точек - целые и ограничены по модулю числом 1000. Твердый шар с центром в точке С прочно закреплен. Радиус шара R - целое положительное число. Расстояния от точки С до точек A и B строго больше R.

Необходимо протянуть из точки А в точку B нитку минимальной длины. Разумеется, эта нитка не может заходить внутрь шара. Ваша задача - найти длину этой нитки.

Вход: в трех последовательных строках входного файла перечислены координаты точек А, B и C соответственно. Каждая строка содержит три числа - координаты X, Y и Z. В четвертой строке указан радиус шара R.

Выход: наименьшая возможная длина нитки с точностью 2 знака после запятой.

Пример входного файла:

0 0 12

12 0 0

10 0 10

10

Пример выходного файла:

19.71