Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 265 266 267 268 269 270 271 >> Отображать по:
#2776
Магический квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Магическим квадратом будем называть квадрат с одинаковой суммой чисел по всем вертикалям и горизонталям; никаких требований на суммы по диагоналям накладывать не будем. Составьте такой квадрат из заданного набора чисел.

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

Во входном файле записаны 16 различных целых чисел в интервале от 0 до 32768

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

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

Примеры
Входные данные
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16
Выходные данные
     1     6    13    14
     2    11    12     9
    15     7     4     8
    16    10     5     3
#2781
Декартово дерево
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вам даны пары чисел \((a_i, b_i)\), Вам необходимо построить декартово дерево, такое что \(i\)-ая вершина имеет ключи \((a_i, b_i)\), вершины с ключом \(a_i\) образуют бинарное дерево поиска, а вершины с ключом \(b_i\) образуют кучу на минимум.

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

В первой строке записано число \(N\) — количество пар. Далее следует \(N\) (\(1 \le N \le 50\,000\)) пар \((a_i, b_i)\). Для всех пар \(\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000\). \(a_i \ne a_j\) и \(b_i \neq b_j\) для всех \(i \ne j\).

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

Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите \(N\) строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.

Если подходящих деревьев несколько, выведите любое.

Примеры
Входные данные
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
Выходные данные
YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0
#2782
Следующий
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Реализуйте структуру данных, которая поддерживает множество \(S\) целых чисел, с котором разрешается производить следующие операции:

  • \(add(i)\) — добавить в множество \(S\) число \(i\) (если он там уже есть, то множество не меняется);
  • \(next(i)\) — вывести минимальный элемент множества, не меньший \(i\). Если искомый элемент в структуре отсутствует, необходимо вывести -1.
Входные данные

Исходно множество \(S\) пусто. Первая строка входного файла содержит \(n\) — количество операций (\(1 \le n \le 300\,000\)). Следующие \(n\) строк содержат операции. Каждая операция имеет вид либо «+ \(i\)», либо «? \(i\)». Операция «? \(i\)» задает запрос \(next(i)\).

Если операция «+ \(i\)» идет во входном файле в начале или после другой операции «+», то она задает операцию \(add(i)\). Если же она идет после запроса «?», и результат этого запроса был \(y\), то выполняется операция \(add((i + y) \bmod 10^9)\).

Во всех запросах и операциях добавления параметры лежат в интервале от \(0\) до \(10^9\).

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

Для каждого запроса выведите одно число — ответ на запрос.

Примеры
Входные данные
6
+ 1
+ 3
+ 3
? 2
+ 1
? 4
Выходные данные
3
4
#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
Страница: << 265 266 267 268 269 270 271 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест