Alex_KPR's blog

By Alex_KPR, 9 years ago, In Russian,

Задача D. Скобочная последовательность

Несомненно, это самая интересная задача контеста. Не пойму, как можно сдать её за 16 минут, как Petr, даже зная решение. Не пойму, как можно сдать её раньше, чем задачу B, как Nerevar (см. достижения справа).

Для её решения рассуждать нужно было, например, следующим образом: давайте вместо знаков вопроса сразу поставим дешевейшую из двух скобок. Если цена открывающей равна A, а закрывающей B, то цена изменения её на противоположную будет |A-B|. Цена изменения бывших "не знаков вопроса" пусть будет равна бесконечности (например, 1015). Получили какую-то фигню из открывающих и закрывающих скобок.

Я и дальше буду использовать термин "фигня", потому что такую же терминологию использовал при рассуждениях во время контеста. В нашей фигне есть X открывающих скобок и Y закрывающих. В правильной скобочной последовательности X=Y. Предположим, что у нас X>Y, тогда возьмём (X-Y)/2 наиболее дешёвых по цене изменения открывающих скобок и заменим их на закрывающие. При Y>X действия аналогичные.

Итак, теперь в нашей фигне X=Y, а это уже почти правильная скобочная последовательность! =) Как проверяется скобочная последовательность на правильность, если в ней X=Y? Конечно, подсчётом баланса: проходим по строке, если символ "(" то увеличим баланс на 1, иначе уменьшим на 1. В том месте, где баланс стал равен -1 (это позиция i), получилась нестыковка. Как её обойти? Оказывается, достаточно просто: найдём самую дешёвую (для замены) открывающую скобку в подстроке [0..i] и самую дешёвую закрывающую скобку в подстроке [i+1..n-1]. Поменяем их на противоположные и этим самым увеличим баланс на 2. И так будем делать каждый раз. Теперь у нас баланс везде неотрицательный... Всё? Ещё нет.

В правильной скобочной последовательности баланс в самом конце равен 0, а у нас может быть какое-нибудь чётное число. Бороться будем так: отразим нашу последовательность зеркально (если было "((()((", то будет "))()))") и повторим ту же процедуру восстановления баланса, что и раньше. Теперь баланс равен 0, X=Y. Значит, получили правильную скобочную последовательность. А так как мы использовали каждый раз самую дешёвую замену, то ответ будет минимальным. Осталось не забыть отразить зеркально обратно перед выводом. =)

И ещё: если где-то самая дешёвая замена равна бесконечности (1015), то ответа не существует. Для того, чтобы быстро находить самую дешёвую открывающую или закрывающую скобку, можно воспользоваться std::set.



Задача A. Кратчайший путь короля

Будем рассуждать просто. Пусть стартовая точка (X0, Y0), финальная точка (X, Y). Очевидно, что если для попадания в финальную точку нужно двигаться по вертикали и горизонтали, то мы вместо двух ходов сделаем один - по диагонали. Утверждение 1: ответ, который нужно вывести - это максимум из |X0-X| и |Y0-Y|. Почему? Очень просто: каждым ходом короля мы можем уменьшать разницу между текущей точкой и финальной как по вертикали, так и по горизонтали одновременно, путешествуя по диагонали. Если, например, |X0-X|>|Y0-Y|, то мы сделаем |Y0-Y| ходов по диагонали, а потом придётся ещё идти горизонтально. А теперь посмотрим внимательно на формат вывода: движение по диагонали выводится как движение по горизонали + движение по вертикали. Значит, основной цикл может выглядеть примерно так:

while(true)

{

  if (x==x0 && y==y0) break; // мы нашли ответ

  if (x>x0) {x0++; cout<<"R";} else // если финальная точка находится справа от текущей, то пойдём вправо

  if (x<x0) {x0--; cout<<"L";} // иначе пойдём влево

  if (y>y0) {y0++; cout<<"D";} else // рассуждения аналогичны

  if (y<y0) {y0--; cout<<"U";}

  cout<<endl;

}



Задача B. Грузовик

Интересная задача. Рассуждать можно по-разному, но ключ - жадное решение. Отсортируем по невозрастанию полезности все байдарки. Возмём каждую пару байдарок и сольём её в катамаран. =) Если осталась какая-то байдарка без пары - ничего страшного. Теперь отсортируем все обычные катамараны, катамараны-мутанты и оставшуюся байдарку опять по невозрастанию полезности, но теперь всех вместе и будем забивать полученными плавсредствами грузовик. Осталось рассмотреть 2 случая. Первый: свободного места уже нет, но катамараны ещё есть. Давайте посмотрим, что же мы положили в конце? Если это две байдарки (тут уже неважно, были ли они с кем-то спарены или нет), то попробуем их вытащить и засунуть самый полезный катамаран. Второй случай: есть место под байдарку, но байдарок больше нет, а есть катамараны. Поступим также: вытащим последнюю байдарку (если она была) и попытаемся разместить катамаран. При рассмотрении каждого из двух случаев необходимо, разумеется, брать максимум из одного и другого результата. Тест на 2-ой случай: 3 3 2 10 1 13 1 7.



Задача C. Крестики-нолики

Давайте узнаем, как определить, какой игрок только что ходил. Если количество крестиков на 1 больше количества ноликов, то ходил первый, а если их количества равны - то второй. Если нельзя определить, какой игрок ходил, то это illegal-ситуация. Посмотрим на игровое поле. Если оба игрока находятся в состоянии победы, то ответ illegal. Если получилось так, что только что ходил первый игрок, а победил второй, то это значит, что первый игрок сделал ход уже после победы второго игрока, следовательно, ответ illegal. Если ситуация разворачивается с точностью до наоборот, то ответ аналогичный. Если ситуация такова, что игрок, который ходил - победил, то он вполне мог победить своим последним ходом, значит, ответ "the ... player won". Если количество крестиков = 5, а ноликов = 4 и никто не победил - то ответ draw, потому что поставить больше некуда. :) Если ничего из вышеперечисленного не случилось и ходил первый игрок, то будет ходить второй, иначе первый. Не решение, а набор условий. =)

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it