Codeforces Round 421 (Div. 1) |
---|
Закончено |
Свободными вечерами Мистеру Б иногда нечем заняться, потому он ищет различные игры в интернете. И вот в один день он нашел интересную игру, в которой предлагалось сыграть против инопланетян.
Все символы в данной игре — строчные буквы английского алфавита. В данной игре участвуют два игрока: Мистер Б и его соперник.
Первоначально игрокам задана строка s из a первых символов английского алфавита в алфавитном порядке (при a = 5, например, строка s выглядит следующим образом: «abcde»).
Далее каждый игрок по очереди дописывает в конец строки s по несколько букв. Первым ходом ходит Мистер Б.
Мистер Б может добавить в конец строки ровно b произвольных букв. Его противник — ровно a букв.
Мистер Б быстро догадался, что его противник — никакой не инопланетянин, а компьютер, действующий по простой программе. Компьютер на очередном своем шаге рассматривает суффикс из последних a символов строки s и для своего хода выбирает строку t длины a такую, что все символы в t попарно различны, никакой из символов строки не встречается в рассматриваемом суффиксе, и из всех возможных вариантов t — лексикографически минимальный (при a = 4 и суффиксе «bfdd» компьютер выберет строку t, равную «aceg»). Далее выбранную строку t компьютер просто добавляет в конец строки s.
Мистеру Б уже надоело играть с компьютером, а потому его заинтересовал вопрос: какое минимальное количество различных символов могло быть в строке s на отрезке с символа номер l по символ номер r, включительно. Символы строки s нумеруется слева направо, начиная с 1.
В первой и единственной строке задано четыре натуральных числа через пробел: a, b, l и r (1 ≤ a, b ≤ 12, 1 ≤ l ≤ r ≤ 109) — количество букв, которые добавляют каждый из игроков, и границы интересующего Мистера Б отрезка, соответственно.
Выведите единственное число — минимально возможное количество различных символов в отрезке с символа номер l по символ номер r в строке s.
1 1 1 8
2
4 2 2 6
3
3 7 4 6
1
В первом примере одной из оптимальных стратегий будет такая, при которой s = "abababab...", поэтому ответ равен 2.
Во втором примере может быть получена строка s = "abcdbcaefg...", нужный отрезок имеет вид "bcdbc", поэтому ответ равен 3.
В третьем примере может быть получена строка s = "abczzzacad...", нужный отрезок имеет вид "zzz", поэтому ответ равен 1.
Название |
---|