Задача Мошенничество во благо ≡

Условие

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

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

Формат входных данных

На вход подается число N.

Формат выходных данных

Вывести "Простое число" в случае, если оно простое, иначе вывести "Составное число".

Ограничения

1 ≤ N ≤ 10⁴⁶

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

2946901

Простое число

750306010782

Составное число

Задача Концертный тур ≡

Условие

Великие ростовские стримеры Четвёрка и Мэлш c недавних пор стали ещё и музыкантами.

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

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

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

Формат входных данных

Входные данные содержат натуральное число N — количество рейсов между городами. А далее идут N строк, в которых указаны числа a_ij b_ij — номера городов, между которыми есть рейс, и s — цена за билет.

Гарантируется, что граф является простым и связным.

Формат выходных данных

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

Ограничения

2 ≤ N ≤ 40
0 ≤ a_ij b_ij ≤ 10
5000 ≤ s ≤ 200000

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

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

0 1 2 3 0
9
            

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

NO

Задача Минимальное остовное дерево ≡

Условие

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

Формат входных данных

В первой строке натуральное число N - размерность матрицы смежности. Далее идет матрица смежности.

Формат выходных данных

Число - сумма ребер минимального остовного дерева

Ограничения

2 ≤ N ≤ 1000

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

2
0 3
3 0

3

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

7

Задача 01. Задание по дискретной математике ≡

Условие

Паша не ходил на дискретную математику весь семестр, но все-таки на комиссию ему не хотелось и он подошел к преподавателю.

Иван Дискретович конечно не хотел давать ему возможность получить оценку, поэтому дал ему очень большой список формул вида: (x₁ ∨ x₂) ∧ (¬ x₁ ∨ x₃) ∧ (¬ x₂ ∨ ¬ x₃), в скобках может содержаться одна или две переменных. Задача Паши определить, может ли обращаться формула в истину. Он был уверен, что Паша не справится.

Паша обратился к вам, помогите ему не попасть на комиссию.

Формат входных данных

В первой строке натуральное число M. В следующих M строках идут целые числа от 1 до N по модулю.

Например для формулы (x₁ ∨ x₂) ∧ (¬ x₁ ∨ x₃) ∧ (¬ x₂ ∨ ¬ x₃) будет следующий ввод:

Формат выходных данных

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

Ограничения

1 ≤ M ≤ 10⁵
|N| ≤ 10⁵
N ≠ 0

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

3
1 2
-1 3
-2 -3
            

Possible

3
1 2
-1
-2
            

Impossible

Задача 02. Задание по дискретной математике 2 ≡

Условие

Паша успешно сдал задание по дискретной математике, но Иван Дискретович дал ему задание сложнее.

В этот раз он дал ему список формул вида: (x₁ ∨ x₂ ∨ x₃) ∧ (¬ x₁ ∨ x₃ ∨ x₄) ∧ (¬ x₂ ∨ ¬ x₃), в скобках может содержаться до трех переменных. Задача Паши определить, может ли обращаться формула в истину. В этот раз он точно был уверен, что Паша не справится.

Паша обратился к вам снова, помогите ему не попасть на комиссию.

Формат входных данных

В первой строке натуральное число M. В следующих M строках идут целые числа от 1 до N по модулю.

Например для формулы (x₁ ∨ x₂ ∨ x₃) ∧ (¬ x₁ ∨ x₃ ∨ x₂) ∧ (¬ x₂ ∨ ¬ x₃) будет следующий ввод:

Формат выходных данных

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

Ограничения

1 ≤ M ≤ 15
|N| ≤ 5
N ≠ 0

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

3
1 2 3
-1 3 2
-2 -3
            

Possible

4
1 2
-1
-2 1 3
-3
            

Impossible

Задача 11. Экскурсия по Италии ≡

Условие

После очередной победы на Кубке Поршня Молния Маквин решил отдохнуть. Вместе с Луиджи и Гвидо он отправился в Италию. Города в Италии состоят из узких улочек, есть множество перекрестков, соединенных дорогами. Однако, не все части городка могут быть соединены между собой, так как некоторые районы могут быть изолированы.

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

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

Формат входных данных

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

Формат выходных данных

Выведите YES, еcли экскурсия возможна. В противном случае выведите NO.

Ограничения

1 ≤ N ≤ 100000
0 ≤ a_ij b_ij ≤ 50000

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

3
0 1
1 2
2 0
            

YES

4
0 1
1 2
1 3
3 2
            

NO

Задача 12. Экскурсия по Италии 2 ≡

Условие

Проехав по городу, Молния Маквин, Луиджи и Гвидо решают посетить различные туристические места, которые были указаны у них в путеводителе. Но времени у них осталось уже не так много, а успеть посетить все очень хочется.

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

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

Формат входных данных

На вход подается число N и S.

N - количество достопримечательностей.

S - начальная точка

После чисел следует матрица смежности графа размерностью N.

Формат выходных данных

Вывести последовательность номеров вершин, которые персонажам предстоит посетить, иначе вывести "Нет решения"

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

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

9 1
0 0 1 1 0 0 1 1 0
0 0 0 1 0 0 1 0 1
1 0 0 0 1 1 0 0 1
1 1 0 0 0 1 0 0 1
0 0 1 0 0 1 0 1 0
0 0 1 1 1 0 1 0 1
1 1 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 0 1 0
            

1 3 0 2 4 7 8 5 6 1

6 0
0 1 0 0 0 0
1 0 0 1 0 1
0 0 0 0 0 1
0 1 0 0 0 1
0 0 0 0 0 0
0 1 1 1 0 0
            

Нет решения

Задача 21. Кратчайший путь ≡

Условие

Двум друзьям нужно добраться до общежития. Комендантский час начинается в 23:00, а сейчас на часах 22:40. Им нужно успеть добежать до общежития как можно скорее.

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

Формат входных данных

На вход подается число N, S и E .

N - количество перекрестков.

S - начальный перекресток.

E - конечный перекресток.

После чисел следует матрица смежности графа размерностью N с расстоянием от одного перекрестка до следующего.

Формат выходных данных

Вывести длину минимального пути.

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

0 ≤ E ≤ 15

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

10 4 6
0 407 405 152 0 0 362 0 0 0
407 0 213 0 15 0 185 0 116 136
405 213 0 350 19 0 385 0 0 0
152 0 350 0 449 391 467 201 0 0
0 15 19 449 0 0 0 0 0 77
0 0 0 391 0 0 0 0 258 444
362 185 385 467 0 0 0 463 254 388
0 0 0 201 0 0 463 0 141 0
0 116 0 0 0 258 254 141 0 284
0 136 0 0 77 444 388 0 284 0
            

391

Задача 22. Длиннейший путь ≡

Условие

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

Помогите Догнатий-Перегнатию дойти до дома как можно дольше.

Формат входных данных

На вход подается число N, S и E .

N - количество перекрестков.

S - начальный перекресток.

E - конечный перекресток.

После чисел следует матрица смежности графа размерностью N с расстоянием от одного перекрестка до следующего.

Формат выходных данных

Вывести длину максимального пути.

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

0 ≤ E ≤ 15

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

6 1 3
0 13 2 49 0 35
13 0 0 30 46 50
2 0 0 14 0 35
49 30 14 0 12 45
0 46 0 12 0 46
35 50 35 45 46 0
            

206

4 2 3
0 19 25 21
19 0 43 15
25 43 0 15
21 15 15 0
            

61

Задача Z. В этой стране хоровод ≡

Условие

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

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

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

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

Формат входных данных

Входной файл содержит натуральные числа n, k, где n — количество пришедших юношей и девушек. Далее следует k пар взаимно симпатичных (в романтическом смысле) имён.

Гарантируется, что количество юношей равно количеству девушек, а также уникальность имени у каждого участника.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 40,

1 ≤ k ≤ n².

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

4 4
Петя Маша
Петя Света
Витя Маша
Витя Света

yes

4 2
Петя Маша
Витя Света

no