қазақша
русскийNurlykhan Kairly
Задача №1.
Задача B. Array
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
Дан массив $a$ длины $k$. Так же, имеются $n$ массивов длины $k$. Массив $x$ называется хорошим, если существует перестановка $p$ длины $k$, такая что для каждого $i$ $(1 <= i <= k)$ выполняется $x_{p_i} \equiv 0 \pmod{a_i}$. Вам необходимо посчитать количество пар $(l, r)$ $(1 <= l <= r <= n)$, таких что количество хороших массивов в отрезке больше чем нехороших.
Формат входного файла
В первой строке входных данных даются числа $n$ и $k$ $(1 <= n <= 10^5, 1 <= k <= 20)$.
Во второй строке входных данных даётся массив $a$ длины $k$ $(1 <= a_i <= 10^9)$.
В следующих $n$ строк даются массивы длины $k$, где в $i$-ой содержится массив $b_i$ $(1 <= b_{ij} <= 10^9,$ где $1 <= i <= k)$.
Формат выходного файла
В единственной строке выходных данных выведите одно число - ответ на задачу.
Система оценки
Данная задача содержит четыре подзадачи:
- $1 <= n <= 1000, k = 1$. Оценивается в $15$ баллов.
- $1 <= n <= 1000, 1 <= k <= 8$. Оценивается в $19$ баллов.
- $1 <= n <= 100, 1 <= k <= 20$. Оценивается в $31$ баллов.
- $1 <= n <= 10^5, 1 <= k <= 8$. Оценивается в $35$ баллов.
Пример:
Вход 3 1 2 1 2 2Ответ
4
Замечание
$a \equiv 0 \pmod{b}$ - означает что число $a$ делится на $b$ без остатка.
В первом тестовом примере, пары $(1, 1)$ и $(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно $0$ $(0 <= 1)$, а во втором равно $1$ $(1 <= 1)$.
(
Nurlykhan Kairly
)
комментарий/решение(2) олимпиада
Задача №2.
Задача B. Array
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
Дан массив $a$ длины $k$. Так же, имеются $n$ массивов длины $k$. Массив $x$ называется хорошим, если существует перестановка $p$ длины $k$, такая что для каждого $i$ $(1 <= i <= k)$ выполняется $x_{p_i} \equiv 0 \pmod{a_i}$. Вам необходимо посчитать количество пар $(l, r)$ $(1 <= l <= r <= n)$, таких что количество хороших массивов в отрезке больше чем нехороших.
Формат входного файла
В первой строке входных данных даются числа $n$ и $k$ $(1 <= n <= 10^5, 1 <= k <= 20)$.
Во второй строке входных данных даётся массив $a$ длины $k$ $(1 <= a_i <= 10^9)$.
В следующих $n$ строк даются массивы длины $k$, где в $i$-ой содержится массив $b_i$ $(1 <= b_{ij} <= 10^9,$ где $1 <= i <= k)$.
Формат выходного файла
В единственной строке выходных данных выведите одно число - ответ на задачу.
Система оценки
Данная задача содержит четыре подзадачи:
- $1 <= n <= 1000, k = 1$. Оценивается в $15$ баллов.
- $1 <= n <= 1000, 1 <= k <= 8$. Оценивается в $19$ баллов.
- $1 <= n <= 100, 1 <= k <= 20$. Оценивается в $31$ баллов.
- $1 <= n <= 10^5, 1 <= k <= 8$. Оценивается в $35$ баллов.
Пример:
Вход 3 1 2 1 2 2Ответ
4
Замечание
$a \equiv 0 \pmod{b}$ - означает что число $a$ делится на $b$ без остатка.
В первом тестовом примере, пары $(1, 1)$ и $(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно $0$ $(0 <= 1)$, а во втором равно $1$ $(1 <= 1)$.
(
Nurlykhan Kairly
)
комментарий/решение(2) олимпиада