НЛО прилетело и написало это условие.
В первой стоке входного файла содержится два числа: \(n\) и \(m\) (\(2 \le n \le 10\), \(1 \le m \le n \times (n - 1)\)).
Это количество вершин и рёбер в графе, в котором вам требуется найти поток. Далее следуют описания рёбер графа,
по одному в каждой строке входного файла. Описание ребра состоит из трёх чисел:
\(a\), \(b\), \(c\) (\(1 \le a, b \le n\),
\(a \neq b\), \(1 \le c \le 100\)). Эти числа означают, что из вершины \(a\) в вершину \(b\) идёт
ребро пропускной способности \(c\). Гарантируется, что в графе нет кратных рёбер.
В единственную строку выходного файла выведите одно число — размер максимального потока из вершины \(1\) в вершину \(n\).
4 5 1 2 2 1 3 3 3 2 1 2 4 3 3 4 2
5
Вам задан ориентированный граф \(G\). Каждое ребро имеет некоторую пропускную способность. Найдите максимальный поток между вершинами \(1\) и \(n\).
Первая строка входного файла содержит \(n\) и \(m\) — число вершин и рёбер в графе (\(2 \le n \le 500\), \(1 \le m \le 10\,000\)). Последующие строки описывают рёбра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности — целые числа, не превосходящие \(10^9\).
Выведите величину максимального потока между вершинами \(1\) и \(n\).
4 5 1 2 1 1 3 2 3 2 1 2 4 2 3 4 1
3
Вася и Сережа играют в следующую игру. В некоторых клетках клетчатого листка Сережа рисует один из
символов 'H', 'O', 'N' или 'C', после чего Вася должен провести между некоторыми
находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение
химической молекулы. К сожалению, Сережа любит рисовать много символов, и Вася не может сразу
определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу,
которая даст ответ на этот вопрос.
В этой задаче проведенные между символами химических элементов линии будем считать корректным изображением молекулы, если они удовлетворяют следующим условиям:
Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) (\(1\leq n,m\leq 50\)) — размеры листочка, на котором рисует Сережа.
Далее следуют \(n\) строк по \(m\) символов в каждой, задающих конфигурацию химических элементов, которую нарисовал Сережа;
пустые клетки задаются символом '.'.
В выходной файл выведите одно слово «Valid», если линии провести требуемым образом можно, и «Invalid»,
если нельзя.
3 4 HOH. NCOH OO..
Valid
3 4 HOH. NCOH OONH
Invalid
В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-вверх и вправо-вверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. О том, что пешка может превращаться в ферзя Глеб не подозревает. Поэтому он придумал свой вариант шахмат.
Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоят P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, их цель — побить все чёрные фигуры.
Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел побить белыми пешками все чёрные фигуры, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть, и, в случае успеха, выведите правильную последовательность ходов белых пешек.
Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ 1000, K ≤ (M - 1)N). Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — координаты (строки и столбцы) чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).
Если пешки не смогут съесть все фигуры, выведите единственное слово NO.
В противном случае в первую строку выведите YES, вторая строка должна содержать суммарное число перемещений C, последующие C строк — описание ходов пешек, по одному ходу на каждую строку. Каждый ход задаётся двумя координатами r, c пешки (номерами строки и столбца), которая будет ходить, и символом m, принимающем три значения: L, R, F — побить вперед и влево, побить вперед и вправо, сделать шаг вперед соответственно. Данные о ходе следует выводить разделёнными одним пробелом, сначала координаты, потом тип хода.
Если последовательностей ходов несколько, выведите любой из них. Обратите внимание, что минимизировать количество перемещений не требуется.
2 2 2 1 1 2 2 2
YES 1 1 1 R
3 3 2 2 1 3 3 1 3 3
NO
В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.
Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоит P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер N (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).
Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел достичь хотя бы одной пешкой самой верхней строки, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть.
Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ (N - 1)M. Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — номера строк и столбцов чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).
Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.
3 3 2 3 1 3 2 2 3 1 3 3
YES
4 4 2 4 1 4 3 1 3 2 4 2 4 4
NO