Темы --> Информатика --> Другое
    Разбор случаев(6 задач)
    Теория вероятностей(3 задач)
    Конструктив(21 задач)
    Формула(17 задач)
    Комбинаторика(9 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников --> 2012-2013 --> Заключительный этап - второй тур
Страница: 1 Отображать по:
#112032
Перемешивание
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Каждое утро капитан Ъ проводит занятия по строевой подготовке в возглавляемой им роте солдат. Всего в роте N солдат, каждый из которых носит форму определенного цвета. Различных цветов формы не более 26, так что для удобства солдаты обозначают цвета строчными латинскими буквами. Таким образом, каждому из \(N\) солдат соответствует буква от 'a' до 'z' — цвет его формы.

За многие месяцы службы солдаты выяснили, что капитан пребывает в наилучшем расположении духа в том случае, когда цвета формы солдат в шеренге образуют определенную последовательность. Недолго думая, они выписали соответствующую строку \(S\) из \(N\) букв на асфальте и договорились, что отныне каждый должен при построении вставать именно на ту букву, которая соответствует цвету его формы.

Но к 23 февраля солдаты решили удивить капитана и поменяться местами так, чтобы \(каждый\) солдат встал не на ту букву, которая соответствует цвету его формы. Так, солдат с цветом формы 'q' может встать на любую букву, кроме буквы 'q', иначе удивление капитана будет недостаточным.

Помогите солдатам организовать праздничное построение: по данной строке \(S\), обозначающей старую последовательность цветов, выведите строку \(T\), являющуюся перестановкой символов строки \(S\) и обозначающую новую последовательность цветов. i-й символ строки T должен отличаться от i-го символа строки \(S\).

Входные данные

В первой строке входного файла содержится единственное целое число \(N\) — количество солдат в роте \((1 \le N \le 100 000)\). Во второй строке содержится строка S, состоящая из \(N\) строчных латинских букв.

Выходные данные

Единственная строка выходного файла должна содержать искомую строку \(T\), если задумка солдат осуществима, и «Impossible» в противном случае. Если верных ответов несколько, выведите любой из них.

Система оценки

Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3—21. В тестах этой группы \(N \le 9\). Эта группа оценивается в 30 баллов.

2. Тесты 22—36. В тестах этой группы \(N \le 200\), а строка не может содержать никаких букв, кроме 'a', 'b' и 'c'. Эта группа оценивается в 30 баллов независимо от первой.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
9
olimpiada
Выходные данные
iapdialom
Входные данные
7
baaaaaa
Выходные данные
Impossible
#112033
Берляндолимпстрой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Скоро в Берляндии пройдет очередная Олимпиада. В рамках подготовки к этому важному мероприятию Берляндолимпстрой уже возвел N объектов и теперь хочет разобраться с тем, во сколько Берляндии это обошлось.

Стройка длилась \(K + 1\) день со дня номер \(0\) по день номер \(K\), причем стоимость j-го объекта в нулевой день была равна \(a_j\) бурлям. Однако каждый следующий день стоимость каждого объекта увеличивалась согласно следующему правилу: стоимость j-го объекта в i-й день становилась равна сумме стоимостей всех объектов с номерами, меньшими или равными j, в предыдущий день. Иначе говоря, \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\), где \(S_{i,j}\) — стоимость j-го объекта в i-й день. В итоге на j-й объект было потрачено \(S_{K,j}\) , то есть его стоимость в последний \(K\)-й день. \t{Назовем эту величину итоговой стоимостью j-го объекта.}

Такие увеличения стоимостей проектов для Берляндии не редкость, однако оказалось, что и этих денег не хватило! Выяснилось, что в некоторый день i > 0 стоимость некоторого объекта j дополнительно повысилась на пока не известную следователям сумму X (то есть \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\) + X), что повлияло на стоимости объектов в последующие дни. Следователи выяснили, что из-за этого сумма итоговых стоимостей всех объектов увеличилась на \(R\) бурлей.

Помогите следователям выяснить минимально возможное значение X.

Входные данные

В первой строке входного файла содержатся три целых числа \(N\), \(K\), \(R\): количество олимпийских объектов (\(1 \le N \le 10^5\) ), количество дней увеличения стоимости объектов (\(1 \le K \le 10^5\) ) и количество бурлей, на которое незаконно возросла итоговая сумма (\(1 \le R \le 10^{18}\)). В следующей строке входного файла содержатся N целых чисел \(a_i\) — стоимости объектов в нулевой день (\(1 \le a_i \le 10^9\)).

Выходные данные

Единственная строка выходного файла должна содержать единственное целое число — минимально возможное значение \(X\)

Система оценки

Тесты к этой задаче состоят из четырех групп.

0. Тест 1. Тест из условия, оцениваемый в ноль баллов.

1. Тесты 2—25. В тестах этой группы \(N \le 10, K \le 10, a_i \le 10\), искомое значение \(X\) не превосходит \(10\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

2. Тесты 26—38. В тестах этой группы \(N \le 1 000, K \le 1 000\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Тесты в этой группе оцениваются \t{независимо}

Примеры
Входные данные
3 3 12
1 3 3
Выходные данные
2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест