Информатика

У Маши есть связный ненаправленный граф G с N вершинами, помеченными 1…N и M ребрами (\(1 \leq N \leq10^2\), \(N-1 \leq M \leq \frac {N^2+N}{2}\)). G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).
Пусть \(f_G(a,b)\) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для \(1 \leq a \leq N\) и \(0 \leq b\), и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ. 
Даша хочет повторить за Машей. В частности, она хочет сконструировать ненаправленный граф G′ такой, что \(f_{G'}(a,b)=f_G(a,b)\) для всех a и b.

Посчитайте количество различных графов G′, которые Даша может создать, по модулю \(10^9+7\). Как и G, G′ может содержать петли но не может иметь параллельные ребра (это означает, что имеется всего \(2^{ \frac {N^2+N} {2}}\) различных графов на N вершинах).
Каждый ввод содержит T (\(1 \leq T \leq \frac {10^5}{4}\)) тестов, которые должны решаться независимо. Гарантируется, что сумма \(N^2\) по всем тестам не превысит \(10^5\).

Входные данные
Первая строка ввода содержит T, количество тестов.
Первая строка каждого теста содержит два целых числа N и M.
Следующие M строк каждого теста содержат два целых числа x и y (\(1 \leq x \leq y \leq N\)), обозначающих ребро между x и y в G.

Тесты разделены пустой строкой для читабельности.

Выходные данные
Для каждого теста выведите количество различных G′ по модулю \(10^9+7\) на отдельной строке.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 5 4 1 2 2 3 1 4 3 5	3	G′ может быть равен G′ или одному из двух следующих графов: 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5
2	7 4 6 1 2 2 3 3 4 1 3 2 4 1 4 5 5 1 2 2 3 3 4 4 5 1 5 5 7 1 2 1 3 1 5 2 4 3 3 3 4 4 5 6 6 1 2 2 3 3 4 4 5 5 6 6 6 6 7 1 2 2 3 1 3 1 4 4 5 5 6 1 6 10 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 22 28 1 2 2 3 3 4 4 5 5 6 6 7 1 7 1 8 3 9 8 10 10 11 10 12 10 13 10 14 11 15 12 16 13 17 14 18 9 15 9 16 9 17 9 18 15 19 19 20 15 20 16 21 21 22 16 22	45 35 11 1 15 371842544 256838540	Это пример более крупного теста. Обязательно выводите ответ по модулю \(10^9+7\). Обратите внимание, что ответ для предпоследнего теста - \(2^{45}\ \ (mod\ 10^9 + 7)\).

 

Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).

Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 10⁹+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N² всех тестов не превысит 2⋅10⁴.


Входные данные: 
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.

Последовательные тесты разделены пустыми строками для читабельности.

Выходные данные: 
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 8 0 SS....RR 00100000 00100000 00011000 00000100 00000100 00000011 00000000 00000000 13 0 SSS.RRRSS.RR. 0001000000000 0001000000000 0001000000000 0000111000000 0000000000000 0000000000000 0000000000000 0000000001000 0000000001000 0000000000110 0000000000000 0000000000000 0000000000000	4 12	Для первого теста ребра таковы 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8. Имеется четыре схемы маршрутизации: 1→3→4→6→7,2→3→5→6→8 1→3→5→6→7,2→3→4→6→8 1→3→4→6→8,2→3→5→6→7 1→3→5→6→8,2→3→4→6→7 Для второго теста 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12. Одна из возможных схем маршрутизации: 1→4→5 2→4→7 3→4→6 8→10→12 9→10→11 В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
2	2 5 1 SS.RR 00101 00100 10010 00000 00000 6 2 S....R 001000 000100 010001 000010 001000 000000	3 1	Для первого теста, ребра 1→3,1→5,2→3,3→1,3→4. имеется три схемы маршрутизации: 1→3→1→5, 2→3→4 1→3→4, 2→3→1→5 1→5, 2→3→1→3→4 Для второго теста 1→3,2→4,3→2,3→6,4→5,5→3. Имеется только одна схема мартшрутизации: 1→3→2→4→5→3→6.
3	5 3 2 RS. 010 101 100 4 2 .R.S 0100 0010 1000 0100 4 2 .SR. 0000 0011 0100 0010 5 2 .SSRR 01000 10101 01010 00000 00000 6 2 SS..RR 001010 000010 000010 000010 100101 000000	2 1 2 6 24

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i,j) для всех 1≤i≤N, 1≤j≤N (1≤N≤150). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:

Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x₁,y) (x₂,y) (x₁≤x₂) есть часть подмножества, то все ячейки (x,y) с x₁≤x≤x₂ также часть подмножества.
Если ячейки (x,y₁) and (x,y₂) (y₁≤y₂) есть часть подмножества, то все ячейки (x,y) with y₁≤y≤y₂ также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 10⁹+7.

Входные данные: 
Первая строка содержит число N.
Каждая их последующих N строк содержит строку из N символов. j-ый символ строки i сверху равен G если ячейка (i,j) содержит траву или символ . в противном случае.

Выходные данные: 
Количество сбалансированных подмножеств по модулю 10⁹+7.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 GG GG	13	Для этого теста все 4-связные подмножества сбалансированные. G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
2	4 GGGG GGGG GG.G GGGG		642 Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию: GG.. .G.. GG.. ....

Коровы Фермера Джона ежедневно собираются на видео-платформе "mooZ". Они придумали простую числовую игру.
У Эльзы есть три положительных целых числа A, B, C (1≤A≤B≤C). Предполагается что они секретные, поэтому она не объявляет их явно своей сестре Беси. Вместо этого она говорит Беси N (4≤N≤7) различных целых чисел x₁,x₂,…,x_N (1≤x_i≤10⁹), подразумевая что каждое из xi это одно из чисел A, B, C, A+B, B+C, C+A, or A+B+C. Однако Эльза может солгать. Целые числа xi могут не соответствовать ни одной корректной тройке (A,B,C).

Беси попросила Вас определить количество троек (A,B,C), соответствующих числам, которые представила Эльза (возможно 0).

Каждый входной файл будет содержать T (1≤T≤100) тестов, которые необходимо обрабатывать независимо.

ФОРМАТ ВВОДА 
Первая строка содержит целое число T.
Каждый тест начинается с числа N, количества целых числе, которые Эльза дала Беси.

Вторая строка каждого теста содержит N различных целых чисел x₁,x₂,…,x_N.

ФОРМАТ ВЫВОДА 
Для каждого теста выведите количество троек (A,B,C), соответствующих представленным Эльзой числам.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 7 1 2 3 4 5 6 7 4 4 5 7 8 4 4 5 7 9 4 4 5 7 10 4 4 5 7 11 4 4 5 7 12 4 4 5 7 13 4 4 5 7 14 4 4 5 7 15 4 4 5 7 16	1 3 5 1 4 3 0 0 0 1	Для x={4,5,7,9}, имеется 5 возможных комбинаций: (2,2,5),(2,3,4),(2,4,5),(3,4,5),(4,5,7).

На вход подается число N - количество элементов массива. 
Далее идут два массива из N целых чисел каждый:
элементы первого массива идут по одному в каждой строке,
элементы второго массива - записаны все в одной строке через пробел
Заполните два массива и выведите их элементы через пробел в одну строку:
первый массив в первой строке
второй массив во второй строке

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 4 5 6	1 2 3 4 5 6

Первая строка входного файла содержит число n. Вам нужно вывести целое число m, где m - округленное до целого число n.
Пример.

Input	Output
3,2	3
-5,6	-6

Программистка Полиночка стала изучать оператор ввода, чтобы ее программы стали более универсальными и работали на разных наборах значений. Ей даются значения двух переменных: первая строка входного файла содержит число детей в классе, вторая -  количество девочек в классе. Ей нужно вывести на экран количество мальчиков. То есть если, например, количество детей в классе 25, из них 10 девочек, то Полиночка должны вывести, что в классе 15 мальчиков.

Пример.

Input	Output
19 10	9

Пример

Входные данные	Выходные данные
Hello, world!	# ## ######### !,Hdelorw
Twas brillig, and the slithy toves Did gyre and gimble in the wabe; All mimsy were the borogoves, And the mome raths outgrabe.	# # # # # # # # # # # # ### #### ## ###### #### ############## ############## ## # # ############## ### ######################## ,.;ADTabdeghilmnorstuvwy

Лифт

В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли n кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

До начала соревнований остается мало времени, поэтому они обратились за помощью к вам. Помогите организаторам выяснить, канат какой максимальной длины удастся получить.

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ a_i ≤ 1000) — длины имеющихся кусков каната.

Формат выходных данных
Выведите единственное число — максимальную длину каната, которую можно получить.
 

Ввод	Вывод
2 10 25 50	55
5 2 4 5 6 7 8	14

Организаторы Всероссийской командной олимпиады школьников по программированию всегда ответственно относятся ко всем этапам проведения соревнования. Недавно организаторам были доставлены футболки для участников олимпиады. Они были сложены в ящик, который является кубом со стороной в один метр. Ящик был поставлен в углу комнаты прямоугольной формы размером m × n метров. Чтобы никто случайно не забрал ящик, на его верхней грани красной краской написали слово «ВКОШП».

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

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

Но когда они уже собрались начать транспортировку, обнаружилась еще одна проблема. Красная надпись «ВКОШП» каждый раз, касаясь пола, оставляет на нем следы. Поэтому среди всех вариантов транспортировки, минимизирующих количество перекатываний, организаторы решили выбрать тот, при котором надпись «ВКОШП» окажется на нижней грани куба минимальное число раз.

Помогите организаторам — посчитайте, сколько раз надпись «ВКОШП» коснется пола при оптимальном перекатывании куба с футболками.

Формат входных данных
В первой строке задано два числа n и m (1 ≤ n, m ≤ 10⁹ ) — размеры комнаты в метрах.

Формат выходных данных
Выведите одно число — сколько раз надпись «ВКОШП» окажется на нижней грани при оптимальном перемещении ящика.
 

Ввод	Вывод
1 2	0
3 3	1

Пояснение

В первом примере необходимо одно перекатывание, надпись, которая исходно была на верхней грани, окажется на боковой грани, но пола не коснется.
Во втором примере необходимо четыре перекатывания. В любом случае хотя бы один раз надпись «ВКОШП» коснется пола. Один из способов сделать перекатывания так, чтобы это произошло один раз, следующий. Сначала два раза перекатим куб в одном направлении (он окажется в соседнем углу комнаты). Сейчас надпись «ВКОШП» находится на нижней грани и касается пола. Затем перекатим куб еще два раза в перпендикулярном направлении. Теперь куб находится в требуемом положении.

Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

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

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

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 10⁶ по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа α_i и β_i , где α_i — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а β_i — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите α_i = β_i = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10⁻⁶ .
 

Ввод	Вывод
4 0 0 -3 -3 0 -6 3 -3 3 -8 0 -2 0 2 -1	360.000000000000 360.000000000000 45.000000000000 225.000000000000 251.565051177078 18.434948822922

Пояснение


На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины.
Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на 45 гр.  по часовой стрелке или на 225 гр. против часовой стрелки.

 

Какие существуют подходы к измерению информации?

1. алфавитные и цифровой
2. алфавитный и содержательный
3. аналоговый и дискретный
4. аналоговый и линейный