---> 91 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Прямоугольный садовый участок шириной $N$ и длиной $M$ метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

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

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

В первой строке находятся числа $N$ и $M$ через пробел, далее идут $N$ строк по $M$ символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ $N$, $M$ ≤ 200.

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

Вывести одно число - количество грядок на садовом участке.

Примеры
Входные данные
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
Выходные данные
5
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Подсчет количества циклов в графе, где у каждой вершины ровно одно исходящее ребро.

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

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

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

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

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

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

Пример

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

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

Комментарий

4

2

1

2

4

2

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

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.

ограничение по времени на тест
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

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

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

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

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

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

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

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

Пример

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

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

Комментарий

4

2

1

2

4

2

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

Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.

В операционной системе Xunil информация обо всех файлах и директориях хранится в специальном файле в следующем формате:

emoh

 vonavi

  a.doc

  b.doc

 vortep

  .bashrc

 vorodis

  onrop

   1.avi

   2.avi

rav

 bil

 

Имена файлов, и только они, содержат точку.

Требуется по данному имени файла найти путь к нему. Если таких файлов несколько, вывести путь к файлу, который записан выше.

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

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

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

Выведите путь к файлу в формате /директория/директория/…/файл

Гарантируется, что такой файл есть.

Гарантируется, что длина строки ответа не превосходит 255.

Примеры
Входные данные
1.avi
12
emoh
 vonavi
  a.doc
  b.doc 
 vortep
  .bashrc
 vorodis
  onrop
   1.avi
   2.avi 
rav
 bil
Выходные данные
/emoh/vorodis/onrop/1.avi

Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест