Codeforces Round 700 (Div. 2) |
---|
Закончено |
У Гомера есть два друга — Алиса и Боб. Оба они фанаты строк.
Однажды Алиса и Боб решили сыграть в игру на строке $$$s = s_1 s_2 \dots s_n$$$ длиной $$$n$$$, состоящей из строчных английских букв. Они ходят по очереди, Алиса начинает.
В свой ход игрок должен выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$), который не был выбран ранее, и поменять $$$s_i$$$ на любую другую строчную английскую букву $$$c$$$, удовлетворяющую $$$c \neq s_i$$$.
Когда все индексы уже были выбраны по одному разу, игра заканчивается.
Цель Алисы — сделать финальную строку лексикографически как можно меньше, в то время как цель Боба — сделать финальную строку лексикографически как можно больше. Оба они являются профессиональными игроками, поэтому всегда играют оптимально. Гомер не является профессиональным игроком, поэтому ему интересно, какой будет финальная строка.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:
Каждый тест содержит несколько наборов входных данных. Первая строка содержит $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.
Единственная строка каждого набора входных данных содержит одну строку $$$s$$$ ($$$1 \leq |s| \leq 50$$$), состоящую из строчных английских букв.
Для каждого набора входных данных выведите финальную строку в отдельной строке.
3 a bbbb az
b azaz by
В первом наборе входных данных: Алиса делает первый ход и должна поменять единственную букву на другую, поэтому она меняет ее на «b».
Во втором наборе входных данных: Алиса меняет первую букву на «a», затем Боб меняет вторую букву на «z», Алиса меняет третью букву на «a», а затем Боб меняет четвертую букву на «z».
В третьем наборе входных данных: Алиса меняет первую букву на «b», а затем Боб меняет вторую букву на «y».
Название |
---|