графы

144 задачи
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Closing the Farm#89966
Фермер Джон и его коровы планируют уехать на длинные каникулы, и поэтому ФД хочет временно закрыть ферму.

Ферма состоит из \(N\) амбаров, соединённых \(M\) двунаправленными дорожками между некоторыми парами амбаров (\(1 \leq N, M \leq 200,000\)). ФД закрывает один амбар за раз. После того как амбар закрыт, все дорожки, прилегающие к нему тоже становятся закрытыми и не могут больше использоваться.

ФД хочет знать в каждый момент времени (изначально и после каждого закрытия), является ли его ферма "полностью связной" - то есть возможно ли добраться от одного открытого амбара до любого другого открытого амбара с помощью серии дорожек. Поскольку на ферме идёт ремонт, она может быть не связной даже изначально.

ФОРМАТ ВВОДА (файл closing.in):

Первая строка ввода содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк описывает дорожку , задавая пару амбаров, которые она соединяет (амбары пронумерованы последовательно \(1 \ldots N\)). Последние \(N\) строк задают перестановку \(1 \ldots N\) описывающую порядок, в котором будут закрываться амбары.

ФОРМАТ ВЫВОДА (файл closing.out):

Вывод содержит \(N\) строк, каждая есть "YES" или "NO". Первая строка отвечает на попрос была ли ферма полностью связанной изначально, а далее строка \(i+1\) указывает, осталась ли ферма полностью связной после \(i\)-го закрывания.

графыПоиск компонент связностиснм
—Войти и решать
Bessie's Birthday Buffet#89960
Фермер Джон подарил корове Беси на день рождения одно из лучших полей.

Поле покрыто \(N\) областями травы (\(1 \le N \le 1000\)), последовательно пронумерованных \(1\ldots N\), имеющих различные показатели качества. Если Беси ест трау с качеством \(Q\), она получает \(Q\) единиц энергии. Каждая область соединена максимум с 10 соседними областями двунаправленными дорожками, и Беси требуется \(E\) единиц энергии чтобы перейти на соседнюю область (\(1 \le E \le 1,000,000\)). Беси может выбрать в качестве начала поедания любую область, которую пожелает, Она заканчивает поедание, когда соберёт максимальное количество энергии.

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

Пожалуйста, определите максимальное количество энергии, которое может собрать Беси.

ФОРМАТ ВВОДА (файл buffet.in):

Первая строка ввода содержит \(N\) и \(E\). Каждая из последующих \(N\) Строк описывает область травы двумя целыми числами \(Q\) и \(D\) определяющими качество травы (в диапазоне \(1\ldots 1,000,000\)) и количество ей соседей, оставшиеся \(D\) чисел указывают её соседей.

ФОРМАТ ВЫВОДА (файл buffet.out):

Выведите максимальное количество энергии, которое может собрать Беси.

ПР�МЕР ВВОДА:

5 2

4 1 2

1 3 1 3 4

6 2 2 5

5 2 2 5

2 2 3 4

ПР�МЕР ВЫВОДА:

7

Беси начинает в области 4, собирает 5 единиц энергии, затем она перемещается в область 5, теряя 2 единицы энергии во время перехода. Затем она отказывается есть траву более низкого качества в области 5 и переходит в область 3 опять теряя 2 единицы энергии. Там она получает +6 единиц энергии, поедая траву. Всего у неё становится 7 единиц энергии.

графы
—Войти и решать
Dueling GPSs#89949

Фермер Джон недавно купил новую машину с двумя навигационными
системами GPS. Что ещё хуже, они часто конфликтуют при выборе
Маршрута.

Карта региона, в котором живёт ФД представляет собой N перекрёстков
(2 <= N <= 10,000) и M двунаправленных дорог (1 <= M <= 50,000).
Дорога I соединяет перекрёстки Ai (1 <= Ai <= N) и Bi (1 <= Bi <= N).

Множество дорого может соединять одну и ту же пару перекрёстков.
Двунаправленные дороги представлены двумя раздельными
однонаправленными дорогами в противоположных направлениях.

Дом ФД находится в перекрёстке 1, а его ферма распложена в перекрёстке
N. Существует путь из дома на ферму, по серии однонаправленных дорог.

Обе GPS-системы используют карту описанную выше, однако они дают
различные значения времени проезда по каждой дороге. Дорога I
требует Pi единиц времени по первой GPS-системе и Qi единиц времени
по второй (каждая из величин – целое число в интервале 1..100,000).

ФД хочет проехать от дома до фермы. Однако каждая GPS-система громко
оповещает ФД каждый раз, когда ФД выбирает дорогу (например, от
перекрёстка X до перекрёстка Y) которую GPS не считает частью
кратчайшего пути от X до фермы (возможно даже что предупреждение
выдают обе GPS-системы, если ФД выбирает дорогу, которую каждая из
GPS считает не принадлежащей к кратчайшему маршруту).

Пожалуйста, помогите ФД определить минимальное количество предупреждений,
которое он может получить соответствующим выбором маршрута.
Если две SPS-системы предупреждают одновременно, к ответу в этом случае
нужно прибавлять число 2.

PROBLEM NAME: gpsduel

Формат ввода:

* Строка 1: целые числа N и M.
* Строка 2-N+1: Строка i описывает дорогу i четырьмя
целыми числами: Ai Bi Pi Qi.

Примечание

Всего имеется 5 перекрёстков и 7 однонаправленных дорог. Первая
дорога идёт от перекрёстка 3 к перекрёстку 4, первая GPS считает,
что нужно 7 единиц времени для проезда по этой дороге, а вторая GPS
- полагает, что требуется одна единица времени.

Формат вывода:

* Строка 1: Минимальное количество предупреждений, которое
может получить ФД при оптимальном проезде от дома до фермы.

Примечание

Если ФД выберет путь 1 -> 2 -> 4 -> 5, тогда первая GPS пожалуется на
дороге 1->2 (она предпочитает путь 1>3). Однако в остальной части маршрута
2 -> 4 -> 5, обе GPS промолчат, поскольку обе считают такой маршрут
кратчайшим от 2 до 5.

Алгоритм Дейкстрыграфыкратчайшие пути
—Войти и решать
Cow Optics#89947

Коровы Фермера Джона хотят провести вечеринку с лазерным шоу. К несчастью, единственный работающий лазер очень тяжёлый и находится далеко. Поэтому они хотят перенаправить его луч с помощью серии зеркал.
Лазер находится в позиции (0,0), а вечеринка – в позиции (Bx,By), Оба рассматриваются как точки на 2D-плоскости. Имеется N (1 <= N <= 100,000) коров, которые держат зеркала под углом 45 градусов к осям координат. Например, зеркало вида \ означает что луч лазера войдёт снизу и отразится влево. Зеркала также рассматриваются как точки на 2D-плоскости.
Прежде чем активировать лазер, Беси поняла, что при имеющейся конфигурации зеркал лазер не попадёт в вечеринку. Она планирует добавить ещё одно зеркало, Тоже под углом 45 градусов, чтобы лазер попал в вечеринку. Пожалуйста, подсчитайте количество мест, в которые Беси может поставить такое одно зеркало, чтобы лазер попал в вечеринку.
Все координаты – целые числа между -1,000,000,000 и 1,000,000,000. Гарантируется, что любое зеркало, которое будет ставиться, также находится в этом диапазоне. Луч никогда не должен вернуться в точку (0,0). Для начальной конфигурации зеркал это гарантируется. Никакие два зеркала не находятся в одной точке пространства и Беси тоже не может ставить своё дополнительное зеркало в позицию, где зеркало уже стоит.
PROBLEM NAME: optics
Формат ввода:
* Строка 1: Целые числа N, Bx, By.
* Строки 2..N + 1: Строка i+1 описывает i-ое зеркало 3 величинами: (x,y) - координатами, и ориентацией ('\' или '/').
Примечание
Зеркала в точках (0,1) и (0,2) решат проблему.
графы
—Войти и решать
Code Breaking#89946

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой. Она организована как корневое дерево из N (1 <= N <= 20,000) вершин, каждая из которых требует цифру от 0 до 9. Вершины пронумерованы от 0 до N-1.
Единственная информация, которой владеют коровы – что определённая последовательность длины 5 не случается на путях в этом дереве.
Например, предположим, то дерево выглядит так (с корнем в A):
A <- B <- C <- D <- E ^ | F
Коровы могут знать, что последовательность 01234 не случится начиная от F, И что последовательность 91234 не случится, начиная от E. Эта информация приводит к тому, что возможными остаются 19 паролей, все такого вида:
The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form
4 <- 3 <- 2 <- 1 <- * ^ | 0
или
4 <- 3 <- 2 <- 1 <- 9 ^ | *
Что даёт 19 паролей, поскольку такой
4 <- 3 <- 2 <- 1 <- 9 ^ | 0
появится дважды
По заданным M (1 <= M <= 50,000) последовательностям длины 5, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет подходить. Вы должны выводить свой ответ по модулю 1234567.

PROBLEM NAME: code
Формат ввода:
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..N: Строка i+1 содержит одно целое число p(i), означающее родителя вершин I в дереве (0 <= p(i) < i).
* Строки N+1..N+M: Строка N+i описывает i-ую последовательность про которую известно, что она не произойдёт в коде. Строка содержит v(i) и s(i), разделённые пробелом. Здесь v(i) - стартовая вершина последовательности, s(i) – строка из 5 цифр, которая не встретится в шифре начиная с вершины v(i) если двигаться вверх по дереву. Гарантируется, что корень дерева находится не менее чем в 4 шагах от v(i).

Вывод формулыграфыДеревья
—Войти и решать
Decorating the Pastures#89943

У Фермера Джона имеется N (1 <= N <= 50,000) пастбищ, последовательно пронумерованных от 1 до N, соединённых M (1 <= M <= 100,000) двунаправленными дорогами. Дорога I соединяет пастбища Ai (1 <= Ai <= N) и Bi (1 <= Bi <= N), Ai != Bi. Возможны две дороги соединяющие одну и ту же пару пастбищ.
Беси хочет украсить пастбища к дню рождения ФД. Она хочет разместить на каждом пастбище огромный знак содержащий либо букву ‘F’ либо букву ‘J’, но чтобы не огорчать ФД, должно быть выполнено правило, Пастбища декорируются разными знаками, если они соединены дорогой.
Компания, изготавливающая знаки, требует больше денег за знак ‘F’ и меньше денег за знак ‘J’, поэтому Беси хочет максимизировать количество знаков ‘J’, которые она использует. Пожалуйста, определите это число или выведите -1, если невозможно расставить знаки по описанным правилам.
uses. Please determine this number, or output -1 if there is no valid way to arrange the signs.
PROBLEM NAME: decorate
Формат ввода:
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Два целых числа, Ai и Bi указывающих наличие двунаправленной дороги между пастбищами Ai и Bi.
Примечание
Пастбища и дороги представляют собой вершины и стороны квадрата.
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальное количество знаков ‘J’ которые сможет использовать Беси. Если нет решения, то выводить -1.
Примечание
Беси может пометить пастбища 1 и 3 знаком ‘J’ (или альтернативно - пастбища 2 и 4).
графыпоиск в глубину и подобноеПоиск компонент связности
—Войти и решать
Counting Friends#89937

N коров Фермера Джона (2 <= N <= 500) объединились в социальную сеть "MooBook". Каждая корова имеет одну или более подружек с которой контактирует в MooBook. ФД сделал список, содержащий для каждой коровы количество её подружек, однако по ошибке он включил в список одно лишнее число и его список содержит N+1 число вместо планировавшихся N чисел.
Пожалуйста, помогите ФД определить какое число в этом списке является лишним – то есть внесённым по ошибке.
PROBLEM NAME: fcount
Формат входных данных
* Строка 1: Одно целое число N.
* Строки 2..2+N: Строка i+1 содержит количество подружек для одной из коров ФД или возможно неправильное лишнее число.
Формат выходных данных
* Строка 1: Целое число K, определяющее количество возможных ошибочного чисел, или 0, если не существует числа в этом списке, удаление которого нарушило бы парность друзей.
* Строки 2..1+K: Каждая строка содержит индекс от 1 до N+1 числа во входной нумерации чисел, которое потенциально может быть лишним числом, поскольку это число может быть удалено и оставшиеся N чисел определяют допустимое множество отношений дружбы между оставшимися коровами. Эти строки должны быть в отсортированном порядке.
Примечание
Удаление первого числа (число 1) оставляет в списке числа 2 2 3 1. Если обозначить коров символами от A до D, то при отношении дружбы заданном парами (A,B), (A,C), (A,D), (B,C) мы получим что у коровы A 3 подружки, у коров B и С по 2 подружки, а у D – 1 подружка. Аналогично при удалении другой 1 и при удалении 3. Удаление числа 2 невозможно – сумма оставшихся чисел нечётна, из чего с очевидностью следует невозможность составить пары.
графы
—Войти и решать
Reordering the Cows#89935

N (1 <= N <= 100) коров Фермера Джона, последовательно пронумерованных от 1 до N, стоят в ряд. Их порядок описан массивом A, где A(i) это номер коровы на позиции i. ФД реорганизовать их в другом порядке, описанном в массиве B, где B(i) – номер коровы, которая должна оказаться на позиции i.
Например, предположим, что изначальный порядок таков:
A = 5 1 4 2 3
И предположим, что ФД хочет переупорядочить их так:
B = 2 5 3 1 4
Переупорядочивание от “A” к “B” осуществляется посредством некоторого количества «циклических» сдвигов. Каждый такой циклический сдвиг начинается с коровы, которая перемещается на свою позицию в “B”-порядке, замещая корову, которая затем движется на свою позицию и т.д, пока какая-то корова не попадёт в место, которая занимала первая корова в этом цикле.
Например, для данных, описанных выше, мы начинаем цикл с коровы 5, которая должна переместиться на позицию 2, замещая корову 1, которая перейдёт на позицию 4, замещая корову 2, которая перейдёт на позицию 1, завершая цикл.
Коровы продолжают выполнять циклические сдвиги, пока все коровы не окажутся на своём месте, определённом B-упорядочиванием.
Пожалуйста, вычислите количество различных циклических сдвигов, а также длину наибольшего циклического сдвига, во время такого переупорядочивания коров.
PROBLEM NAME: reorder
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит целое число A(i).
* Строки 2+N..1+2N: Строка 1+N+i содержит целое число B(i).
Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, первое даёт количество циклических сдвигов, второе даёт количество коров, которые поучаствовали в самом длинном сдвиге. Если нет циклических сдвигов, выведите -1 в качестве второго числа.
Примечание
Всего имеется два циклических сдвига, один включает коров 5 1 2, а второй включает коров 3 4.
графы
—Войти и решать
Cross Country Skiing#89932

Лыжная трасса описана решёткой из M x N высот (1 <= M,N <= 500), каждая из высот в диапазоне 0 .. 1,000,000,000.
Некоторые из этих ячеек обозначены как точки маршрута гонки. Организаторы хотят назначить маршруту рейтинг трудности D так, чтобы корова могла попасть в любую точки маршрута из любой другой точки маршрута, последовательно перемещаясь между соседними ячейками, абсолютная разность высот которых не превышает D. Две ячейки считаются соседними, если они граничат по стороне (в направлении на север, юг, запад или восток одна от другой). Рейтинг трудности маршрута это минимальное значение D такое, что все точки маршрута взаимно достижимы при выполнении вышеописанного требования.
PROBLEM NAME: ccski
Формат входных данных
* Строка 1: Целые числа M и N.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин 0 или 1, 1 указывает, что данная высота – точка маршрута гонки.

Формат выходных данных
* Строка 1: Рейтинг трудности маршрута (минимальное значение D такое, что все точки маршрута взаимно достижимы)
Примечание
Если D = 21, то все 3 точки маршрута взаимно достижимы. Если D<21 верхняя правая точка не достижимы из других двух.

Бинарный поиск по ответуграфыОбход в ширину
—Войти и решать
Ski Course Rating#89930

Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.
Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет успешно достичь как минимум T ячеек решётки (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D.
Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.
PROBLEM NAME: skilevel
Формат входных данных
* Строка 1: Целые числа M, N, T.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка

Формат выходных данных
* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).


Примечание Рейтинг трудности верхнего левого угла равен 4. Рейтинг трудности правого нижнего угла равен 20.

графы
—Войти и решать
Roadblock#89923
Problem 2: Roadblock [Brian Dean]
Каждое утро Фермер Джон по ферме от своего дома к амбару. Ферма это коллекция из N полей (1<=N<=250), соединённых M двунаправленными дорожками (1<=M<=25,000) определённой длины. Дом фермера находится на поле 1, а амбар – на поле N. Никакие два поля не соединены более чем одной дорожкой. И существует путь (как последовательность дорожек) из любого поля к любому. Перемещаясь от поля к полю, ФД всегда выбирает маршрут, состоящий из последовательности дорожек, имеющих наименьшую общую длину. Коровы «вредничают». Они планируют построить стог сена ровно на одной из M дорожек, тем самым увеличив вдвое её длину. Коровы хотят выбрать такую дорожку, чтобы максимизировать увеличение маршрута ФД от дома к амбару. Помогите коровам определить, насколько они могут удлинить маршрут ФД.
PROBLEM NAME: rblock
Формат входных данных
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..1+M: Строка j+1 описывает j-ую двунаправленную дорожку тремя разделёнными пробелами числами Aj Bj Lj, где Aj и Bj это числа в диапазоне1..N, указывающие поля, соединённые этой дорожкой, а L – длина этой дорожки (в диапазоне 1...1,000,000).
Формат выходных данных
* Строка 1: Максимально возможное увеличение длины кратчайшего маршрута ФД, которого можно достичь удвоением длины одной дорожки.
Примечание
Если коровы удвоят длину дорожки из поля 3 в поле 3 (от 3 до 6), тогда кратчайший маршрут ФД станет 1-3-5 с длиной 1+7=8, что увеличивает на 2 первый кратчайший путь.
графыкратчайшие путиреализация
—Войти и решать
Yin and Yang#89912

Фермер Джон планирует утренную прогулку по ферме. Ферма имеет структуру как дерево: имеется N амбаров (1 <= N <= 100,000), которые соединены N-1 дорожками по которым можно ойти о одного амбара в другой. ФД хочет выбрать путь, который начнется и закончится в различных амбарах, так чтобы не проходить ни по какой дорожке дважды. Поскольку путь может оказаться слишком длинным, он хочет определить "амбар отдыха", который лежит на пути и отличается от стартового и конечного амбаров.
Вдоль каждой дорожки гуляет стадо белых или стадо черных коров. Поэтому ФД хочет выбрать такой путь, чтобы он прошел одинаковое количество белых и черных стад в обоих случаях - и на пути от старта к "амбару отдыха", и на пути от "амбара отдыха" к финишу.
ФД интересуется сколько существует различных путей, обладающих свойствами, описанными выше. Два пути различаются, если они содержат различные множества дорожек. Путь должен считаться один раз, даже если может быть множество "амбаров отдыха" на этом пути. Вычислите это количество для ФД.
PROBLEM NAME: yinyang
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..N: Три целых числа ai, bi и ti, представляющих два амбара, которые соединяет эта дорожка. t0 равно 0 если вдоль дорожки пасутся белые коровы и 1, если черные.
Формат выходных данных
* Строка 1: Одно целое число, представляющее количество возможных путей ФД
Примечание
Никакой из путей длины 2 не имет подходящегоамбара для остановки. Поэтому должны рассматривать только пути длины 4. Единственный подходящий путь 3-1-2-5-7 с остановкой в 2.
графы
—Войти и решать
Hill Walk#89891

Имется N (1 <= N <= 100,000) холмов. Каждый холм имеет форму отрезка из точки (x1, y1) в точку (x2, y2) где x1 < x2 и y1 < y2. Никакие из этих отрезков не пересекаются и не касаются даже в конечных точках. Кроме того, для первого холма справедливо (x1,y1) = (0,0).
Беси начинает свой путь в точке (0,0) на первом холме. Когда Беси попадает на холм, она карабкается вверх пока не достигнет конца холма. Затем она прыгает вниз. Если она приземлится на другой холм, она продолжит карабкание уже на этом холме, иначе она падает в бездну (где y=-бесконечности). Каждый холм (x1, y1) -> (x2, y2) необходимо рассматривать как содержащий точку (x1, y1), но не содержащий точку (x2, y2), поэтому Бэси приземляется на холм, если она падает на него сверху с позиции x = x1, но не приземлится на него, если она падает сверху с позиции x = x2.
Посчитайте общее количество холмов, которых Беси коснется в некоторой точке во время своего путешествия.
PROBLEM NAME: hillwalk
Формат входных данных
* Строка 1: Количество холмов, N.
* Строки 2..1+N: Строка i+1 содержит четыре целых числа (x1,y1,x2,y2) описывающих холм i. Каждое целое число находится в диапазоне 0..1,000,000,000.
Формат выходных данных
* Строка 1: Количество холмов, которых коснется Беси за время своего путешествия.
Примечание
Беси пройдется по холмам #1, #4, #3.
геометрияграфыреализация
—Войти и решать
Breed Assignment#89888

У фермера Джона имеется N (2 <= N <=15) коров трех различных пород:
Holsteins, Jerseys, Guernseys.

Однако ФД помнит о породах специфически, а именно он помнит список из K
(1 <= K <= 50) отношений между парами коров. Например, он может помнить,
что коровы 1 и 2 одинаковой породы, или, что коровы 1 и 5 разной породы.

Вам дан этот список ФД, помогите ему вычислить количество различных
назначений пород его коровам. Это число может равняться нулю, если
его список содержит противоречивую информацию.

PROBLEM NAME: assign

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

* Строка 1: Два разделенных пробелом целых числа: N и K.

* Строки 2..1+K: Каждая строка описывает отношение между парой коров
x и y (1 <= x,y <= N, x != y) в одной из форм
"S x y", означающей, что коровы x и y одной и той же породы, или
"D x y", означающей, что коровы x и y различных пород.

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

* Строка 1: Количество возможных назначений пород.

Примечание

Следующие 6 назначений возможны для первых трех коров:
HHG, HHJ, GGH, GGJ, JJH, JJG.
В каждом из этих вариантов мы имеем 3 возможных назначения
для 4-ой коровы, поэтому и получается всего 18 вариантов.

графы
—Войти и решать
Party Invitations#89886

Фермер Джон организовывает вечеринку для своих коров. Но он хочет пригласить минимальное их количество.
Коровы имеют группы друзей, скажем размера k. И тогда если ФД пригласил k-1 корову из группы, он должен пригласить и оставшуюся k-ую корову из группы.
Группы могут быть любого размера и могут перекрываться. В то же время, никакие две группы не содержат точно одно и то же множество коров. Сумма всех рамзеров групп коров не превысит 250,000.
По заданным группам коров определите минимальное количество коров, которое ФД может пригласить на вечеринку, если он определенно решит пригласить корову с номером 1 (все коровы пронумерованы последовательно, от 1 до N, N<=1,000,000).

PROBLEM NAME: invite
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N (количество коров), и G (количество групп).
* Строки 2..1+G: Каждая строка описывает группу коров. Она начинается с целого числа - размера группы S, за которым следуют S номеров коров в этой группе (все целые числа в диапазоне от 1 до N).
Формат выходных данных
* Строка 1: Минимальное количество коров, которое ФД может пригласить на вечеринку.
Примечание
В дополнение к корове 1 ФД должен пригласить корову 3 (по первой группе), корову 4 (по второй группе), корову 2 (по 4-ой группе).

графы
—Войти и решать
Island Travels#89883

Фермер Джон отвез саоих коров на океан. Коровы живут на N (1<=N<=15) островах, которые расположены на решетке R x C (1 <= R, C <= 50). Остров - это максимальная связная группа квадратов на решетке, помеченная символами 'X', где два 'X' связны, только если они имеют общую сторону. Квадраты имеющие общий угол, не обязательно связны.
Беси опоздала, она прилетела с ФД на вертолете. Она может приземлиться на любом острове. Она хочет посетить все N островов хотя бы один раз.
Вокруг островов находится мелководье (обозначено буквой 'S'). Беси может плыть по нему в четырех направлениях (север, юг, запад, восток) для того, чтобы путешествовать между островами. Она также может путешествовать между островом и мелководьем и наоборот.
Определите минимальное расстояние, которое Беси должна проплыть, чтобы посетить все острова (гарантируется, что это возможно). Расстояние, которое проплывет Беси, равно количеству различных раз, когда Беси посетит клеточку 'S'.
PROBLEM NAME: island
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: R и C.
* Строки 2..R+1: Строка i+1 содержит C символов, определяющих i-ую строку решетки. Глубокая вода обозначена '.', острова 'X', мелководье 'S'.
Формат выходных данных
* Строка 1: Одно целое число, представляющее минимальное расстояние, которое должна проплыть Беси, чтобы посетить все острова.
Примечание
Бэси может проплыть от левого верхнего сотрова к среднему, проплыв 1 клеточку, а затем от среднего острова к правому нижнему, проплыв 2 клеточки - всего 3.
графыМинимальный каркасОбход в ширину
—Войти и решать
Liars and Truth Tellers#89879

Среди N коров (2 <= N <= 1000) Фермера Джона некоторые всегда говорят правду, а некоторые всегда лгут.
ФД выслушал M утверждений (1 <= M <= 10,000) своих коров, каждое в форме "x y T", обозначающей, что корова x утверждает, что корова y всегда говорит правду или в форме "x y L", обозначающей, что корова x утверждает, что корова y всегда лжет.
Каждое утверждение вовлекает пару различных коров и одна и та же пара коров может появится во множестве утверждений.
К несчастью, не все записи утверждений были сделаны правильно. И теперь ФД хочет вычислить наибольшее A такое, что существует корректное распределение коровам статуса "лжеца" и "правдоруба", так, чтобы оказались корректными первые A высказываний из списка ФД.
PROBLEM NAME: truth
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M.
* Строки 2..1+M: Каждая строка в форме "x y L" или "x y T", описывающее утвеждение сделанное коровой x о корове y.
Формат выходных данных
* Строка 1: Максимальное значение A такое, что первые A утвеждений из списка могут ьыть корректны при определенном назначении N коровам статусов "лжец", "правдец".
Примечание
Утверждения 1 и 3 противоречивы всегда, а утверждения 1 и 2 могут быть непротиворечивы, если мы назначим коров 1..3 - "правдецами", а корову 4 - лжецом.
графы
—Войти и решать
Perimeter#89877

Фермер Джон выстроил N (1 <= N <= 50,000) стогов сена в одном из своих полей. Мы рассмотрим это поле как решетку 1,000,000 x 1,000,000 из квадратных ячеек 1 х 1, где каждый стог сена занимает ровно одну ячейку. Никакие два стога не находятся в одной и той же ячейке.

ФД заметил, что его стоги всегда образуют один большой связный регион, что означает, что начиная с любого стога сена можно достичь любого другого стога сена с помощью серии шагов в строго соседнюю клетку в одном из четырех направлений: север, юг, запад, восток.
Однако этот связный регион может содержать "дыры" - пустые регионы, которые полностью окружены стогами.
Помогите ФД определить периметр региона, сформированный его стогами. Учитывайте, что дыры не вносят вклад в периметр.
PROBLEM NAME: perimeter
Формат входных данных
* Строка 1: Количество стогов, N.
* Строки 2..1+N: Каждая строка содержит(x,y) - положение одного стога где x и y целые числа в диапазоне 1..1,000,000. Позиция (1,1) это левый нижний угол поля ФД, а позиция (1,000,000,1,000,000) это правый верхний угол поля.
Формат выходных данных
* Строка 1: периметр связного региона стогов.
Примечание
Длина периметра равна 14, например левая сторона имеет длину 3. Заметьте, что дыра в середине не вносит значение в периметр.

графы
—Войти и решать
Message Relay#89871

N (1 <= N <= 1000) коров Фермера Джона последовательно пронумерованы от 1 до N. Коровы хотят переговариваться друг с другом с помощью жестяных банок и проводов.
Каждая корова может послать сообщение не более чем одной другой корове: для коровы i значение F(i) указывает Вам индекс коровы, которой корова i может послать любое сообщение, которое она получит (это число всегда отличается от i). Если F(i) равно 0, то эта корова не может переслать сообщение никому.
К несчастью, существует возможность что сообщение посланное некоторой коровой, будет ходить по кругу бесконечно. Корова называется "циклической", если сообщение, посланное этой коровой, попадает в бесконечный цикл. Коровы хотят избежать посылок сообщений от циклических коров. Пожалуйста, помогите им, подсчитв общее количество нециклических коров.
PROBLEM NAME: relay
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Строка i+1 содержит значение F(i).

Формат выходных данных
* Строка 1: Общее количество нециклических коров.
Примечание
Корова 1 нециклическая, поскольку она не пересылает сообщения. Корова 3 также нециклическая, поскольку она пересылает сообщения корове 1, которая не пересылает сообщений. Все остальные коровы циклические.

графы
—Войти и решать
Unlocking Blocks (Silver)#89860

Коровы любят головоломки. Фермер Джон подарил Беси на день рождения новую головоломку. Она состоит из трех твердых объектов, каждый из которых состоит из склеенных вместе квадратиков размера 1 х 1. Каждый из этих объектов имеет «связную» форму в том смысле, что Вы можете перейти из одного квадратика в любой другой, двигаясь по квадратикам этого объекта в одном из четырех направлений: север, юг, запад, восток.
Объект может перемещаться последовательно скольжением на одну единицу в одном из четырех направлений: север, юг, запад, восток. Цель головоломки - переместить объекты так, чтобы они разделились – то есть, чтобы граничные квадратики отошли друг от друга. Ваша задача – по заданным трем объектам определить, можно их разделить, или нет. Конфигурация, которую разделить нельзя, называется заблокированной.

Замечание: программы, которые не делают ничего, кроме угадывания ответа, могут быть дисквалифицированы.
PROBLEM NAME: unlock
Формат входных данных
* Строка 1: Три разделенных одиночными пробелами целых числа: N1, N2, and N3, описывающих количество квадратов соответственно в фигурах 1, 2, и 3.
* Строки 2..1+N1: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
* Строки 2+N1..1+N1+N2: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 2. Все координаты в интервале 0..9.
* Lines 2+N1+N2..1+N1+N2+N3: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
Формат выходных данных
* Строка 1: Минимальное количество шагов, которое необходимо выполнить, чтобы разделить три объекта или -1, если объекты не могут быть разделены.
Примечание
Если мы сдвинем объект 3 на 4 позиции на восток, а затем объект 2 на одну позицию на север и затем на 3 позиции на восток, то границы трех фигур разъединятся.

графыЗадачи на моделированиеОбход в ширину
—Войти и решать
Поделиться
Класснуть