Мосты(2 задач)
Применение обхода в глубину(3 задач)
Топологическая сортировка(2 задач)
Точки сочленения(1 задач)
Прямоугольный садовый участок шириной \(N\) и длиной \(M\) метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.
В первой строке находятся числа \(N\) и \(M\) через пробел, далее идут \(N\) строк по \(M\) символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ \(N\), \(M\) ≤ 200.
Вывести одно число - количество грядок на садовом участке.
5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####
5
У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.
Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.
Пример
Входные данные | Выходные данные | Комментарий |
4 2 1 2 4 | 2 | Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой. Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4. |
Прямоугольную таблицу, состоящую из 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 |
У Васи есть 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