Задача 1. Дерево

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

Формат входного файла

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа ui и vi через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

Формат выходного файла

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 105

0 ≤ m ≤ 105

1 ≤ ui, vi ≤ n

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
1 3
YES
2
3 3
1 2
2 3
3 1
NO

Задача 11. Элемент N-мерного масcива

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется написать программу, которая по количеству измерений массива — N, размерностям измерений — ai и индексы элемента в массиве — ki, напечатает позицию элемента в памяти относительно начала массива. Размер элемента массива составляет один байт.

Формат входных данных

В первой строке входные данные содержат число N — количество измерений массива.

В следующих двух строках содержатся по N чисел ai и ki соответственно.

Формат выходных данных

Выходные данные должны содержать одно целое число — позицию элемента в памяти.

Ограничения

1 ≤ N ≤ 32

1 ≤ ai ≤ 232

0 ≤ ki < ai

Примеры тестов

Стандартный вход Стандартный выход
1
1
10
8
8
2
2
2 5
1 3
8
3
2
5 5
2 1
11

Задача 2. Водовод на о. Русский

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

Известно, что водовод представляет собой последовательность ячеек, имеющих общую сторону. Первая его ячейка находится в первом столбце клеток карты, последняя — в последнем. Водовод не проходит дважды через одну и ту же ячейку.

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

Формат входного файла

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

Формат выходного файла

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида ri, ci, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5
...##
##...
.####
...#.
YES
6  2 1  2 2  3 2  3 3  3 4  3 5 
2
3 6
#.###.
###.##
......
MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
3
3 6
..###.
###.##
..###.
MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6
4
3 3
...
.##
...
NO

Задача 3. Расстояние от корня

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

В заданном корневом дереве найдите вершины, максимально удалённые от корня. Расстоянием между вершинами считается количество рёбер в пути.

Формат входного файла

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, , n. Вершина 1 является корнем дерева.

Формат выходного файла

В первой строке выведите максимальное расстояние от корня до остальных вершин дерева.

Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии.

В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1
1
1
2
2 3
2
3
1
2
2
1
3

Задача 4. Семь колонн Владивостока

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Когда абитуриент Дима пришёл в кампус ДВФУ на день открытых дверей, его внимание привлекла инсталляция "Семь колонн Владивостока".

Данная инсталляция является рабочим макетом объекта, спроектированного для создания в бетоне в городской среде. В основе идеи лежат наблюдения за природой и инфраструктурой города и их взаимодействием. Данный образ, семь колонн, является символом диалога между силами природы и деятельностью человека.

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

Поскольку Дима дополнительно изучает информатику, он быстро смекнул, что данная конструкция может быть представлена как планарный граф, т.е. граф, который можно нарисовать на плоскости без пересечений рёбер.

Дима знает, как посчитать число граней этого планарного графа, для этого нужно применить формулу Эйлера V − E + F = 2, где V — число вершин, E — число рёбер, F — число граней, включая внешнюю грань. В нашем случае V = 7, E = 13, отсюда F = 8, поэтому треугольных граней всего 7, что легко проверить.

Но теперь Дима хочет посчитать общее число элементарных циклов в этом графе. Путь в графе — это последовательность вершин графа, в которой каждая пара последующих вершин соединена ребром. Циклом называется путь, в котором первая и последняя вершины совпадают. Цикл называется элементарным, если в нём вершины и рёбра не повторяются.

Напишите программу, принимающую на вход данный граф и вычисляющую количество элементарных циклов в этом графе.

Формат входного файла

Входной файл содержит целые числа N M — количество вершин и количество рёбер соответственно. Далее следуют M пар целых чисел — рёбра графа.

Ребро не может идти из вершины в неё саму. В графе нет повторяющихся рёбер. Ребра (u, v) и (v, u) — это одно и то же ребро.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество элементарных циклов.

Ограничения

2 ≤ N ≤ 7

M ≥ 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 13
1 2
1 3
2 3
2 5
2 6
3 4
3 5
3 7
4 5
4 6
4 7
5 6
6 7
56
2
6 6
1 2
2 3
3 1
4 6
6 5
5 4
2
3
4 6
1 2
1 3
1 4
2 3
2 4
3 4
7

Задача 5. Репликация

Автор:И. Туфанов, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Компьютерная сеть крупного предприятия содержит N серверов баз данных. Некоторые сервера напрямую связаны между собой кабелями локальной сети, при этом от каждого сервера можно добраться по связям до любого другого.

Сервера содержат копии одной и той же базы данных. Чтобы поддерживать эти копии в одинаковом состоянии, используется система репликации — сервер рассылает каждое изменение, внесённое в его данные, всем соседним серверам, те, в свою очередь, рассылают его далее до тех пор, пока об изменении не будет оповещена вся сеть.

С целью снижения нагрузки на сеть было решено для некоторых кабелей разрешить передачу данных только в одном из направлений. Требуется написать программу, которая по описанию сети зафиксирует направление передачи по как можно большему числу кабелей таким образом, чтобы данные по-прежнему можно было передать с любого сервера на любой другой.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Во входном файле содержатся числа N M, где N — число серверов, M — число кабелей. За ними идут M пар чисел ai bi, — номера серверов, соединённых i-м кабелем. Сервер не может быть соединён сам с собой, но два сервера могут быть соединены несколькими кабелями.

Формат выходного файла

В выходном файле должно содержаться M чисел di, равных 0, 1 или 2. di = 0 означает, что для соответствующего кабеля следует сохранить двустороннюю передачу данных, di = 1 — что следует фиксировать направление от ai к bi, di = 2 — что следует фиксировать направление от bi к ai. Если имеется несколько оптимальных решений, следует вывести любое из них.

Ограничения

1 ≤ N ≤ 2 × 105; 0 ≤ M ≤ 2 × 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 2
1 2
2 3
2
1
0
2
3 3
1 2
1 3
2 3
1
2
1

Задача K. Свинья-копилка

Автор:А. Кленин, краевая олимпиада 2001 г.   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

Формат входного файла

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Ci Wi. Все числа во входном файле — целые.

Формат выходного файла

В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число  − 1.

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1

0.788s 0.011s 31