Автор: | Ю.Сидоренко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
Жила-была гадалка, которая всех обманывала, и на самом деле не имела никаких сверхестественных сил. Но однажды к ней пришел некий человек, увлекающийся математикой. Он начал задавать ей числа и просить дать ответ: простое число или сложное.
Но гадалка не из простых обманщиков, она делает все профессионально. Именно поэтому ей нужна помощь с написанием программы, которая достаточно быстро проверяет число на простоту.
На вход подается число N.
Вывести "Простое число" в случае, если оно простое, иначе вывести "Составное число".
1 ≤ N ≤ 1046
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Т.А. Трепаченко | Ограничение времени: | 10 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
Великие ростовские стримеры Четвёрка и Мэлш c недавних пор стали ещё и музыкантами.
Фанаты очень хотят увидеть своих кумиров вживую, а стримеры исполнить свои песни на сцене. Поэтому они решили отправиться в тур по городам России с концертами, чтобы встретиться с поклонниками и порадовать их выступлениями.
Однако, будучи новичками в организации туров, Четвёрка и Мэлш не хотят рисковать и тратить много денег на поездки по неизвестным маршрутам. Чтобы сэкономить и выбрать наиболее выгодный путь, они обратились к вам за помощью. Артисты предоставили вам список городов, а также данные о перелётах и поездках на поезде, включая стоимость билетов.
Ваша задача — подсказать им, можно ли организовать такой тур, чтобы они посетили все выбранные города по одному разу, вернулись в свой родной город и при этом потратили бы минимальную сумму денег.
Входные данные содержат натуральное число N — количество рейсов между городами. А далее идут N строк, в которых указаны числа aij bij — номера городов, между которыми есть рейс, и s — цена за билет.
Гарантируется, что граф является простым и связным.
Требуется вывести порядок посещаемых городов, начиная и заканчивая с города "0" и минимальную стоимость маршрута, если такой тур возможно организовать. В противном случае выведите "NO".
2 ≤ N ≤ 40
0 ≤ aij bij ≤ 10
5000 ≤ s ≤ 200000
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Н.Добрынский | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
Вам дан связный, взвешенный, неориентированный граф, ваша задача подсчитать сумму ребер его минимального остовного дерева.
В первой строке натуральное число N - размерность матрицы смежности. Далее идет матрица смежности.
Число - сумма ребер минимального остовного дерева
2 ≤ N ≤ 1000
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Н.Добрынский | Ограничение времени: | 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 |
|
|
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 |
|
|
2 |
|
|
Автор: | Н.Добрынский | Ограничение времени: | 3 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
После очередной победы на Кубке Поршня Молния Маквин решил отдохнуть. Вместе с Луиджи и Гвидо он отправился в Италию. Города в Италии состоят из узких улочек, есть множество перекрестков, соединенных дорогами. Однако, не все части городка могут быть соединены между собой, так как некоторые районы могут быть изолированы.
Так как Маквин здесь еще не бывал, он хочет проехаться и посмотреть каждый городок целиком. Начать свой путь он может с любого перекрестка. Но есть одно условие, Молния хочет проехать по всем улицам ровно один раз и вернуться в исходную точку, чтобы завершить экскурсию.
Ваша задача выяснить, сможет ли Маквин совершить подобный заезд.
В первой строке натуральное число N - количество дорог. В следующих N строках идут целые числа aij bij- номера перекрестков, соединенных дорогой, по два в каждой строке. Граф является простым и не имеет изолированных вершин.
Выведите YES, еcли экскурсия возможна. В противном случае выведите NO.
1 ≤ N ≤ 100000
0 ≤ aij bij ≤ 50000
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Ю.Сидоренко | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
Проехав по городу, Молния Маквин, Луиджи и Гвидо решают посетить различные туристические места, которые были указаны у них в путеводителе. Но времени у них осталось уже не так много, а успеть посетить все очень хочется.
Чтобы успеть везде побывать они хотят найти самый оптимальный маршрут. Достопримечательности могут быть связаны между собой дорогой, а могут быть совершенно в другом месте. Каждую достопримечательность нужно посетить лишь единожды. Начальная точка экскурсии и количество достопримечательностей выбираются с самого начала.
Ваша задача понять, возможно ли проехать по всем достопримечательностям, посетив каждую лишь единожды.
На вход подается число N и S.
N - количество достопримечательностей.
S - начальная точка
После чисел следует матрица смежности графа размерностью N.
Вывести последовательность номеров вершин, которые персонажам предстоит посетить, иначе вывести "Нет решения"
3 ≤ N ≤ 16
0 ≤ S ≤ 15
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Ю.Сидоренко | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
Двум друзьям нужно добраться до общежития. Комендантский час начинается в 23:00, а сейчас на часах 22:40. Им нужно успеть добежать до общежития как можно скорее.
На их пути есть несколько последовательностей перекрестков, по которым они могут пройти. Но только одна последовательность будет кратчайшей. Нужно помочь друзьям найти кратчайший путь и добраться до общежития, которое находится на одном из перекрестков вовремя.
На вход подается число N, S и E .
N - количество перекрестков.
S - начальный перекресток.
E - конечный перекресток.
После чисел следует матрица смежности графа размерностью N с расстоянием от одного перекрестка до следующего.
Вывести длину минимального пути.
3 ≤ N ≤ 16
0 ≤ S ≤ 15
0 ≤ E ≤ 15
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Ю.Сидоренко | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход |
Догнатий-Перегнатий идет со школы домой, он прогуливает последний урок. Но сидеть на улице ему не хочется, он хочет прогуляться до дома настолько долго, насколько это возможно. Его путь может лежать через несколько перекрестков, но только один путь будет длиннейшим.
Помогите Догнатий-Перегнатию дойти до дома как можно дольше.
На вход подается число N, S и E .
N - количество перекрестков.
S - начальный перекресток.
E - конечный перекресток.
После чисел следует матрица смежности графа размерностью N с расстоянием от одного перекрестка до следующего.
Вывести длину максимального пути.
3 ≤ N ≤ 16
0 ≤ S ≤ 15
0 ≤ E ≤ 15
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | П.Р. Месенёв, А.В. Байдин | Ограничение времени: | 3 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Согласно исследованиям известного ученого, А.Г. Пря́мина, проблемы одной конкретной страны можно решить, если устроить огромный хоровод, от одного края страны до другого.
Так как в этой стране бытуют крайне консервативные взгляды, то в таком хороводе юноши и девушки должны чередоваться. Но и этого мало — держащиеся за руки должны быть взаимно симпатичны друг другу (в романтическом смысле).
Вам дан список взаимных симпатий, в котором, для вашего удобства, сначала указан юноша, а затем девушка.
Ваша задача написать программу, которая по предоставленному списку определит, можно ли устроить хоровод с участием всех пришедших, решив все проблемы одной конкретной страны разом.
Входной файл содержит натуральные числа n, k, где n — количество пришедших юношей и девушек. Далее следует k пар взаимно симпатичных (в романтическом смысле) имён.
Гарантируется, что количество юношей равно количеству девушек, а также уникальность имени у каждого участника.
Требуется напечатать "yes", если можно составить хоровод из всех участников по указанным правилам, и "no" в противном случае.
1 ≤ n ≤ 40,
1 ≤ k ≤ n2.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | П.Р. Месенёв | Ограничение времени: | 10 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
В один солнечный день Гаечка решила, что её образ нуждается в свежести. "Как насчёт чего-то яркого, стильного и немного эксцентричного?" — подумала она. Идея покрасить волосы в несколько цветов (разделённых на две группы — тёплые и холодные) показалась ей гениальной, но вскоре стало ясно: сделать это без проблем будет совсем непросто.
Каждый участок волос представлял собой сложную задачу. Некоторые краски могли соседствовать, а другие — вызывали странные реакции. Когда Гаечка попыталась смешать флуоресцентный оранжевый с кислотно-синим, У Дейла внезапно потемнело в глазах, Чип потерял дар речи, а Вжик нервно кружил над её головой, пока не упал в банку с краской.
Чтобы всё грамотно распланировать, Гаечка превратила свою голову в математическую задачу:
Теперь задача проста: разделить участки на две группы (по два цвета), чтобы количество рёбер, соединяющих вершины разного цвета, было максимально большим. "Это идеальный баланс между хаосом и гармонией," — решила она.
Чип взялся за рассчитать необходимое количество оксигента, Вжик помогал раскладывать краски, а Дейл продолжал предлагать добавить "немного больше блёсток".
Помогите Гаечке решить эту задачу, чтобы её новый стиль стал самым запоминающимся!
Входные данные содержат число n — количество вершин на первой строке. Далее на отдельных строках идут пары вершин, соединённых рёбрами.
Требуется указать множество полученное оптимальным разбиением, включающее первую вершинку. Если возможных разбиений несколько, вывести любое оптимальное, содержащее первую вершинку.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|