Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 6 задач <---
Источники --> Личные олимпиады --> COCI
    COCI 2016-2017(0 задач)
    COCI 2015-2016(36 задач)
    COCI 2014-2015(0 задач)
Страница: 1 2 >> Отображать по:
#113538
Вечеринка Петара
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Вечеринка Петара ]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
32 megabytes

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.

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

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .

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

Выведите единственное число - количество возможных наборов типов шуток на вечеринке.

Примеры
Входные данные
4
2 1 3 4
1 2
1 3
3 4
Выходные данные
6
Входные данные
4
3 4 5 6
1 2
1 3
2 4
Выходные данные
3
Входные данные
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
Выходные данные
10
#113554
Король Артур
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Король Артур ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вы наверняка слышали легенду о Короле Артуре и Рыцарях Круглого Стола. Практически все версии этой истории указывают на то, что круглость Круглого Стола тесно связана с верой Артура в равенство среди рыцарей. Это ложь! На самом деле выбор Артура касательно формы стола вызван его детской травмой.

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

В этой задаче представим стол на координатной плоскости как квадрат с противоположными вершинами в точках (0, 0) и (10000, 10000), где палочкам соответствуют прямые отрезки, лежащие внутри квадрата. Предположим, что Артур сидит у края стола, прилежащего к оси X. Тогда уборка палочек со стола сводится к передвижению их к оси X, покуда они не упадут со стола. Ваша задача - определить порядок уборки палочек со стола, который соответствует условиям из предыдущего абзаца.

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

Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 5000 ) - количество палочек на столе. Каждая из следующих N строк содержит 4 целых числа x 1 , y 1 , x 2 , y 2 ( 0 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10000 ), обозначающих крайние точки палочек.

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

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

Примеры
Входные данные
4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3
Выходные данные
2 4 1 3
Входные данные
4
0 0 1 1
1 2 0 3
2 2 3 3
4 0 3 1
Выходные данные
4 3 1 2
Входные данные
3
4 6 5 5
2 1 15 1
3 2 8 7
Выходные данные
2 3 1
#113567
Хорватские ученые
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 3, Хорватские ученые ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Ученые в тайной химической лаборатории в Хорватии изучают химические связи в недавно обнаруженном веществе инопланетного происхождения. Имеющаяся в распоряжении ученых порция вещества состоит из N молекул, соединенных между собой N - 1 ковалентными связями, и все молекулы объединены этими связями (не обязательно напрямую) в единую сеть.

Так как вещество нестабильное, в каждой молекуле регулярно возникают импульсы, перемещающиеся по веществу через существующие связи в обоих направлениях. Ученые собираются стабилизировать вещество, направив ковалентные связи (то есть, дав импульсам возможность путешествовать по ним между молекулами лишь в одном направлении). Показатель нестабильности вещества определяется длиной максимального пути, который может пройти импульс в нем, и ученые хотят сделать эту величину как можно меньше.

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

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

Первая строка содержит одно целое число N ( 2 ≤ N ≤ 100000 ). Каждая из последующих N - 1 строк содержит по два целых числа a i и b i ( 1 ≤ a i , b i ≤ N ), которые показывают что молекулы с номерами a i и b i соединены ковалентной связью.

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

Выведите N - 1 строку, каждая из которых должна содержать 1 если ковалентная связь должна быть направлена от a i к b i или 0 в противном случае.

Примечание

Решения, в которых N ≤ 20 , будут оцениваться в 30 баллов.

Примеры
Входные данные
3
1 2
2 3
Выходные данные
0
1
Входные данные
4
2 1
1 3
4 1
Выходные данные
1
0
1
#113570
День рождения Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 3, День рождения Мирко ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
512 megabytes

Мирко получил в подарок на свой день рождения квадратный стол N x N , где в каждой клетке записано неотрицательное целое число. К сожалению, некоторые числа кажутся Мирко слишком большими, поэтому он собирается положить на стол K фишек домино, которые закроют некоторые слишком большие числа. Точнее, он собирается положить фишки домино в соответствии со следующими правилами:

1. Каждая фишка домино покрывает две клетки, соседних по строчке или столбцу..

2. Фишки домино не накладываются друг на друга (но могут соприкасаться).

3. Сумма чисел на всех видимых (непокрытых) клетках минимальна.

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

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

Первая строка содержит два целых числа: N ( 1 ≤ N ≤ 2000 ) - размер стола, и K ( 1 ≤ K ≤ 8 ) - количество фишек домино. Каждая из следующих N строк содержит N целых чисел (в диапазоне [0, 1000]) - числа в соответствующих клетках поля.

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

Выведите единственное целое число - минимально возможную сумму чисел в клетках после установки фишек домино.

Примечание

Решения, работающие при K ≤ 5 , будут оцениваться в 70 баллов.

Примеры
Входные данные
3 1
2 7 6
9 5 1
4 3 8
Выходные данные
31
Входные данные
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
Выходные данные
17
#113574
Чубакка и дерево
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Чубакка и дерево ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.

Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .

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

Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y ≤ N , x ≠ y ) - запросы, описанные в условии.

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

Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.

Примечание

Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.

Примеры
Входные данные
7 2 3
1 2
2 1
4 7
Выходные данные
1
1
4
Входные данные
9 3 3
8 9
5 7
8 4
Выходные данные
2
2
3
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест