Задача A. Игра ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:2 сек
Входной файл:game.in   Ограничение памяти:64 Мб
Выходной файл:game.out  
Максимальный балл:100  

Условие

Два игрока играют в следующую игру:

  1. Дана строка.
  2. Игроки по очереди стирают один символ с начала или конца строки, после чего дописывают его в конец результата.
  3. Цель первого игрока состоит в том, чтобы результирующая строка была как можно больше (в лексикографическом порядке), а цель второго — чтобы она была как можно меньше.
Определите полученный результат в предположении, что оба игрока играют оптимально.

Формат входного файла

В единственной строке входного файла записана строка, состоящая из строчных латинских букв, длиной не более 100 символов.

Формат выходного файла

Выведите единственную строку — полученный результат при оптимальной игре обоих игроков.

Примеры тестов

№ Входной файл (game.in) Выходной файл (game.out)
1 
abcde
 
eadbc
2 
aaaca
 
aacaa

Задача B. Выходные ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:2 сек
Входной файл:holidays.in   Ограничение памяти:64 Мб
Выходной файл:holidays.out  
Максимальный балл:100  

Условие

В огромной международной компании работает n программистов. Все программисты работают удаленно, а общаются только по телефону или ICQ. Проблема состоит в том, что все они живут в разных странах. В этих странах разные традиции и разные праздники. Компания уважает государственные праздники всех своих сотрудников, поэтому не может заставлять их выходить на работу в такие дни. Сейчас перед советом директоров фирмы стоит задача назначить одного из программистов руководителем проекта. Но если руководитель приходит на работу и не может связаться с одним из своих сотрудников (так как у него выходной), то он недоволен.

Если он не может связаться более, чем с k сотрудниками, то руководитель просто приходит в ярость. Скажем, что степень недовольства в некоторый рабочий день руководителя вычисляется как количество сотрудников, с которыми он не может связаться. Если руководитель приходит в ярость, то степень его недовольства в этот день равна 10 ⋅ k.

Совет директоров принял решение, что руководителем проекта нужно назначить человека, суммарная степень недовольства которого за все время работы будет минимальным. (Главное — моральное состояние сотрудников. Совершенно не важна квалификация руководителя). Несмотря на то, что в фирме огромное количество программистов высокого уровня, которые бы с легкостью справились с этой задачей, никому из них нельзя доверить ее решение, так как они заинтересованы стать руководителями проекта сами. Поэтому решение этой задачи поручается независимому эксперту, то есть Вам.

Формат входного файла

Во входном файле содержится два числа — n и k. Далее в n строках следует описание праздников каждого из программистов. Сначала записано количество государственных праздников p, а затем следует p пар чисел l и r, задающие непересекающиеся отрезки праздников в соответствующей стране. Обратите внимание, что, хотя отрезки, задающие праздники в одной стране, пересекаться не могут, в различных странах могут быть праздники в один и тот же день.

Формат выходного файла

В выходной файл выведите ответ — номер программиста, которого нужно назначить руководителем. Программисты нумеруются с 1 в порядке их задания во входном файле. Если существует несколько вариантов, то выберите программиста с наименьшим номером. (Программисты записаны в порядке уменьшения их квалификации).

Ограничения

1 ≤ n, k ≤ 105

0 ≤ p ≤ 105

1 ≤ l ≤ r ≤ 105

Суммарное количество отрезков не превосходит 105.

Все числа во входном файле целые.

Примеры тестов

№ Входной файл (holidays.in) Выходной файл (holidays.out)
1 
2 1
2 1 3 5 10
1 4 4
 
1
2 
3 1
1 1 1
2 1 2 5 7
1 2 10
 
2

Задача C. Переворачивания ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:5 сек
Входной файл:reverse.in   Ограничение памяти:64 Мб
Выходной файл:reverse.out  
Максимальный балл:100  

Условие

Учитель физкультуры школы с углубленным изучением предметов уже давно научился считать суммарный рост всех учеников, находящихся в ряду на позициях от l до r. Но дети играют с ним злую шутку. В некоторый момент дети на позициях с l по r меняются местами. Учитель заметил, что у детей не очень богатая фантазия, поэтому они всегда "переворачивают" этот отрезок, т. е. l меняется с r, l + 1 меняется с r − 1 и так далее. Но учитель решил не ругать детей за их хулиганство, а все равно посчитать суммарный рост на всех запланированных отрезках.

Формат входного файла

В первой строке записано два числа n и m — количество детей в ряду и количество событий, произошедших за все время. Во второй строке задано n натуральных чисел — рост каждого школьника в порядке следования в ряду. Далее в m строках задано описание событий: три числа q, l, r в каждой строке. Число q показывает тип события: 0 показывает необходимость посчитать и вывести суммарный рост школьников на отрезке [l, r]; 1 показывает то, что дети на отрезке [l, r] "перевернули" свой отрезок. Все числа во входном файле целые.

Формат выходного файла

Для каждого события типа 0 выведите единственное число на отдельной строке — ответ на этот запрос.

Ограничения

1 ≤ n, m ≤ 2 ⋅ 105

Рост детей не превосходит 2 ⋅ 105.

0 ≤ q ≤ 1

1 ≤ l ≤ r ≤ n

Примеры тестов

№ Входной файл (reverse.in) Выходной файл (reverse.out)
1 
5 6
1 2 3 4 5
0 1 5
0 2 4
1 2 4
0 1 3
0 4 5
0 3 5
 
15
9
8
7
10
0.330s 0.015s 17