Problem A. SST for sparse graph
Statement
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3
1 2 10
2 3 10
3 1 10
|
20
|
Problem B. Eulerian cycle
Statement
You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.
Input file format
Input file contains two integers
N,
M.
Vertices are numbered with integer numbers from
1 to
N.
M is the number of edges. Each of following
M lines contains a pair of
vertex numbers, connected by some edge. There is at most one edge connecting two vertices.
Output file format
Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle.
If there does not exist any Eiler cycle, output file must contain
−1.
Constraints
1 ≤ N, M ≤ 100000
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3
1 2
2 3
3 1
|
1 2 3 1
|
Задача C. Метро
Условие
Метрополитен состоит из нескольких линий метро.
Все станции метро в городе пронумерованы натуральными числами от 1 до N.
На каждой линии расположено несколько станций.
Если одна и та же станция расположена сразу на нескольких линиях,
то она является станцией пересадки и на этой станции можно пересесть
с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).
Напишите программу, которая по данному вам описанию метрополитена определит,
с каким минимальным числом пересадок можно добраться со станции A на станцию B.
Если данный метрополитен не соединяет все линии в одну систему,
то может так получиться, что со станции A на станцию B добраться невозможно,
в этом случае ваша программа должна это определить.
Формат входного файла
Во входном файле записано сначала число N — количество станций метро в городе.
Далее записано число M — количество линий метро.
Далее идет описание M линий.
Описание каждой линии состоит из числа Pi — количество станций на этой линии и Pi чисел,
задающих номера станций, через которые проходит линия
(ни через какую станцию линия не проходит дважды).
В конце файла записаны два различных:
числа A — номер начальной станции, и B — номер станции, на которую нам нужно попасть.
При этом если через станцию A проходит несколько линий,
то мы можем спуститься на любую из них.
Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.
Формат выходного файла
В выходной файл выведите минимальное количество пересадок, которое нам понадобится.
Если добраться со станции
A на станцию
B невозможно,
выведите в выходной файл одно число
−1 (минус один).
Ограничения
2 ≤ N ≤ 100,
1 ≤ M ≤ 20,
2 ≤ Pi ≤ 50.
Примеры тестов
| № |
Входной файл (e.in) |
Выходной файл (e.out) |
|---|
| 1 |
5 2
4 1 2 3 4
2 5 3
3 1
|
0
|
| 2 |
5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
|
2
|
| 3 |
10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
|
1
|
| 4 |
4 2
2 1 2
2 3 4
1 3
|
-1
|
Задача D. Заколдованный аквариум
Условие
По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.
Очередной понедельник выдался в НИИЧАВО
(Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным.
Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды,
куда на прошлой неделе завезли новый аквариум.
Туда и вошел Привалов в самый интересный момент беседы между
Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой.
Сейчас Кристобаль Хозевич в красках описывал,
какие могут возникнуть повреждения всей новейшей системы безопасности,
недавно установленной в институте, от всего того количества воды,
которым сейчас затапливался его отдел.
— Подождите, остановил его речь Выбегалло, вот закончим проверку и выключим воду.
— Да какая же это проверка, это же чистой воды саботаж! —
возмущался Хунта, вот сейчас заделаю все дырки в вашем аквариуме, и тогда будем разговаривать.
— Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете?
Мы проводим важнейший эксперимент!
— Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов
— Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить,
и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.
— Ну, раз вы все-таки запечатали отверстия, то спешки особой нет, —
продолжил Амвросий Амбруазович, — на прошлой неделе мне, доставили новый большой аквариум,
необычной конструкции, а если быть точным, с несколькими прямоугольными
отверстиями на лицевой стороне, вот посмотрите.
Привалов, наконец, осмотрел новый аквариум. Он представлял собой
прямоугольный параллелепипед размерами W × H × L метров без верхней крышки,
на лицевой стороне которого было вырезано N квадратных отверстий
c длиной стороны ai метров. Сверху над аквариумом висела большая труба,
через которую в него поступало M кубических метров воды в секунду.
— Так вот, — продолжил Выбегалло, —
до появления здесь Кристобаля Хозевича мы проводили эксперимент,
целью которого было определить уровень воды в этом аквариуме при заданной конфигурации отверстий.
— А более сухого способа вы не нашли, — вставил свою реплику Хунта
Привалов, как программист, прекрасно понимал,
что для таких экспериментов вовсе не обязательно затапливать пол-института.
Нужно лишь определить скорость вытекания воды из отверстий и
описать весь эксперимент очень простой компьютерной моделью.
Свои соображения он и изложил собравшимся.
— Замечательная идея, молодой человек, — произнес Выбегалло, — это ж сколько средств то можно сэкономить, да и воду тратить не придется.
Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме.
Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой:
через отверстие площадью b квадратных метров
в одну секунду будет вытекать V × b кубических метров воды.
В начале эксперимента аквариум пуст. Через некоторое время после того, как
из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется
(либо аквариум переполнится).
Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.
Формат входного файла
Входной файл содержит числа
V M N —
соответственно скорость вытекания воды (в
м/с), поток втекающей воды (
м3/c)
и количество отверстий в лицевой стороне аквариума. Далее следует
N троек
чисел
xi yi ai — координаты нижнего левого угла и длина стороны. отверстия номер
i.
Отверстия не пересекаются и не соприкасаются друг с другом.
Формат выходного файла
Выходной файл должен содержать единственно число — высоту уровня воды в аквариуме
с точностью до четырех знаков после запятой, либо
−1, если аквариум переполнится.
Ограничения
0 < V, M ≤ 1000,
0 ≤ N ≤ 100,
0 ≤ xi, yi, ai ≤ 106.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0
|
2.0
|
Задача E. Дипломы
Условие
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике.
Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы.
К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры:
W — в ширину и H — в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками.
Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной
стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы
прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет,
чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго
в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих
внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для
размещения всех своих дипломов.
Система оценивания
Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.
Формат входного файла
Входной файл содержит три целых числа: W, H, N
Формат выходного файла
В выходной файл необходимо вывести ответ на поставленную задачу.
Ограничения
1 ≤ W, H, N ≤ 109
Примеры тестов
| № |
Входной файл (diploma.in) |
Выходной файл (diploma.out) |
|---|
| 1 |
2 3 10
|
9
|
