Nurdaulet Akhanov

Задача №1.

Задача B. Делимость

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на 8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ.

Формат входного файла

В первой строке дано цело число

$n$

$(1 \leq n \leq 10^3)$ - длинна числа.

$\\$ Во второй строка дана строка состоящая из цифр

$s$ - число которое надо проверить.

Формат выходного файла

Выведите YES если число делится на 8 по правилам ОМЫ иначе NO

Примеры:

Вход

2
23

Ответ

YES

Вход

3
101

Ответ

NO

Замечание

Перестановка числа х - это число, состоящее из тех же цифр, что и х, но в другом порядке. Например, числа, которые можно получить путем перестановки цифр числа 123: 132, 213, 231, 312, 321 В первом примере из числа 23 можно получить делящееся на 8 число 32, ответ YES. Во втором примере из числа 101 невозможно получить число делящееся на 8, ответ NO.

$\\$

$\\$ Subtask 1:

$(n \leq 100)$

$\\$ Subtask 2:

$(n \leq 1000)$ ( Nurdaulet Akhanov )
комментарий/решение(10) олимпиада

Задача №2.

Задача C. Хан и массив

Ограничение по времени:

2 секунды

Ограничение по памяти:

512 мегабайт

Хан на день рождения получил массив из

$n$ элементов. И начал с ним играться. Он взял каждый элемент и записал

$m$ раз. Также у Хана есть любимое простое число

$P$ . Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на

$P$ . Помогите Хану узнать сколько таких подпоследовательностей.

Формат входного файла

В первой строке даны три целых числа

$n$ ,

$m$ ,

$P$ через пробел — размер массива Хана; количество раз, которое он записывает каждое число в массиве; и простое число соответственно

$(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$ . Во второй строке даны

$n$ целых чисел

$a_1, a_2, ..., a_n$ — полученный Ханом массив на его день рождения

$(1 <= a_i <= 10^9)$ .

Формат выходного файла

Выведите одно число — количество подпоследовательностей, которые в сумме делятся на

$P$ . Так как это число может быть большим, выведите его остаток от деления на

$1000000007$ .

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

Подзадача 1 (10 баллов) —

$n <= 10^5$ ,

$m <= 10^5,$

$P = 2$ . Подзадача 2 (10 баллов) —

$n * m <= 20$ ,

$P <= 1000$ . Подзадача 3 (10 баллов) —

$n * m * P <= 10^6,$ . Подзадача 4 (20 баллов) —

$n * m <= 250000$ ,

$P <= 500$ . Подзадача 5 (50 баллов) —

$n <= 10^5$ ,

$m <= 10^9$ ,

$P <= 1000$ .

Пример:

Вход

3 2 5
3 7 4

Ответ

Замечание

Хан преобразует изначальный массив следующим образом. Пусть

$a_1, a_2, ..., a_n$ будет изначальным массивом. И заведем пустой массив

$b$ . Один за одним, слева направо будем обрабатывать элементы массива

$a$ и элемент

$a_i$ припишем к

$b$ ровно

$m$ раз. Хан будет решать задачу над полученным массивом

$b$ . Подпоследовательность — последовательность, которая получается путем удаления нескольких, возможно ноль, элементов изначальной последовательности. В первом примере, массив

$b$ будет выглядеть следующим образом:

$3, 3, 7, 7, 4, 4$ . Вот все

$11$ подпоследовательности, сумма которых делится на

$5$ :

$[3, 7]$ ,

$[3, 3, 4]$ ,

$[3, 3, 7, 7]$ ,

$[7, 4, 4]$ ,

$[7, 4, 4],$ [3, 7, 7, 4, 4],

$[3, 7, 7, 4, 4]$ . ( Nurdaulet Akhanov )
комментарий/решение(2) олимпиада

Задача №3.

Задача C. Хан и массив

Ограничение по времени:

2 секунды

Ограничение по памяти:

512 мегабайт

Хан на день рождения получил массив из

$n$ элементов. И начал с ним играться. Он взял каждый элемент и записал

$m$ раз. Также у Хана есть любимое простое число

$P$ . Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на

$P$ . Помогите Хану узнать сколько таких подпоследовательностей.

Формат входного файла

В первой строке даны три целых числа

$n$ ,

$m$ ,

$(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$ . Во второй строке даны

$n$ целых чисел

$a_1, a_2, ..., a_n$ — полученный Ханом массив на его день рождения

$(1 <= a_i <= 10^9)$ .

Формат выходного файла

Выведите одно число — количество подпоследовательностей, которые в сумме делятся на

$P$ . Так как это число может быть большим, выведите его остаток от деления на

$1000000007$ .

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

Подзадача 1 (10 баллов) —

$n <= 10^5$ ,

$m <= 10^5,$

$P = 2$ . Подзадача 2 (10 баллов) —

$n * m <= 20$ ,

$P <= 1000$ . Подзадача 3 (10 баллов) —

$n * m * P <= 10^6,$ . Подзадача 4 (20 баллов) —

$n * m <= 250000$ ,

$P <= 500$ . Подзадача 5 (50 баллов) —

$n <= 10^5$ ,

$m <= 10^9$ ,

$P <= 1000$ .

Пример:

Вход

3 2 5
3 7 4

Ответ

Замечание

Хан преобразует изначальный массив следующим образом. Пусть

$a_1, a_2, ..., a_n$ будет изначальным массивом. И заведем пустой массив

$b$ . Один за одним, слева направо будем обрабатывать элементы массива

$a$ и элемент

$a_i$ припишем к

$b$ ровно

$m$ раз. Хан будет решать задачу над полученным массивом

$b$ будет выглядеть следующим образом:

$3, 3, 7, 7, 4, 4$ . Вот все

$11$ подпоследовательности, сумма которых делится на

$5$ :

$[3, 7]$ ,

$[3, 3, 4]$ ,

$[3, 3, 7, 7]$ ,

$[7, 4, 4]$ ,

$[7, 4, 4],$ [3, 7, 7, 4, 4],

$[3, 7, 7, 4, 4]$ . ( Nurdaulet Akhanov )
комментарий/решение(2) олимпиада

Задача №4.

Задача A. Найдите все пары

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Дано простое

$P$ , натуральное

$n$ и массив

$a$ размера

$n$ . Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на

$P$ что и сумма. Более формально, если выполняется условие

$x * y$

$mod$

$P = (x + y)$

$mod$

$P$ то пара

$(x, y)$ считается хорошей. Найдите количество хороших пар в массиве.

Формат входного файла

В первой строке входного файла заданы два целых числа

$n$

$(1 <= n <= 10^5)$ — количество чисел в массиве,

$P$

$(2 <= P <= 10^9)$ — заданное простое число

$P$ . Во второй строке входного файла заданы

$n$ чисел

$a_i$

$(0 <= a_i <= 10^9)$ -

$i$ -число в массиве.

Формат выходного файла

Выведите одно целое число - количество хороших пар в массиве.

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

Данная задача содержит четыре подзадачи:

$1 <= n <= 1000, 2 <= p <= 1000$ . Оценивается в $20$ баллов.
$1 <= n <= 1000, p = 2$ . Оценивается в $20$ баллов.
$1 <= n <= 100000, 2 <= p <= 1000$ . Оценивается в $20$ баллов.
$1 <= n <= 100000, 2 <= p <= 10^9$ . Оценивается в $40$ баллов.

Примеры:

Вход

4 3
3 5 12 11

Ответ

Вход

3 5
1 2 7

Ответ

Замечание

Число называется простым если оно делится только на себя и на единицу. (например:

$2, 3, 5, 7, 11, 13, 17, \dots$ ) Запись

$a$

$mod$

$b$ обозначает взятие остатка от деления числа

$a$ на

$b$ .

В первом тестовом примере подходят только 2 пары: $(3, 12), (5, 11)$ так как $(3 + 12)$ mod $3$ = $(3 * 12)$ mod $3$ и $(5 + 11)$ mod $3$ = $(5 * 11)$ mod $3$
{Во втором тестовом примере подходит только 1 пара: $(2 + 7)$ mod $5$ = $(2 * 7)$ mod $5$ }

( Nurdaulet Akhanov )
комментарий/решение(8) олимпиада

Задача №5.

Задача C. Поиск медианы

Ограничение по времени:

3 секунды

Ограничение по памяти:

512 мегабайт

Дан массив чисел

$a$ длинны

$n$ и

$q$ запросов. Каждый из запросов описывается числами

$l$ и

$r$ . Для каждого из запросов нужно найти, какой будет медиана в массиве, если удалить числа из массива от

$l$ до

$r$ .

Формат входного файла

В первой строке входных данных подаются 2 числа

$n, q$

$(1 <= n, q <= 10^6)$ — количество чисел в массиве и количество запросов. Во второй строке входных данных подаются

$n$ целых чисел

$a_i$

$(1 <= a_i <= 10^9)$ —

$i$ -й элемент массива

$a$ . В последующих

$q$ строках подаются по два целых числа

$l, r$

$(1 <= l <= r <= n)$ — границы удаляемого отрезка. Гарантируется что в оставшемся массиве будет хотя бы один элемент.

Формат выходного файла

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

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

Данная задача содержит шесть подзадач:

$1 <= n <= 1000, 1 <= q <= 1000, 1 <= a_i <= 10^9$ . Оценивается в $8$ баллов.
$1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= a_{i + 1} <= 10^9$ . Оценивается в $9$ баллов.
$1 <= n <= 100000, 1 <= q <= 10000, 1 <= a_i <= 10^9$ . Оценивается в $19$ баллов.
$1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 100$ . Оценивается в $15$ баллов.
$1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 10^9$ . Оценивается в $31$ баллов.
$1 <= n <= 500000, 1 <= q <= 1000000, 1 <= a_i <= 10^9$ . Оценивается в $18$ баллов.

Пример:

Вход

Ответ

Замечание

Медианой массива длинны

$n$ называется элемент который стоит на позиции

$\frac{n+1}{2}$ в отсортированном виде. В первом примере, после проведения первой операции, удалится отрезок

$[2, 1, 4]$ и останется

$[1, 9]$ . Так как длинна оставшегося массива равна

$2$ , позиция на которой попадает медиана равна

$\frac{3}{2} = 1$ . После проведения второй операции, удалится отрезок

$[1]$ и останется

$[2, 1, 4, 9]$ . Так как длинна оставшегося массива равна

$4$ , позиция на которой попадает медиана равна

$\frac{5}{2} = 2$ . Вторым элементом в отсортированном оставшемся массиве будет

$2$ . После проведения третьей операции, удалится отрезок

$[4, 9]$ и останется

$[1, 2, 1]$ . Так как длинна оставшегося массива равна

$3$ , позиция на которой попадает медиана равна

$\frac{4}{2} = 2$ . Вторым элементом в отсортированном оставшемся массиве будет

$1$ . ( Nurdaulet Akhanov )
комментарий/решение(1) олимпиада