Задача A. Дорога в аэропорт ≡

Условие

Город соединяется с аэропортом автодорогой, имеющей N полос движения. Дорога состоит из K участков длиной 10 километров каждый. На каждом участке полосы разделены сплошной линией разметки (т.е. сворачивать с одной полосы на другую запрещено). На стыке участков разрешено перемещение на любую из соседних полос. В начале каждого участка на каждой полосе дороги поставлен знак ограничения скорости, при этом на разных полосах ограничения могут различаться.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1 3
70 60 40

0.559

3 2
1 10000
1 1
100 1

10.001

Задача B. Knapsack problem ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 7
1 5 6

1 0 1

Задача C. Breadth First Search ≡

Условие

Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S. Расстояние между вершинами A и B это длина кратчайшего пути из A в B. Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S, выведите их в произвольном порядке.

Формат входного файла

Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины. Вершины пронумерованы целыми числами от 1 до N. Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.

Формат выходного файла

Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S. Если какая-то из вершин недостижима из S, выведите единственное число −1.

Ограничения

Примеры тестов

3 2 1
1 2
2 3

1 2 3

Задача D. Интернет по ЛЭП ≡

Условие

Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач. Для этого на подстанциях были установлены N ретрансляторов.

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

Требуется написать программу, которая по заданной схеме электросети подсчитает нагрузку на каждый ретранслятор.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 2
2 3

2 1 2

4
1 2
1 3
1 4

1 3 3 3

Задача E. Двойные тетради Чебурашки ≡

Условие

Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу. Он заранее готовился к этому: накупил карандашей, ручек, тетрадей. Среди покупок, кроме обычных тетрадей, были также и двойные, каждая из которых предназначена сразу для двух предметов.

Каждый день Чебурашке нужно брать с собой тетради для всех предметов, которые будут преподаваться в его классе в этот день. Тетради тяжелые, а носить лишний вес в школу не хочется. Поэтому он пытается распределить предметы по тетрадям таким образом, чтобы за неделю переносить наименьший возможный вес. Помогите ему это сделать.

У Чебурашки есть N_S одинарных и N_D двойных тетрадей. Все одинарные тетради имеют вес W_S, а все двойные — вес W_D. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

Формат входного файла

Во входном файле содержатся числа N M N_S N_D W_S W_D. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится K_i — число уроков в i-ый день, за которым следует K_i чисел — номера предметов. Все числа во входном файле целые.

Формат выходного файла

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ W_S, W_D ≤ 10⁹

0 ≤ K₁ + K₂ + … + K_N ≤ 15

2 × N_D + N_S = M

Примеры тестов

4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4

8

4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4

4

Задача F. Табуретки-1 ≡

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L₁, L₂, …, L_N.

Требуется определить максимальное количество качественных табуреток, которые можно изготовить из данных ножек.

Формат входного файла

Входной файл содержит число N, за которым следуют N чисел L_i — длины ножек. Все числа целые.

Формат выходного файла

Ограничения

Примеры тестов

9
17 18 18 17 17 16 17 17 19

1

Задача G. Табуретки-2 (30 баллов) ≡

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L₁, L₂, … L_N. Научно-исследовательский отдел фабрики обнаружил, что выпуск табуреток можно увеличить, если укорачивать некоторые ножки. При этом отпиленная часть выбрасывается.

Требуется определить минимальное количество распилов, необходимых для для изготовления N / 4 качественных табуреток.

Формат входного файла

Входной файл содержит число N, за которым следуют N чисел L_i — длины ножек. Все числа целые.

Формат выходного файла

Ограничения

Примеры тестов

8
18 16 17 17 16 17 17 19

2

Problem H. Jokers ≡

Statement

Once upon a time Marfa Gennadievna bought a pack of 54 playing cards containing two jokers. She put cards face down and chose N cards of them randomly (with uniform probability distribution).

Your program must calculate the probability that there will be at least one joker among chosen cards.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single real number — required probability with at least 6 correct digits after decimal point.

Constraints

2 ≤ N ≤ 54

Sample tests

2

0.073375

10

0.338924

Задача I. Ближайшее число - 1 ≡

Условие

Дан массив A, состоящий из N неотрицательных целых чисел.

Назовём правым (левым) соседом нулевого элемента ближайший к нему справа (слева) ненулевой элемент.

Требуется построить массив B, который получается из массива A заменой каждого нулевого элемента на его ближайшего соседа в массиве A. Если оба соседа отсутствуют либо расстояния до них равны, замена не производится (элемент остаётся нулевым).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
0 0 1 0 2

1 1 1 0 2

4
8 0 0 6

8 8 6 6

Задача J. Барбара ≡

Условие

На некотором языке все слова записываются заглавными латинскими буквами, и состоят из слогов. Слогом называется непустая последовательность согласных, заканчивающаяся гласной. Все остальные последовательности букв словами этого языка не являются. Например, слово BARBARA состоит из трех слогов — BA, RBA и RA. Последовательности букв ААХ, Е, К, АНА словами не являются. Осмысленными считаются слова, в которых все согласные различны.

По данной последовательности из N заглавных латинских букв определить, является ли она осмысленным словом и, если да, то сколько различных слогов можно составить из букв этого слова. Например, из слова BARAKA можно составить 15 слогов — BA, KA, RA, BKA, KBA, BRA, RBA, KRA, RKA, BKRA, BRKA, RBKA, RKBA, KBRA, KRBA.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

BARAKA

15