Processing math: 100%

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) выполняется xpi0(modai). Вам необходимо посчитать количество пар (l,r) (1<=l<=r<=n), таких что количество хороших массивов в отрезке больше чем нехороших.
Формат входного файла
В первой строке входных данных даются числа n и k (1<=n<=105,1<=k<=20). Во второй строке входных данных даётся массив a длины k (1<=ai<=109). В следующих n строк даются массивы длины k, где в i-ой содержится массив bi (1<=bij<=109, где 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<=105,1<=k<=8. Оценивается в 35 баллов.
Пример:
Вход
3 1
2
1
2
2
Ответ
4
Замечание
a0(modb) - означает что число 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<=106) — количество чисел в массиве и количество запросов. Во второй строке входных данных подаются n целых чисел ai (1<=ai<=109)i-й элемент массива a. В последующих q строках подаются по два целых числа l,r (1<=l<=r<=n) — границы удаляемого отрезка. Гарантируется что в оставшемся массиве будет хотя бы один элемент.
Формат выходного файла
Для каждого запроса выведите ответ в отдельной строке, медиана оставшегося массива.
Система оценки
Данная задача содержит шесть подзадач:
  1. 1<=n<=1000,1<=q<=1000,1<=ai<=109. Оценивается в 8 баллов.
  2. 1<=n<=100000,1<=q<=100000,1<=ai<=ai+1<=109. Оценивается в 9 баллов.
  3. 1<=n<=100000,1<=q<=10000,1<=ai<=109. Оценивается в 19 баллов.
  4. 1<=n<=100000,1<=q<=100000,1<=ai<=100. Оценивается в 15 баллов.
  5. 1<=n<=100000,1<=q<=100000,1<=ai<=109. Оценивается в 31 баллов.
  6. 1<=n<=500000,1<=q<=1000000,1<=ai<=109. Оценивается в 18 баллов.
Пример:
Вход
5 5
1 2 1 4 9
2 4
1 1
4 5
3 4
1 3
Ответ
1
2
1
2
4
Замечание
Медианой массива длинны n называется элемент который стоит на позиции n+12 в отсортированном виде. В первом примере, после проведения первой операции, удалится отрезок [2,1,4] и останется [1,9]. Так как длинна оставшегося массива равна 2, позиция на которой попадает медиана равна 32=1. После проведения второй операции, удалится отрезок [1] и останется [2,1,4,9]. Так как длинна оставшегося массива равна 4, позиция на которой попадает медиана равна 52=2. Вторым элементом в отсортированном оставшемся массиве будет 2. После проведения третьей операции, удалится отрезок [4,9] и останется [1,2,1]. Так как длинна оставшегося массива равна 3, позиция на которой попадает медиана равна 42=2. Вторым элементом в отсортированном оставшемся массиве будет 1.

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