Страница: << 1 2 3 >> Отображать по:
#577
Развлечения с измерителем
  
Источники: [ Командные олимпиады, ВКОШП, 2007, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

В первой строке вводится число \(n\) - количество дырок (2 <= \(n\) <= 1000). Следующие n строк содержат по два целых числа - координаты дырок. Координаты не превышают \(10^4\) по абсолютной величине.

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

В первой строке выведите \(k\) - количество различных расстояний, которые Дима мог установить между иглами измерителя. Следующие k строк должны содержать искомые расстояния, по одному вещественному числу в строке. Расстояния должны быть выведены в возрастающем порядке. Каждое число должно быть выведено с точностью не менее, чем 10-9.

Гарантируется, что существует по крайней мере одно расстояние, которое Дима мог установить между иглами измерителя.

Примеры
Входные данные
4
0 0
1 1
1 0
0 1
Выходные данные
2
1.0
1.4142135623730951
#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
Страница: << 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест