Страница: << 1 2 3 >> Отображать по:
#858
Свинки-копилки
  
Подсчет количества циклов в графе, где у каждой вершины ровно одно исходящее ребро.

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

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

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

В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

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

Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Пример

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

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

Комментарий

4

2

1

2

4

2

Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
#859
Трехцветные таблицы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Прямоугольную таблицу, состоящую из N строк и M столбцов, раскрашивают следующим образом. Каждый столбец таблицы и каждую строку красят либо в синий, либо в желтый цвет. В итоге клетки, оказавшиеся на пересечении синего столбца и синей строки оказываются синими, желтого столбца и желтой строки — желтыми, а клетки на пересечении синего столбца и желтой строки, или, наоборот, желтого столбца и синей строки — зелеными.

Раскраска всех клеток таблицы (или просто сама таблица) называется правильной, если она может быть получена описанным выше способом.

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

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

Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:

0 — клетка может в итоге быть любого цвета

1 — клетка должна быть синей

2 — клетка должна быть желтой

3 — клетка должна быть зеленой

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

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

Примеры

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

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

3 4

1 0 0 0

3 0 0 0

0 0 0 0

16

2 2

3 3

3 3

1

2 2

2 2

2 3

0
#865
Свинки-копилки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан ориентированный граф, в котором у каждой вершины существует ровно одно исходящее ребро. Требуется найти количество циклов в нем.

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

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

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

В первой строке содержится число N — количество свинок-копилок (1≤N≤100). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

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

Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Пример

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

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

Комментарий

4

2

1

2

4

2

Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
#1111
Обход в глубину
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача D ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Программа выводит номера посещенной вершины графа после вызова обхода в глубину. По результатам работы этой программы требуется восстановить граф и вывести его в виде списка ребер.

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования Паскале и Си.

Паскаль

Си

var

   a: array [1..maxn, 1..maxn] of boolean;

  visited: array [1..maxn] of boolean;

 

procedure dfs(v: integer);

var

   i: integer;

begin

   writeln(v);

   visited[v] := true;

   for i := 1 to n do begin

     if a[v][i] and not visited[i] then begin

       dfs(i);

       writeln(v);

     end;

   end;

end;

 

procedure graph_dfs;

var

   i: integer;

begin

   for i := 1 to n do

     if not visited[i] then

       dfs(i);

end;

int a[maxn + 1][maxn + 1];

int visited[maxn + 1];

 

void dfs(int v) {

   printf("%d\n", v);

   visited[v] = 1;

   for (int i = 1; i <= n; i++) {

     if ((a[v][i] != 0) && (visited[i] == 0)) {

       dfs(i);

       printf("%d\n", v);

     }

   }

}

 

void graph_dfs() {

   for (int i = 1; i <= n; i++) {

     if (visited[i] == 0) {

       dfs(i);

     }

  }

}

Петина программа хранит граф с использованием матрицы смежности в массиве a (вершины графа пронумерованы от 1 до n). В массиве visited помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру graph_dfs для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

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

Первая строка входного файла содержит два целых числа: n и l количество вершин в графе и количество чисел в выведенной последовательности (1 ≤ n ≤ 300, 1 ≤ l ≤ 2n − 1). Следующие l строк по одному числу вывод Петиной программы. Гарантируется, что существует хотя бы один граф, запуск программы Пети на котором приводит к приведенному во входном файле выводу.

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

На первой строке выходного файла выведите одно число m максимальное возможное количество ребер в графе.

Следующие m строк должны содержать по два целых числа номера вершин, соединенных ребрами. В графе не должно быть петель и кратных ребер.

Примеры
Входные данные
6 10
1
2
3
2
4
2
1
5
6
5
Выходные данные
6
1 2
1 3
1 4
2 3
2 4
5 6
#1190
Введите одностороннее движение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Тридевятом Царстве было N городов, некоторые из которых были соединены дорогами. К сожалению, в последнее время добраться из одного города в другой стало очень сложно из-за возникших автомобильных пробок. В целях борьбы с пробками было решено все дороги сделать односторонними, т.е. разрешить проезд по каждой дороге только в одном направлении. При этом требуется, чтобы по-прежнему можно было из любого города попасть в любой другой.

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

Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.

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

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

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

Примеры
Входные данные
4
6
1 2
1 2
2 3
2 4
4 3
1 4
Выходные данные
2 1
2 1
3 2
4 2
4 3
1 4
Входные данные
2
1
1 2
Выходные данные
0
Страница: << 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест