Темы --> Информатика --> Структуры данных
    Деревья(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 >> Отображать по:
#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
#113539
Продажа картин
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Продажа картин ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
32 megabytes

Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a i цветных картин и не более b i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.

У Луки практически неограниченный запас картин, поэтому запросы клиентов не являются для него проблемой. Однако, Лука не любит продавать черно-белые картины, и если окажется, что меньше, чем C людей купили цветные картины, он очень огорчится.

В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.

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

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 105, 1 ≤ C ≤ 20 ). Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 109 ). Третья строка содержит N целых чисел b i ( 1 ≤ b i ≤ 109 ). Четвертая строка содержит одно целое число Q ( 1 ≤ Q ≤ 105 ) - количество изменений требований клиентов. Каждая из следующих Q строк содержит три числа: номер клиента, меняющего требования P ( 1 ≤ P ≤ N ), новое максимальное количество цветных картин, которое он готов купить A p ( 1 ≤ A p ≤ 109 ) и новое максимальное количество черно-белых картин, которое он готов купить B p ( 1 ≤ B p ≤ 109 ).

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

Выведите Q строк, где в q -й строке записано единственное число - количество вариантов продать картины клиентам, чтобы хотя бы C человек купили цветные картины, по модулю 10007 после первых q изменений требований.

Разбалловка для личной олимпиады

Тесты 4-6 — числа n, q не превосходят 1000. Группа тестов оценивается в 30 баллов.

Тесты 7-13 — Полные ограничения. Группа тестов оценивается в 70 баллов.

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

Мирко большой любитель шахмат и программирования, но обычные шахматы уже наскучили ему, поэтому он начал экспериментировать и придумал свою игру. Он взял шахматную доску с N рядами и N столбцами и расположил на ней K ладей. Игра Мирко следует таким правилам: 1. У каждой ладьи есть своя сила, заданная натуральным числом. 2. Ладья видит все клетки поля в своем ряду и своем столбце кроме той, на которой стоит сама. 3. Клетка считается атакованной в том случае, если побитовый XOR сил всех ладей, которые видят эту клетку, положителен. Изначально Мирко некоторым образом расположил ладьи на поле, и теперь собирается сделать P перемещений. Каждый раз он будет брать одну ладью и ставить ее на другую клетку поля (при этом ладья не обязательно будет перемещена вдоль ряда или столбца в котором она стоит). После каждого перемещения, определите сколько клеток на поле атакованы.

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

Первая строка содержит 3 целых числа N , K , P ( 1 ≤ N ≤ 1000000000 , 1 ≤ K , P ≤ 10000 ). Каждая из следующих K строк содержит 3 натуральных числа R i , C i , X i ( 1 ≤ R i , C i ≤ N , 1 ≤ X i ≤ 1000000000 ), которые обозначают что на клетке ( R i , C i ) стоит ладья с силой X i . Каждая из следующих P строк содержит 4 натуральных числа R 1 , C 1 , R 2 , C 2 ( 1 ≤ R 1, C 1, R 2, C 2 ≤ N ), которые означают что ладья, стоящая на клетке ( R 1, C 1 ), была передвинута на поле ( R 2, C 2 ). Гарантируется, что в момент перемещения на клетке ( R 1, C 1 ) есть ладья и что ни в какой момент времени на одной клетке нет двух и более ладей.

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

Выведите P строк, где в k -й строке записано единственное число - количество клеток поля, атакованных после первых k перемещений.

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