Задача №115134. Игра с переворотом
Алиса и Боб играют в игру. У них есть две строки \(S\) и \(T\) одинаковой длины \(n\), состоящие из маленьких латинских букв. Игроки ходят по очереди, первой ходит Алиса.
В свой ход Алиса выбирает число \(i\) от \(1\) до \(n\), одну из строк \(S\) или \(T\), а также любую маленькую латинскую букву \(c\), и заменяет \(i\)-й символ в выбранной строке на символ \(c\).
Боб же в свой ход выбирает одну из строк, \(S\) или \(T\), и переворачивает её, то есть делает замену \(S\) на \(\operatorname{rev}(S)\) или же \(T\) на \(\operatorname{rev}(T)\), где \(\operatorname{rev}(S)\) означаёт перевёрнутую строку \(S\) (т.е \(\operatorname{rev}(S) = S_n S_{n-1} \ldots S_1\)).
Игра продолжается, пока строки \(S\) и \(T\) не равны. Как только строки становятся равными, игра моментально заканчивается .
Определим длительность игры, как суммарное количество ходов сделанное обоими игроками в процессе игры. Например, если всего Алиса сделала \(2\) хода, а Боб — \(1\) ход, то длительность такой игры равна \(3\).
Цель Алисы — минимизировать длительность игры, а цель Боба — максимизировать длительность игры.
Чему будет равна длительность игры, при оптимальной игре обоих игроков? Можно показать, что игра завершится за конечное число ходов.
Первая строка входных данных содержит единственное целое число \(n\) (\(1 \le n \le 100\,000\)) — длину строк \(S\) и \(T\).
Вторая строка входных данных содержит строку \(S\) длины \(n\), состоящую из маленьких латинских букв.
Третья строка входных данных содержит строку \(T\) длины \(n\), состоящую из маленьких латинских букв.
Выведите единственное число — длительность описанной игры при оптимальной игре обоих игроков.
В первом примере Алиса в свой ход может заменить третий символ строки \(S\) на \(\tt{x}\). После чего обе строки станут равны \(\tt{abxde}\) и игра завершится после одного хода. Так как цель Алисы минимизировать длительность игры, этот ход будет одним из оптимальных первых ходов для неё, и итоговый ответ равен \(1\).
Во втором примере Алиса в свой ход может заменить пятый символ строки \(T\) на \(\tt{h}\). После этого хода \(S = \tt{hello}, T = \tt{olleh}\). Далее ходит Боб. В свой ход он обязан перевернуть одну из строк. Если Боб выберет строку \(S\), то после его хода обе строки будут равны \(\tt{olleh}\), а если он выберет строку \(T\), то после его хода обе строки будут равны \(\tt{hello}\). Таким образом, после представленного первого хода Алисы игра гарантированно завершится через \(2\) хода. Несложно показать, что стратегии гарантирующей завершение игры менее чем за \(2\) хода у Алисы не существует. Итого ответ равен \(2\).
В третьем примере Алиса в свой первый ход может заменить второй символ строки \(S\) на \(\tt{c}\). После этого хода \(S = \tt{ac}, T = \tt{cd}\). Далее ходит Боб. Если Боб перевернёт строку \(S\), то после его хода \(S = \tt{ca}, T = \tt{cd}\). Тогда несложно видеть, что в этом случае Алиса может гарантированно закончить игру на \(3\)-м ходу, заменив второй символ строки \(T\) на \(\tt{a}\), после чего обе строки станут равны \(\tt{ca}\). Если же Боб перевернёт строку \(T\), то после его хода \(S = \tt{ac}, T = \tt{dc}\). В этом случае Алиса также может гарантированно закончить игру на \(3\)-м ходу, заменив первый символ строки \(S\) на \(\tt{d}\), после чего обе строки станут равны \(\tt{dc}\). Таким образом Алиса может гарантированно закончить игру за \(3\) хода вне зависимости от ходов Боба. Можно показать, что меньше чем за \(3\) хода, при оптимальной игре Боба, игра завершиться не может.
В пятом примере строки \(S\) и \(T\) равны, а значит игра завершится не начавшись, за \(0\) ходов.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n \le 2\), наберут не менее \(10\) баллов.
Решения, корректно работающие при \(n \le 7\), наберут не менее \(40\) баллов.
Решения, корректно работающие при \(n \le 2000\), наберут не менее \(70\) баллов. Дополнительно, решения, корректно работающие, когда строка \(S\) состоит только из символов \(a\), наберут не менее \(10\) баллов.
5 abcde abxde
1
5 hello olleo
2
2 ab cd
3
7 aaaaaaa abbbbba
9
1 q q
0