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Ответ
11
Замечание
Хан преобразует изначальный массив следующим образом. Пусть $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, 7]$, $[3, 7]$, $[3, 7]$, $[3, 3, 4]$, $[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$, $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Ответ
11
Замечание
Хан преобразует изначальный массив следующим образом. Пусть $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, 7]$, $[3, 7]$, $[3, 7]$, $[3, 3, 4]$, $[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Ответ
2Вход
3 5 1 2 7Ответ
1
Замечание
Число называется простым если оно делится только на себя и на единицу. (например: $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$}
комментарий/решение(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$ баллов.
Пример:
Вход 5 5 1 2 1 4 9 2 4 1 1 4 5 3 4 1 3Ответ
1 2 1 2 4
Замечание
Медианой массива длинны $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) олимпиада