Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск по ответу
---> 2 задач <---
Источники --> Личные олимпиады --> COCI
    COCI 2016-2017(0 задач)
    COCI 2015-2016(36 задач)
    COCI 2014-2015(0 задач)
Страница: 1 Отображать по:
#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
#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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест