Задача A. Слишком много способов ≡

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера x, y, z — порядковые номера по ширине, длине и высоте соответственно. Самая первая аудитория имеет номера 1, 1, 1. Из каждой аудитории можно перейти в любую соседних, имеющих с ней общую стену.

Вася находится в аудитории (x_B, y_B, z_B). Мастер-класс пройдет в аудитории (x_M, y_M, z_M). Вася решил посчитать, сколькими способами можно попасть из текущей аудитории в ту, где проходит мастер-класс, за наименьшее число переходов между аудиториями.

Однако Вася частенько прогуливает мастер-классы и не знает как это сделать, поэтому он отправил смс-ку вам, в надежде, что вы подскажете ему ответ.

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

Входной файл содержит 6 целых чисел x_M y_M z_M x_B y_B z_B.

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

Выходной файл должен содержать единственное целое число — количество способов. Так как ответ на вопрос Васи может быть слишком большим, выведите в его остаток от деления на 10⁹ + 7.

Ограничения

1 ≤ x_M, y_M, z_M, x_B, y_B, z_B ≤ 1000.

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

1 1 1 2 2 2

6

1 1 1 3 3 3

90

Problem B. 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

Задача C. Гадание на ромашках ≡

Условие

Однажды Аполлинарий Матвеевич очутился на поле, на котором росли ромашки. Он сорвал несколько ромашек и стал гадать, любит или не любит его Марфа Геннадьевна. А гадал он так: брал каждую ромашку по отдельности и отрывал от неё лепестки, приговаривая: "любит", "не любит", "любит", "не любит"... Если при отрывании последнего лепестка он говорил "любит", то для этой ромашки ответ — "любит", а иначе для этой ромашки ответ — "не любит". Аполлинарий Матвеевич посчитал, сколько ромашек дали ответ "любит" и сколько ромашек дали ответ "не любит". Если количество ромашек с ответом "любит" строго больше, чем количество ромашек, давших ответ "не любит", то Аполлинарий Матвеевич считает, что Марфа Геннадьевна его любит. А в противном случае ромашки, увы, говорят обратное.

Аполлинарий Матвеевич задумался: сколько существует способов сорвать букет таким образом, чтобы ответ был "любит"?

Дано N — число ромашек на поле и числа a_i — количества лепестков на ромашках. Требуется определить, сколькими способами можно сорвать букет, чтобы ответ был "любит".

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

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

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

Требуется вывести в выходной файл единственное целое число — число способов сорвать букет, чтобы ответ был "любит".

Ограничения

1 ≤ N ≤ 31

1 ≤ a_i ≤ 20

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

2
8 5

1

3
5 8 7

4

Problem D. Cthulhu spawn ≡

Statement

Scientists of the Nearsea Institute of Underwater Mythology are researching the mythical creature called Cthulhu.

The creature is famous for producing many offspring known as Cthulhu spawn. Each spawn has a small round body with N radially protruding appendages. Each appendage is either a tentacle or a claw.

Two spawns are considered identical, if one of them can be rotated in such a way that the sequence of tentacles and claws will coincide with the other spawn.

For example, if we designate tentacle by "T" and claw by "C", spawns "TCTCCT" and "CCTTCT" are identical and different from spawns "TTTCCT" ad "CCTTTC".

You program must, for given N, calculate the total number of different spawns with N appendages.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single integer — number of different spawns.

Constraints

1 ≤ N ≤ 58

Sample tests

1

2

4

6

Задача E. Океанариум ≡

Условие

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

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

Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.

Рекомендуется рассмотреть частичные решения

• N = 1,
• каждый листок содержит ровно одно название рыбки.

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

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

Ограничения

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

1
2
Carassius auratus
Poecilia reticulata

2

3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead

8

Задача E. Марсианский тир ≡

Условие

Стрельба в марсианском тире проходит по следующим правилам: Когда стрелок приходит в тир, ему выдаётся новая мишень, имеющая вид горизонтального отрезка чёрного цвета. Стрелок делает N серий выстрелов. Перед началом каждой серии некоторые отрезки мишени красят в красный цвет. Краска не смывается до конца всех серий стрельбы. За выстрел начисляется балл, если он попал в закрашенный участок.

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

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

Входной файл содержит целое число N, за которым идут N блоков, описывающих серии выстрелов. Серия номер i задаётся числом K_i — количеством закрашиваемых отрезков, за которым следуют K_i пар чисел L_{i, j} R_{i, j}, задающих левую и правую границу очередного отрезка; затем S_i — количество выстрелов в i-ой серии, и наконец S_i чисел P_{i, j}, задающих координаты попаданий.

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

Выходной файл должен содержать единственное число — количество набранных баллов.

Ограничения

1 ≤ N ≤ 100

0 ≤ K_i ≤ 1000

0 ≤ S_i ≤ 10⁴

0 ≤ L_{i, j} ≤ R_{i, j} ≤ 10⁷

0 ≤ P_{i, j} ≤ 10⁷

Все числа во входном файле целые

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

1
4   9 14  4 5  1 2  6 6
5   1 6 3 17 12

3

2
3   10 20  75 100  15 25
4   4 2 16 9
1   23  78
2   13 77

3

Задача F. Золотая середина ≡

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).

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

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

Входной файла содержит количество чисел n, за которым следуют n целых чисел a_i в порядке их добавления в набор.

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

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

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

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

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2

Задача G. Сбалансированное дерево ≡

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Problem H. Breadth First Search ≡

Statement

You are to write a program that receives an unweighted undirected graph and writes all its vertices in order of increasing distance from given vertex S. Distance between vertices A and B is the length of the shortest path from A to B. If there are several vertices such that their distances to S are equal, they may be printed in arbitrary order.

Input file format

Input file contains three integers N, M and S, where M is the number of edges, S is the starting vertex. Vertices are numbered with integer numbers from 1 to N. Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.

Output file format

Output file must contain sequence of vertex numbers sorted by increasing distance from S. If some vertex is not reachable from S, output a single number −1.

Constraints

Sample tests

3 2 1
1 2
2 3

1 2 3

Задача I. Лабиринт ≡

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

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

В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.

Ограничения

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

4 1 1 4 1
..#.
..#.
..#.
....

9

Задача J. Бюрократия ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4

Задача K. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

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

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Problem L. Biconnectivity ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 6
1 2
1 3
2 3
1 4
1 5
4 5

1 1

Задача M. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

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

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

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

Ограничения

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

3 1
2 3

2