Задача 01. 2-SAT ≡

Условие

Для некоторой булевой формулы, представленной в 2-КНФ требуется подобрать пследовательноость значений литералов так, чтобы формула стала истинной.

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

Первая строка содержит число n — количество клозов (англ. clause). Далее идут n строк, каждая из которых содержит не более 2х чисел. Каждое положительное число означает соответствующий литерал, а каждое отрицательное — соответствующий литерал под отрицанием. К примеру формула (X ∧ Y) ∧ (¬ X ∧ Z) будет представлена как2 1 2 -1 3

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

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

2
1 2
-1

0 1

3
1 2
-1
-2

-1

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ n ≤ 50,

2 ≤ k ≤ n².

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

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

yes

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

no

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

Условие

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

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

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

• Каждый участок волос стал вершиной графа.
• Соседствующие участки волос соединены рёбрами.

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

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

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

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

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

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

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

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

6
1 4
2 5
3 6

1 2 3

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

1

1

1

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

1 2 4

Задача Z1. Москва-Петушки ≡

Условие

Каждую пятницу Венечка садится на поезд с Курского вокзала и едет до станции Петушки к своей возлюбленной. Как только Венечка садится в поезд, он начинает избавляться от страшного недуга – похмелья, употребляя алкоголь на протяжении всей поездки. Венечке известно, что его возлюбленная отправилась к нему навстречу и ждёт его на одной из станций. Если с момента начала употребления напитков проходит t часов и Венечка не встречает свою возлюбленную ни на одной из пройденных им станций, то от грусти и количества выпитого он засыпает и просыпается на Курском вокзале, где всё начинается сначала.

Железная дорога, по которой едет поезд Венечки, соединена n станциями. Переход от станции u к станции v занимает w часов. Венечка не хочет каждый раз выходить на станции и искать возлюбленную, поэтому хочет знать наверняка – сможет ли он гарантированно найти её на одной из станций.

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

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

Далее идут m строк, в каждой из которых указаны три целых числа через пробел:

• u и v — номера станций, которые соединяют переход.
• w — количество часов, необходимое для перехода между станциями u и v.

Станция Курского вокзала в каждом примере имеет номер 0.

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

Ограничения

n ≤ 100,

0 ≤ m ≤ n².

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

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

yes

Задача Z2. You weak pathetic fool! ≡

Условие

Лю Кан проходит башни смертельных поединков. Каждая башня представляет собой испытание, в котором он может провести любое количество боёв — выигрывая или проигрывая, и накапливая общий счёт "поражения минус победы". Лю Кан начинает своё прохождение с первой башни.

После окончания тренировок в одной башне, Лю Кан может перейти в другую башню. Каждый переход имеет свою цену — разность между победами и поражениями, необходимыми для перехода. Некоторые переходы могут быть «выгодными» (отрицательная цена), другие — тяжёлыми (положительная цена).

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

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

Первая строка входного файла содержит два целых числа n и m — количества башен и переходов между ними соответственно. Далее идут m строк, в каждой из которых указаны три целых числа через пробел:

• u и v — номера башен, которые соединяют переход.
• w — разность победы минус поражения, необходимая для перехода между башнями u и v.

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

Ограничения

n ≤ 100,

0 ≤ m ≤ n².

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

5 8
1 2 4
1 3 2
2 3 3
2 4 2
2 5 4
3 4 -1
4 5 2
5 2 1

no

Задача Z3. Тайна самой дальней планеты ≡

Условие

В далёком 2182 году экспедиция с планеты Земля отправляется в космос на поиски Говоруна, что отличается умом и сообразительностью. Проблема в том, что Говоруна похитили пираты с планеты Катрук. По некоторым сведениям известно, что Говорун находится на планете t.

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

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

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

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

Вторая строка входного файла содержит два целых числа k и t - предположительное количество у.е топлива, требуемое эспедиции, и планета, на которой находится Говорун.

Далее идут m строк, в каждой из которых указаны три целых числа через пробел:

• u и v — номера планет, которые соединяют переход.
• w — количество топлива, необходимое для перехода между планетами u и v.

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

Ограничения

n ≤ 100,

0 ≤ m ≤ n².

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

4 6 
15 2
0 2 9
0 3 7
0 1 5
1 3 10
1 2 4
2 3 6

6

Задача z4. Оптимальная стратегия ≡

Условие

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

Найдите минимальное количество атак "Расэнсюрикен", необходимое, чтобы поразить всех врагов.

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

Первая строка содержит целое число n — количество врагов. Далее идут n строк, в каждой из которых указаны два целых числа через пробел xᵢ, yᵢ — координаты врагов.

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

Ограничения

1 <= n <= 15

−100 <= xᵢ, yᵢ <= 100

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

3
0 0
1 1
2 2

1

Задача Z5. Сапёр ≡

Условие

Петя изучает теорию сложности вычислений и узнал, что задача "Сапёр" является NP-полной. Так как эта задача принадлежит классу NP, её можно свести к задаче выполнимости булевых формул (SAT).

Игровое поле состоит из клеток, некоторые из которых содержат мины. Число в клетке (подсказка) показывает, сколько мин находится в соседних 8 клетках. Если в клетке число 0 - все соседние клетки безопасны.

Необходимо реализовать это сведение - преобразовать игровое поле Сапёра в булеву формулу в формате DIMACS CNF.

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

Первая строка содержит два целых числа через пробел: n m, где:

• n - количество строк
• m - количество столбцов

Последующие n строк содержат по m целых чисел через пробел, где:

• -1 обозначает закрытую клетку (неизвестно, есть ли мина)
• 0-8 обозначает открытую клетку с соответствующим числом

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

Программа должна выводить SAT-формулу в формате DIMACS CNF:

p cnf variables clauses
clause1 0
clause2 0
...

Требования к структуре формулы

Для прохождения тестов формула должна быть детерминированной. Соблюдайте следующие правила:

1. Приоритет подсказок: генерация ограничений происходит в цикле по значению числа в клетке K от 0 до 8. Сначала обрабатываются все клетки с цифрой 0, затем с цифрой 1, и так далее до 8. Внутри группы с одинаковыми цифрами клетки обрабатываются в естественном порядке (построчно: сверху-вниз, слева-направо).
2. Нумерация переменных: переменная для закрытой клетки получает свой ID (1, 2, 3...) в тот момент, когда она впервые упоминается как сосед при формировании ограничений согласно порядку из п.1.
3. Порядок соседей: при перечислении соседей (для формирования клоуза или присвоения ID) используется геометрический порядок: от верхнего левого (-1, -1) к нижнему правому (1, 1).
4. Порядок ограничений для одной клетки:
   • Сначала выводятся условия, запрещающие ситуацию "мин больше K" (комбинации отрицательных литералов).
   • Следом выводятся условия, запрещающие ситуацию "мин меньше K" (комбинации положительных литералов).
5. Уникальность: В итоговом файле не должно быть дублирующихся строк (клоузов). Дубликаты должны быть удалены, при этом сохраняется порядок первого появления клоуза.

Ограничения

1 ≤ n, m ≤ 10

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

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

p cnf 5 19
-1 -2 0
1 2 0
-3 -4 0
3 4 0
-1 -2 -3 0
-1 -2 -4 0
-1 -2 -5 0
-1 -3 -4 0
-1 -3 -5 0
-1 -4 -5 0
-2 -3 -4 0
-2 -3 -5 0
-2 -4 -5 0
-3 -4 -5 0
1 2 3 4 0
1 2 3 5 0
1 2 4 5 0
1 3 4 5 0
2 3 4 5 0

3 4
0 1 -1 -1
1 3 -1 -1
-1 -1 -1 -1

p cnf 5 19
-1 -2 0
1 2 0
-3 -4 0
3 4 0
-1 -2 -3 -4 0
-1 -2 -3 -5 0
-1 -2 -4 -5 0
-1 -3 -4 -5 0
-2 -3 -4 -5 0
1 2 3 0
1 2 4 0
1 2 5 0
1 3 4 0
1 3 5 0
1 4 5 0
2 3 4 0
2 3 5 0
2 4 5 0
3 4 5 0

Задача Z6. Быстрое перемножение матриц ≡

Условие

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

• алгоритм Штрассена;
• или модификацию Штрассена-Винограда.

Алгоритм должен корректно работать при любых размерностях n, в том числе если n не является степенью двойки. Рекомендуется продумать гибридную стратегию, при которой быстрый алгоритм используется там, где это выгодно, а на малых или неудачных размерах - обычный тройной цикл. Сторонние библиотеки запрещены. Статья про умножение матриц - https://github.com/Rmgs123/Matrix-Multiplication/blob/main/article.md

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

Вход задаёт две квадратные матрицы A и B одинакового размера. Первая строка содержит целое число n.
Затем идут n строк по n целых чисел - элементы матрицы A.
После них - n строк по n целых чисел - элементы матрицы B.

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

Выведите n строк по n целых чисел — элементы матрицы C = A × B. Числа в строках можно разделять произвольным числом пробелов. Дополнительные пробелы в конце строк допускаются.

Ограничения

1 <= n <= 512

-9 <= a_ij, b_ij <= 9

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

2
1 2
3 4
5 6
7 8

19 22
43 50

Задача Z7. Межвселенский коллапс ≡

Условие

Рик и Морти в ходе своих путешествий по вселенным нарушили парочку правил и теперь за головой Рика охотится k версий Рика из альтернативных вселенных. Они объединились и договорились разойтись по разным маршрутам из измерения s, откуда сбежал оригинальный Рик, в измерение t, где он потерял своего Морти, стараясь двигаться по попарно непересекающимся (измерения могут повторяться, но их очередность - нет) путям.

Рик тоже пытается добраться из s в t, но он хочет избежать встречи с остальными версиями себя в пространстве между измерениями. Получится ли у него это сделать, если между измерениями можно передвигаться только по определённому правилу?

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

Рик обязательно найдет путь, не пересекающийся с путями его врагов, если такой путь существует. Осталось понять существует ли k+1 непересекающихся по пространствам между измерениями путей. Также Рик провалится, если пути из s в t не существует вовсе - Морти погибнет, а Рик сдастся в плен.

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

В первой строке записано натуральное число n - количество бит в двоичном представлении измерения.

Во второй строке указаны натуральные числа s и t - начальное и конечное измерения.

В третьей строке записано число k - количество альтернативных Риков.

Далее следуют n строк, задающих правило перемещения между измерениями x и y. Каждая строка описывает операцию, результатом которой является один бит. Операции применяются по порядку: первая строка - к младшим битам чисел, вторая - к следующим и т.д.

Возможные операции над i-ыми битами чисел x и y:

• x - i-й бит результата равен i-ому биту числа x
• ~x - i-й бит результата противоположен i-му биту числа x
• y - i-й бит результата равен i-ому биту числа y
• ~y - i-й бит результата противоположен i-му биту числа y
• x & y - конъюнкция i-ых битов x_i, y_i (или их отрицаний, например x & ~y)
• x | y - дизъюнкция i-ых битов x_i, y_i (или их отрицаний)
• x ^ y - исключающее ИЛИ i-ых битов x_i, y_i (или их отрицаний)
• 0 - i-й бит результата тождественно равен нулю
• 1 - i-й бит результата тождественно равен единице

Результирующие n бит складываются (подсчитывается количество единиц) и сравниваются с числом p, указанным после описания операций. Если сумма меньше p, перемещение из x в y невозможно. Иначе между измерениями можно открыть портал.

Пояснение к примеру 1

Измерения кодируются 3-битными числами (от 0 до 7). Рик стартует в 0 (000) и должен попасть в 7 (111).

Операции по битам:

• 1-й бит: x ^ y
• 2-й бит: x ^ y
• 3-й бит: 1

Третий бит результата всегда равен 1, первые два - равны 1, если соответствующие биты x и y различаются. Портал открывается, если сумма битов ≥ p = 2.

Например, для ребра 0 → 7: 000 и 111 дают биты (1, 1, 1), сумма = 3 ≥ 2 - портал существует.

Рассмотрим подробнее, как применяется правило операций к отдельным битам на примере ребра 0 → 1.

x = 0 = 000
y = 1 = 001

1-й бит: x₀ ^ y₀ = 0 ^ 1 = 1
2-й бит: x₁ ^ y₁ = 0 ^ 0 = 0
3-й бит: 1

Сумма битов = 1 + 0 + 1 = 2 ≥ p

Так как сумма не меньше p = 2, портал между измерениями 0 и 1 существует.

Аналогично существуют портал 1 → 7, поэтому возможен путь 0 → 1 → 7.

Всего имеется как минимум три рёберно-непересекающихся пути (0→7, 0→1→7, 0→2→7), а альтернативных Риков k = 2. Рик может выбрать свободный маршрут.

Ответ: Yes

Пояснение к примеру 2

Здесь измерения - 2-битные числа. Рик идёт из 0 (00) в 3 (11).

• 1-й бит результата = первый бит x
• 2-й бит результата = 0

Порог p = 1, поэтому портал возможен только если старший бит x равен 1.

У стартового измерения 0 (00) старший бит равен 0, следовательно, из него невозможно открыть ни одного портала.

Путь из s в t отсутствует.

Ответ: No

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

Вывести Yes, если Рику возможно незамеченным перейти из s в t.

Вывести No, если это невозможно.

Ограничения

1 ≤ n ≤ 30
0 ≤ s, t ≤ 2^n − 1
0 ≤ k ≤ 2^n − 1
0 ≤ p ≤ n

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

3
0 7
2
x ^ y
x ^ y
1
2

Yes

2
0 3
1
x
0
1

No

Задача z8. Force Choke Optimizer ≡

Условие

Гранд-мофф Таркин получил приказ от Императора установить тотальный контроль над гиперпространственными маршрутами в Внешнем Кольце. Разведка донесла, что повстанцы активно используют сеть из N планет, соединённых M гиперпространственными маршрутами, для переброски оружия и диверсантов.

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

Гравитационный колодец

Бюджет операции ограничен: Звезда Смерти требует колоссальных ресурсов. Однако Дарт Вейдер лично прибудет с инспекцией через неделю. Если лорд ситхов обнаружит, что количество гарнизонов превышает теоретический минимум (минимальное количество гарнизонов, перекрывающих все маршруты) более чем в два раза, Таркина ждёт Force choke и немедленная отставка.

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

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

В первой строке входных данных подаются два целых числа: N — количество планет в секторе (1 ≤ N ≤ 10⁵) и M — количество гиперпространственных маршрутов между ними (0 ≤ M ≤ 2 ⋅ 10⁵).

В следующих M строках содержится описание маршрутов. Каждая строка содержит два целых числа u и v (1 ≤ u, v ≤ N, u ≠ v) — номера планет, соединённых маршрутом. Между двумя планетами может быть не более одного маршрута.

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

В первой строке выведите K — количество размещённых гарнизонов. Во второй строке через пробел выведите K различных целых чисел — номера планет, на которых Таркину необходимо разместить имперские гарнизоны. Если существует несколько вариантов дислокации, выведите любой из них.

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

4 3
2 3
1 2
3 4

2
2 3

5 4
1 2
1 3
1 4
1 5

1
1

Задача z9. Война матриц ≡

Условие

В качестве шифрования для передачи данных между штабами было принято использовать метод умножения матриц Штрассера. Берётся некоторая матрица B, известная всем штабам. Секретные данные записываются числами в некоторую матрицу A. Данные матрицы умножаются по методу Штрассера и записываются все M₁, M₂, ..., M₇, используемые в методе Штрассера. Данные M передаются в другой штаб, где их уже расшифровывают. Однако в ходе операции врага часть данных может не дойти до базы.

Ваша задача — написать дешифратор, который по матрице B и неполным M должен найти матрицу A. Причём элемент матрицы A равен числу только в том случае, если он однозначно определяется M. В противном случае на его место выводится символ "_". Для создания M используется следующий код:

def split(A):
    n = A.shape[0]
    k = n // 2
    return A[:k, :k], A[:k, k:], A[k:, :k], A[k:, k:]


def strassen(A, B):
    if A.shape[0] == 1:
        return A * B

    A11, A12, A21, A22 = split(A)
    B11, B12, B21, B22 = split(B)

    M1 = strassen(A11 + A22, B11 + B22)
    M2 = strassen(A21 + A22, B11)
    M3 = strassen(A11, B12 - B22)
    M4 = strassen(A22, B21 - B11)
    M5 = strassen(A11 + A12, B22)
    M6 = strassen(A21 - A11, B11 + B12)
    M7 = strassen(A12 - A22, B21 + B22)

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

Первая строка содержит целое число t, где 2^t — размер квадратных матриц A и B. Далее идут 2^t строк, содержащие матрицу B. Затем идут 7^t-1 строк, содержащие все значения M₁, …, M₇, где каждый элемент либо целое число, либо "_".

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

Ограничения

1 <= t <= 5

0 <= bᵢⱼ <= 50

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

1
49 48
15 7
_ 3430 _ -1428 308 _ -880

42 2
28 42

2
14 41 48 42
27 28 45 8
9 18 33 1
0 43 18 15
11340 4700 -65 -122 4687 -2314 -1496
5166 1596 806 793 3500 -495 110
408 450 1632 204 -371 -1176 40
750 -350 -1178 -968 840 140 228
5040 3630 -616 -915 1260 170 -693
-294 868 -141 0 576 2465 2052
-2100 420 819 0 -1450 1891 -304

34 19 10 21
13 17 36 44
31 38 31 25
27 17 26 44