Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 189 190 191 192 193 194 195 >> Отображать по:
#2783
Максимальный поток - 1
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

НЛО прилетело и написало это условие.

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

В первой стоке входного файла содержится два числа: \(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
#2784
Максимальный поток - 2
  
Темы: [Потоки]

Вам задан ориентированный граф \(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
#2785
Химия!!!
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася и Сережа играют в следующую игру. В некоторых клетках клетчатого листка Сережа рисует один из символов 'H', 'O', 'N' или 'C', после чего Вася должен провести между некоторыми находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение химической молекулы. К сожалению, Сережа любит рисовать много символов, и Вася не может сразу определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу, которая даст ответ на этот вопрос.

В этой задаче проведенные между символами химических элементов линии будем считать корректным изображением молекулы, если они удовлетворяют следующим условиям:

  • каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках,
  • между каждой парой символов проведено не более одной линии,
  • от каждого элемента отходит ровно столько линий, какова валентность этого элемента (1 для H, 2 для O, 3 для N, 4 для 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
#2787
LCA-Offline
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Изначально имеется дерево состоящее только из корня (вершина с номером \(1\)). Требуется научиться отвечать на следующие запросы:

  • ADD \(a\) \(b\) — подвесить вершину \(b\) за вершину \(a\) (гарантируется, что вершина \(a\) уже существует, а вершина \(b\) еще не существует).
  • GET \(a\) \(b\) — вернуть LCA вершин \(a\) и \(b\).

Все номера вершин от \(1\) до \(N\).

В каждый момент времени у нас есть одно дерево.

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

В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).

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

Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.

Примеры
Входные данные
9
ADD 1 2
ADD 1 3
ADD 2 4
GET 1 3
GET 2 3
GET 3 4
ADD 2 5
GET 4 5
GET 5 5
Выходные данные
1
1
1
2
5
#2798
Возведение в степень
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вычислите 2n

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

Единственное целое неотрицательное число n, не превосходящее 20000

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

Выведите ответ на поставленную задачу

Примеры
Входные данные
10
Выходные данные
1024
Страница: << 189 190 191 192 193 194 195 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест