Темы --> Информатика --> Структуры данных --> Деревья
    Куча(30 задач)
    Двоичное дерево поиска(24 задач)
    Дерево отрезков, RSQ, RMQ(90 задач)
    Бор(14 задач)
    Дерево Фенвика(6 задач)
    Декартово дерево(10 задач)
---> 43 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 3 4 5 6 7 8 9 Отображать по:
#113555
Генерал Хенрик
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Генерал Хенрик ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.

У одного медведя есть N строк (обозначим i -ю из них x i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x i и x j ( i < j ) могут принадлежать одной такой последовательности, если x i является и префиксом, и суффиксом x j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.

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

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

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

Выведите одно число – ответ на вопрос любопытного генерала Хендрика.

Примечание

В первом примере наибольшая последовательность A -> AA -> AAA В третьем примере наибольшая последовательность A -> A -> A или B -> B -> B

Примеры
Входные данные
5
A
B
AA
BBB
AAA
Выходные данные
3
Входные данные
5
A
ABA
BBB
ABABA
AAAAAB
Выходные данные
3
Входные данные
6
A
B
A
B
A
B
Выходные данные
3
#113556
Вудист Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Вудист Мирко ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Юный Мирко решил купить куклу вуду. Учитывая что он крайне заинтересован в том, ктобы купить ее как можно дешевле, он начал отслеживать цены на кукол вуду каждый день. Его список состоит из цен на куклы в последние N дней, где a i обозначает цену куклы i дней назад.

Мирко думает, что нашел связь между средней ценой кукол в течении нескольких последовательных дней и ценой куклы в следующий день. Он хочет проверить свою догадку и задался вопросом: "Для данного числа P , сколько существует наборов последовательных дней в течении последних N дней, для которых средняя цена куклы в эти дни составляет не менее P ".

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

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ \(10^6\) ), количество дней в списке Мирко. Вторая строка содержит N целых чисел a i ( 0 ≤ a i ≤\(10^9\) ) - цены кукол в соответствующие дни. Третья строка содержит одно целое число P ( 0 ≤ P ≤\(10^9\) ).

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

Выведите одно целое число - ответ на вопрос Мирко для данного P .

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