Universal Paperclips — инкрементальная игра, целью которой является изготовление скрепок. В вашем распоряжении есть оборудование, производящее скрепки по нажатию кнопки.
В упрощенной версии игры для этой задачи будем считать, что игроку доступны два вида действий:
Изначально у игрока ноль скрепок, а каждое нажатие на кнопку добавляет одну скрепку. На каждое улучшение тратится $$$x$$$ скрепок. Во всех входных данных гарантируется, что перед каждым улучшением в наличии есть хотя бы $$$x$$$ скрепок.
Бенни решил написать бота для этой игры. Он закодировал в бота последовательность из $$$n$$$ действий $$$S$$$, которую бот выполняет по циклу. Каждую секунду бот совершает очередное действие: на 1-й секунде бот применяет $$$S_1$$$, на второй — $$$S_2$$$, ..., на $$$n$$$-й — $$$S_n$$$, на $$$n+1$$$-й — снова $$$S_1$$$, и далее по циклу.
Сколько скрепок будет у Бенни после $$$t$$$ секунд работы его бота?
В первой строке содержатся три числа $$$n$$$, $$$t$$$ и $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le t \le 10^9$$$; $$$0 \le x \lt n$$$). Во второй строке содержится строка $$$S$$$ длины $$$n$$$ из символов «C» и «U».
Выведите одно число — число скрепок через $$$t$$$ секунд.
| Подзадача | Баллы | Ограничения |
| 1 | 33 | $$$t \le 10^5$$$ |
| 2 | 67 | Без дополнительных ограничений |
10 15 2 CCCCCUUCCU
25
3 10 0 UUU
0
9 150 1 CCUCCCCUC
2023
Рассмотрим первый пример. Первые пять операций приносят по одной скрепке каждая. Следующие две операции используют по две скрепки, после чего остается одна скрепка, однако, следующие два нажатия производят по три скрепки. Далее, улучшение снова отбирает две. Последние пять нажатий приносят по 4 скрепки каждое.
Итоговое число скрепок равно $$$1 + 1 + 1 + 1 + 1 - 2 - 2 + 3 + 3 - 2 + 4 + 4 + 4 + 4 + 4 = 25$$$.
| Innopolis Open 2022-2023. Финал |
|---|
| Закончено |
