Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы
    НОД и алгоритм Евклида(45 задач)
    Системы счисления(36 задач)
    "Длинная" арифметика(58 задач)
    Простые числа и разложение на множители(45 задач)
    Остатки(21 задач)
    Быстрое возведение в степень(3 задач)
    Быстрое преобразование Фурье(3 задач)
---> 6 задач <---
Источники --> Личные олимпиады --> COCI
    COCI 2016-2017(0 задач)
    COCI 2015-2016(36 задач)
    COCI 2014-2015(0 задач)
Страница: 1 2 >> Отображать по:
#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
#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
#113576
Хамелеоны Эндора
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Хамелеоны Эндора ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На лесистой луне Эндора находится, если верить Имперской Книге Рекордов, самая длинная ветка в галактике. На этой ветке длиной L метров сидит N дружелюбных хамелеонов. Каждый хамелеон ходит вдоль ветки со скоростью 1 м/с в одном из двух возможных направлений (налево или направо), а также имеет собственный цвет среди одного из K возможных.

Известно, что хамелеоны на Эндоры следуют древним законам, в соответствии с которыми любая прогулка вдоль ветки должна продолжаться до ее конца (после чего хамелеон спрыгивает с ветки), а в случае столкновения двух хамелеонов, они должны развернуться на 180 градусов и продолжить движение в противоположном направлении. Кроме того, при таком столкновении, если хамелеон, двигавшийся налево, имел цвет a , а хамелеон, двигавшийся направо - цвет b , то после разворота первый хамелеон изменит свой цвет на b , а второй хамелеон - на ( a + b ) modK .

Вам даны изначальные цвета, положения и направления движения всех хамелеонов. Определите для каждого цвета, какое расстояние пройдут хамелеоны, находящиеся в этом цвете, до того момента, пока не спрыгнут с ветки.

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

В первой строке содержится три целых числа числа N , K и L ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 40 , 1 ≤ L ≤ 1000000 ). В последующих N строках дана информация о хамелеонах. В i -й строке содержатся: целое число d i ( 1 ≤ d i ≤ L ) - изначальное положение, целое число b i ( 1 ≤ b i ≤ K - 1 ) - изначальный цвет, и символ "L" (налево) или "D" (направо) - изначальное направление движения. Гарантируется, что все числа d i различны и даны в возрастающем порядке.

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

Выведите K строк, i -я строка должна содержать одно число - расстояние, пройденное хамелеонами цвета i .

Примечание

Решения, работающие при 1 ≤ Nle 3000 , будут оцениваться в 50 баллов.

Примеры
Входные данные
2 3 10
0 0 D
10 1 L
Выходные данные
10.0
10.0
0.0
Входные данные
4 3 7
1 0 D
3 0 D
4 1 L
6 2 D
Выходные данные
10.0
4.0
1.0
Входные данные
4 4 5
1 1 D
3 3 L
4 2 D
5 0 L
Выходные данные
2.5
4.0
2.5
4.0
#113579
Пианистка Перика
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Пианистка Перика ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Перика начала играть на пианино. Оно у нее особенное - на нем есть N клавиш, и на каждой написано число a i . В процессе игры Перика одновременно нажимает K клавиш, но так как пианино особенное, звук издаст только клавиша с наибольшим числом среди нажатых. Перика собирается нажать каждую из возможных комбинаций из K клавиш и хочет знать сумму чисел на тех клавишах, которые при этом издадут звуки.

Помогите Перике и ответьте на ее вопрос. Так как ответ может быть очень большим, выведите его по модулю 1 000 000 007.

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

В первой строке содержатся два целых числа N и K ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 50 ). Во второй строке содержатся N целых чисел a i ( 0 ≤ a i ≤ 10 9 ) - числа на клавишах пианино.

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

В единственной строке выведите одно целое число - ответ на вопрос Перики по модулю 1000000007.

Примечание

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

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