Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 17 задач <---
Источники --> Личные олимпиады --> COCI --> COCI 2015-2016
    Раунд 1(6 задач)
    Раунд 2(6 задач)
    Раунд 3(6 задач)
    Раунд 4(6 задач)
    Раунд 5(6 задач)
    Раунд 6(6 задач)
Страница: << 1 2 3 4 >> Отображать по:
#113557
Держава
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Держава ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В далекой стране есть N городов. Был избран новый премьер-министр. В настоящее время в этой стране нет ни одной дороги, поэтому премьер-министр решил модернизировать страну, соединив некоторые города с двусторонними автострадами в транспортные сети. Два города будут расположены в одной и той же сети, если можно добраться до одного города от другого, используя недавно построенные дороги. Каждый город будет расположен в какой-то сети. Каждая сеть состоит из одного или нескольких городов.

Города представлены в виде точек в двумерной системе координат. Дорога между двумя городами представлена ​​в виде отрезка, соединяющего две точки, в которых расположены города. Длина дороги равна длине отрезка в километрах.

В настоящее время страна переживает экономический спад, поэтому премьер-министр решил, что из-за отсутствия бюджета они не будут строить дороги длиннее, чем D километров. Кроме того, премьер-министр радуется мелочам, поэтому он будет счастлив, если по крайней мере в одной сети будет существовать непустое подмножество городов (оно может включать все города в сети), где общая сумма жителей делится на К . Например, если K = 4 и есть сеть с городами, в которых есть 3 , 5 , 7 жителей соответственно, премьер-министр будет счастлив, потому что сумма жителей в первых двух городах равна 8 .

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

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

Первая строка ввода содержит целые числа N и K (1 ≤ N ≤ 50000, 1 ≤ K ≤ 30) . Каждая из следующих N строк содержит три целых числа x i ; y i ; k i (0 ≤ x i , y i , k i ≤ 100000000) , которые представляют координату x города, координату y и количество жителей в этом городе, соответственно. На входных данных не будет двух городов с одинаковыми координатами. Кроме того, не будет ни одного города, в котором число жителей делится на К .

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

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

Примечание

Объяснение первого примера: единственный способ удержать премьер-министра в счастливом настроение - все города должны находятся в одном округе. Минимальный D , для которого это возможно, равен 1.414 .

Объяснение второго примера: премьер-министр будет рад, если первые 5 городов находятся в одном округе. Если D = 5.657 , премьер-министр может соединить города 1, 2, 3, 5 с городом 4 . В этом случае сумма жителей в городах 1, 2, 3, 4, 5 составит 11 , что делится на 11 , Поэтому премьер-министр будет счастлив.

Примеры
Входные данные
3 3
0 4 4
1 5 1
2 6 1
Выходные данные
1.414
Входные данные
6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10
Выходные данные
5.657
Входные данные
6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3
Выходные данные
2.000
#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
#113568
Слон
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 3, Слон ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Слон постоянно шалит в своей школе. На уроках ему становится скучно, и он начинает хулиганить. Учитель решил успокоить слона, поэтому дал ему очень сложную математическую задачу.

Учитаель дал слону арифметическое выражение A и числа P и M . Слону надо ответить на такой вопрос: "Каково минимальное неотрицательное значение переменной x в выражении A , такое что остаток от деления A на M равно P ?". Гарантируется, что решение всегда существует.

Кроме того, после применения законов распределения к выражению A , x содержится в A только в первой степени.

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

В первой строке содержится выражение A ( 1 ≤ | A | ≤ 10 5 ). Вторая строка содержит два целых числа P и M ( 0 ≤ P < M ≤ 10 6 ). A состоит только из символов +, -, *, (, ), x и цифр от 0 до 9. Каждый оператор +, -, * применяется ровно к двум значения, умножения всегда обозначены явно.

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

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

Примечание

Пояснение к первому примеру:

(5 + 3 + x ) mod 10 при x = 0 равно 8.

(5 + 3 + x ) mod 10 при x = 1 равно 9. Значит, ответ x = 1 .

Примеры
Входные данные
5+3+x
9 10
Выходные данные
1
Входные данные
20+3+x
0 5
Выходные данные
2
Входные данные
3*(x+(x+4)*5)
1 7
Выходные данные
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 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест