Областная олимпиада по информатике, 2018 год, 10-11 класс
(Тима и Рама) На доске в ряд написано $N$ целых чисел. Темірлан и Рамазан играют в следующую игру:
Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?
Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.
Ограничения которые присутствуют в тестах:
посмотреть в олимпиаде
- Они будут ходить по очереди, первым начинает Темірлан.
- На каждом ходу игрок может стереть с доски любое ненулевое количество чисел с начала, или с конца. Но нельзя стереть все числа.
- Игра закончится, когда на доске останется ровно одно число. Темірлан хочет минимизировать последнее число, а Рамазан хочет максимизировать это число.
Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число $N$.Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.
Формат выходных данных:
Выведите через пробел $Q$ чисел, $i$-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет $K_i$ чисел.Примеры:
1.Вход:4 1 4 2 3 4 0 1 2 3Ответ:
1 3 3 42.Вход:
3 5 5 5 3 0 1 2Ответ:
5 5 53.Вход:
6 2 7 5 4 8 10 3 3 5 2Ответ:
7 10 7
Замечание:
В первом тесте при $K=3$, Рамазану выгодно стереть первое,второе и четвертое числа.Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 3 теста: Первые три теста является тестами из примеров
- 5 тестов: $1 \le N \le 3, Q = 1, K_1 = 0$
- 10 тестов: $1 \le N \le 100, Q = 1, K_1 = 0$
- 12 тестов: $1 \le N \le 10^5, 1\le Q \le 2, 0 \le K_i \le 1$
- 10 тестов: $1 \le N \le 10^5, 1 \le Q \le 10^5,0 \le K_i \le N - 1$
- 10 тестов: $1 \le N \le 10^6, 1 \le Q \le 10^6, 0 \le K_i \le N - 1$
Комментарий/решение:
Работает на претестах но говорит "ошибка проверки" что это значит?
Можно доказать, если есть последовательность $a_1, a_2, ..., a_n$ то в конце останется число $min(a_1,a_n)$
Для того что бы получить число С мы должны на префиксе жадно удалить все числа меньше С и на суффиксе тоже. Если удалили $len$ чисел то $ans[len] >= C$.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.