Страница: << 27 28 29 30 31 32 33 >> Отображать по:

#1693

Бюрократия

Темы: [Обход в глубину]

Некогда гордая и свободолюбивая республика Акадия совсем погрязла в коррупции. Депутаты покупают и перепродают голоса друг друга, чтобы затем принять или отклонить какие-то законы. К принятым законам довольно быстро появляются поправки, их аннулирующие. Эти поправки, в свою очередь, аннулируются следующими поправками, и так далее. Секретарь премьер-министра хочет разобраться, какие законы в данный момент действуют, а какие нет.

С незапамятных времён в Акадии всего два типа законов:

* прямой закон, устанавливающий новые правовые нормы;
* поправка, аннулирующая какой-то из предыдущих законов.
Закон считается действующим тогда и только тогда, когда нет действующего закона, который бы являлся поправкой, его аннулирующей.

В распоряжении секретаря — все законы Акадии с момента становления республики в порядке их принятия. Помогите ему выяснить, какие из законов — действующие.

Входные данные

В первой строке ввода записано \(n\) (1 \(\le\) \(n\) \(\le\) 100000) — количество принятых законов.

Следующие \(n\) строк описывают сами законы. Каждое описание имеет следующий вид:

* «declare», если данный закон — это прямой закон.
* «cancel i», если данный закон — это поправка, аннулирующая закон с номером \(i\).

Законы нумеруются, начиная с единицы.

Выходные данные

В первой строке вывода выведите одно число — количество действующих законов. Далее выведите номера всех действующих законов в порядке возрастания.

Примеры

Входные данные

5
declare
cancel 1
declare
cancel 2
cancel 3

Выходные данные

3
1 4 5

#1701

Модель Крипке

Темы: [Обход в глубину]

Тестирование и контроль качества являются чрезвычайно трудоемкими этапами разработки ПО. Для облегчения этой задачи используются несколько различных техник. Одна из них называется верификацией. Model checking — верификация на базе модели Крипке.

Модель Крипке представляет собой набор \((P, S, R, L)\), где \(P\) – конечное множество высказываний, \(S\) — конечное множество состояний модели, \(R \in SxS\) – переход из одного состояния в другое. \(L \in SхP\) – отношение истинности (высказывание \(P\) в состоянии \(S\) истинно).

Отношение \(R\) будем считать рефлексивным, т.е. \(R(S, S)\) всегда существует.

Набор состояний π, начинающийся в состоянии s, представляет собой бесконечную последовательность состояний \(s_0, s_1,...,\) такую что \(s_0 = s\) и для любого \(i ≥ 0\) выполнено \((s_i s_{i+1})\) представляет собой переход.

В данной модели существует кванторы, применяемые к наборам и к состояниям, с помощью которых образуются формулы (элементарная формула, это высказывание, оно выполняется во всех своих истинных состояниях).

Af выполняется в состоянии \(s\), если формула \(f\) выполняется для каждого набора, начинающегося в состоянии \(s\);
Ef выполняется в \(s\), если существует набор, начинающийся в состоянии \(s\), в котором формула \(f\) выполняется.
Если \(f\) и \(g\) формулы, то
Gf (Globally) выполняется для набора \(s_0s_1…,\) если для любого \(i ≥ 0\) формула \(f\) выполняется в состоянии \(s_i\);
fUg (Until) выполняется для набора \(s_0s_1…,\) если существует такое \(i ≥ 0\), что \(f\) выполняется для всех состояний \(s_0;s_1;…; si-1,\) и \(g\) выполняется в состоянии \(s_i\).

Проверить формулу \(f\) – означает найти все состояния, для которых она выполняется. Для произвольной формулы это сделать сложно. Ваша задача проще – проверить формулу E(xU(AGy)), где \(x\) и \(y\) - высказывания.

Входные данные

Первая строка содержит три натуральных числа \(n, m\) и \(k (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 100 000; 1 ≤ k ≤ 26)\) – число состояний, переходов и высказываний. Каждая из следующих \(n\) строк описывает одно из состояний. Состояние \(i (1 ≤ i ≤ n)\) описывается числом \(c_i (0 ≤ c_i ≤ k)\) – количеством высказываний, которые истинны в этом состоянии, затем через пробел перечислены эти высказывания. Сами высказывания обозначаются первыми \(k\) маленькими латинскими буквами.

Следующие \(m\) строк описывают переходы. Каждое описание содержит два числа \(s\) и \(t\)

\((1 ≤ s, t ≤ n; s ≠ t)\) – переход из состояния \(s\) в состояние \(t\). Переходы из \(s\) в \(s\) существуют всегда и во входных данных не отражены. Никакие переходы не упомянуты дважды.

Последняя строка входных данных содержит формулу, которую надо проверить. Она всегда имеет вид E(xU(AGy)), где \(x\) и \(y\) – некоторые высказывания.

Выходные данные

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

Примеры

Входные данные

7 8 2
1 a
1 a
2 a b
1 b
1 b
1 a
1 a
1 2
2 3
3 4
4 5
5 3
2 6
6 7
7 6
E(aU(AGb))

Выходные данные

#1704

Маршрут для гонца

Темы: [Эйлеров цикл]

В королевстве \(N\); городов, пронумерованных от 1 до \(N\). Столица имеет номер 1. Каждый город окружен городской стеной с 4 воротами. Ворота пронумерованы следующим образом: ворота \(i\)-го города (1 \(\le\) \(i\) \(\le\) \(N\)) имеют номера 4\(i\)−3, 4\(i\)−2, 4\(i\)−1, 4\(i\). Через каждые ворота проходит ровно 1 дорога, которая ведет до некоторых ворот другого города (заметьте, что может существовать несколько дорог между двумя городами). По всем дорогам можно двигаться в обоих направлениях. Благодаря системе туннелей и мостов дороги не пересекаются вне городов.

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

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

Входные данные

Первая строка входного файла содержит целое число \(N\) (2 \(\le\) \(N\) \(\le\) 1000). Каждая из последующих 2\(N\) строк описывает одну дорогу и содержит 2 целых числа, разделенных пробелом: номера ворот, соединенных дорогой.

Выходные данные

В первую строку выходного файла выведите Yes или No в зависимости от того, может ли поручение гонца быть выполнено, если проходить через ворота только один раз. В случае если это возможно, вторая строка выходного файла должна содержать 4\(N\) целых чисел, разделенных пробелом: номера ворот в порядке прохождения через них гонцом. Если существует несколько решений, выведите любое из них.

#1721

Кенгуренок Лео

Темы: [Обход в ширину]

#1737

Заправки

Темы: [Алгоритм Флойда] [Алгоритм Дейкстры]

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

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

Входные данные

Во входном файле записано сначала число \(N\) (1 \(\le\) \(N\) \(\le\) 100), затем идёт \(N\) чисел, \(i\)-ое из которых задает стоимость бензина в \(i\)-ом городе (всё это целые числа из диапазона от 0 до 100). Затем идет число \(M\) — количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

Выходные данные

В выходной файл выведите одно число — суммарную стоимость маршрута или −1, если добраться невозможно.

Примеры

Входные данные

4
1 10 2 15
4
1 2 1 3 4 2 4 3

Выходные данные

Страница: << 27 28 29 30 31 32 33 >> Отображать по:

Выбрано

Отменить

Добавить в контест