Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 10 задач <---
Источники --> Личные олимпиады --> COCI
    COCI 2016-2017(0 задач)
    COCI 2015-2016(36 задач)
    COCI 2014-2015(0 задач)
Страница: << 1 2 Отображать по:
#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
#113569
Весёлые запросы
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 3, Весёлые запросы ]
Ограничение по времени, сек2
Ограничение по памяти, мегабайт512

Дан массив a длины n , состоящий из натуральных чисел в диапозоне [1; k ] . Вам необходимо обработать 2 типа запросов:

1 p u — изменить значение элемента на позиции p на u .

2 — сообщить длину кратчайшего подотрезка, содержащего все числа от 1 до k или - 1 если такого подотрезка не существует.

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

В первой строке входного файла задано 3 целых числа n , k и m (1 ≤ n , m ≤ 10 5 , 1 ≤ k ≤ 50) — длина массива, максимальное число в массиве и число запросов, соответственно.

В следующей строке содержится n чисел (1 ≤ a i ≤ k ) — элементы массива.

В последующих m строках содержатся запросы в формате, указанном выше.

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

Для каждого запроса второго типа выведите ответ на него.

Группы тестов

11 баллов — (1 ≤ n , m ≤ 40) .

47 балла — (1 ≤ n , m ≤ 5 000) .

42 балла — (1 ≤ n , m ≤ 10 5 ) потестовая оценка.

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

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

1. A и B - различные планеты.

2. В действующей сети межпланетных магистралей существует путь между A и B .

3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.

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

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).

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

Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.

Примечание

Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.

Примеры
Входные данные
2
1 2 0
1
Выходные данные
1
0
Входные данные
3
1 2 4
2 3 4
1 2
Выходные данные
1
0
0
Входные данные
4
1 2 0
2 3 0
2 4 0
3 1 2
Выходные данные
6
3
1
0
#113580
Маленький Матеж и большие проблемы
  
Темы: [Хеш]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Маленький Матеж и большие проблемы ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

У маленького Матежа возникла проблема с решением следующей задачи.

У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.

Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.

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

В первой строке содержатся N и Q ( 1 ≤ N , Q ≤ 10 5 ). В последующих N строках содержатся строки из множества. В последующих Q строках содержатся шаблоны. Входной файл содержит не более трех миллионов символов.

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

Выведите Q строк: в каждой ответ для соответствующего шаблона.

Система оценки

40 баллов: 1 ≤ N , Q ≤ 1000

Примеры
Входные данные
3 3
aaa
abc
aba
a*a
aaa*
*aaa
Выходные данные
2
1
1
Входные данные
5 3
eedecc
ebdecb
eaba
ebcddc
eb
e*
*dca
e*c
Выходные данные
5
0
2
#113581
Массивы, числа, три хеша
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Массивы, числа, три хеша ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .

Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s )  =  ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.

Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .

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

В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).

Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).

Гарантируется, что во всех тестах K ≤ 2 N - 1 .

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

Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .

Примечание

Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.

Примеры
Входные данные
2 3 1 5
1 2
Выходные данные
1 1
3 2
2 1
Входные данные
3 4 2 3
1 3 1
Выходные данные
1 1
1 1
0 2
2 2
Входные данные
5 6 23 1000
1 2 4 2 3
Выходные данные
1 1
25 2
25 2
577 3
274 4
578 3
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест