Processing math: 42%

4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе


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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Дано простое P, натуральное n и массив a размера n. Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на P что и сумма. Более формально, если выполняется условие xy mod P=(x+y) mod P то пара (x,y) считается хорошей. Найдите количество хороших пар в массиве.
Формат входного файла
В первой строке входного файла заданы два целых числа n (1<=n<=105) — количество чисел в массиве, P (2<=P<=109) — заданное простое число P. Во второй строке входного файла заданы n чисел ai (0<=ai<=109) - i-число в массиве.
Формат выходного файла
Выведите одно целое число - количество хороших пар в массиве.
Система оценки
Данная задача содержит четыре подзадачи:
  1. 1<=n<=1000,2<=p<=1000. Оценивается в 20 баллов.
  2. 1<=n<=1000,p=2. Оценивается в 20 баллов.
  3. 1<=n<=100000,2<=p<=1000. Оценивается в 20 баллов.
  4. 1<=n<=100000,2<=p<=109. Оценивается в 40 баллов.
Примеры:
Вход
4 3
3 5 12 11
Ответ
2
Вход
3 5
1 2 7
Ответ
1
Замечание
Число называется простым если оно делится только на себя и на единицу. (например: 2,3,5,7,11,13,17,) Запись a mod b обозначает взятие остатка от деления числа a на b.
  • В первом тестовом примере подходят только 2 пары: (3,12),(5,11) так как (3+12) mod 3 = (312) mod 3 и (5+11) mod 3 = (511) mod 3
  • {Во втором тестовом примере подходит только 1 пара: (2+7) mod 5 = (27) mod 5}

комментарий/решение(8) Проверить мое решение

Задача 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. 1 <= n <= 1000, k = 1. Оценивается в 15 баллов.
  2. 1 <= n <= 1000, 1 <= k <= 8. Оценивается в 19 баллов.
  3. 1 <= n <= 100, 1 <= k <= 20. Оценивается в 31 баллов.
  4. 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).

комментарий/решение(2) Проверить мое решение

Задача 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. 1 <= n <= 1000, 1 <= q <= 1000, 1 <= a_i <= 10^9. Оценивается в 8 баллов.
  2. 1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= a_{i + 1} <= 10^9. Оценивается в 9 баллов.
  3. 1 <= n <= 100000, 1 <= q <= 10000, 1 <= a_i <= 10^9. Оценивается в 19 баллов.
  4. 1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 100. Оценивается в 15 баллов.
  5. 1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 10^9. Оценивается в 31 баллов.
  6. 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.

комментарий/решение(1) Проверить мое решение