Задача 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 — количества станций и переходов между станциями соответственно. Далее идут m строк, в каждой из которых указаны три целых числа через пробел:

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

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

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

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

Ограничения

n ≤ 100,

0 ≤ m ≤ n².

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

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

no

Задача 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