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

Автор:Ю.Сидоренко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1046

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

Стандартный вход Стандартный выход
1
2946901
Простое число
2
750306010782
Составное число

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

Автор:Т.А. Трепаченко   Ограничение времени:10 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 40
0 ≤ aij bij ≤ 10
5000 ≤ s ≤ 200000

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

Стандартный вход Стандартный выход
1
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
            
2
4
0 1 2
0 2 4
0 3 5
1 3 1
            
NO

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

Автор:Н.Добрынский   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Ограничения

2 ≤ N ≤ 1000

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

Стандартный вход Стандартный выход
1
2
0 3
3 0
3
2
4
0 1 0 3
1 0 4 2
0 4 0 0
3 2 0 0
7

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

Автор:Н.Добрынский   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Например для формулы (x1 ∨ x2) ∧ (¬ x1 ∨ x3) ∧ (¬ x2 ∨ ¬ x3) будет следующий ввод:

3
1 2
-1 3
-2 -3

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

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

Ограничения

1 ≤ M ≤ 105
|N| ≤ 105
N ≠ 0

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

Стандартный вход Стандартный выход
1
3
1 2
-1 3
-2 -3
            
Possible
2
3
1 2
-1
-2
            
Impossible

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

Автор:Н.Добрынский   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Например для формулы (x1 ∨ x2 ∨ x3) ∧ (¬ x1 ∨ x3 ∨ x2) ∧ (¬ x2 ∨ ¬ x3) будет следующий ввод:

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

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

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

Ограничения

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

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

Стандартный вход Стандартный выход
1
3
1 2 3
-1 3 2
-2 -3
            
Possible
2
4
1 2
-1
-2 1 3
-3
            
Impossible

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

Автор:Н.Добрынский   Ограничение времени:3 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000
0 ≤ aij bij ≤ 50000

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

Стандартный вход Стандартный выход
1
3
0 1
1 2
2 0
            
YES
2
4
0 1
1 2
1 3
3 2
            
NO

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

Автор:Ю.Сидоренко   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

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

Стандартный вход Стандартный выход
1
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
2
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. Кратчайший путь

Автор:Ю.Сидоренко   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

0 ≤ E ≤ 15

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

Стандартный вход Стандартный выход
1
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. Длиннейший путь

Автор:Ю.Сидоренко   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

0 ≤ E ≤ 15

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

Стандартный вход Стандартный выход
1
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
2
4 2 3
0 19 25 21
19 0 43 15
25 43 0 15
21 15 15 0
            
61

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

Автор:П.Р. Месенёв, А.В. Байдин   Ограничение времени:3 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 40,

1 ≤ k ≤ n2.

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

Стандартный вход Стандартный выход
1
4 4
Петя Маша
Петя Света
Витя Маша
Витя Света
yes
2
4 2
Петя Маша
Витя Света
no

Задача Z1. Гаечка и покраска волос

Автор:П.Р. Месенёв   Ограничение времени:10 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Фоновая картинка :3

В один солнечный день Гаечка решила, что её образ нуждается в свежести. "Как насчёт чего-то яркого, стильного и немного эксцентричного?" — подумала она. Идея покрасить волосы в несколько цветов (разделённых на две группы — тёплые и холодные) показалась ей гениальной, но вскоре стало ясно: сделать это без проблем будет совсем непросто.

Каждый участок волос представлял собой сложную задачу. Некоторые краски могли соседствовать, а другие — вызывали странные реакции. Когда Гаечка попыталась смешать флуоресцентный оранжевый с кислотно-синим, У Дейла внезапно потемнело в глазах, Чип потерял дар речи, а Вжик нервно кружил над её головой, пока не упал в банку с краской.

Чтобы всё грамотно распланировать, Гаечка превратила свою голову в математическую задачу:

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

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

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

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

Входные данные содержат число n — количество вершин на первой строке. Далее на отдельных строках идут пары вершин, соединённых рёбрами.

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

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

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

Стандартный вход Стандартный выход
1
6
1 4
2 5
3 6
1 2 3 7 8 9
2
9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1
3
1
1
4
5
1 2
1 5
2 5
2 3
3 4
4 5
1 2 4 6

0.671s 0.009s 35