Олимпиадный тренинг

Задача . Cow Run


Задача

Темы: дп

Фермер Джон и Беси придумали новую игру для коров. Коровы бегут по круглой дорожке длиной M (2 <= M <= 1 000 000 000), начиная с с одной и той же позиции. Игра проходит в N (1<=N<14) раундов с использованием колоды из 8N карт, на каждой из которых написано число Xi (0 <= Xi < M).
На каждом раунде ФД перемещает верхние 8 карт в отдельную кучку и выбирает или верхние 4 или нижние 4 для Беси. Затем Беси из них выбирает или верхние 2 или нижние 2 карты. После этого ФД называет число X_top, которое написано на верхней карте и коровы бегут расстояние R * X_top, где R - это общее расстояние, которое коровы пробежали до сих пор, затем Беси называет число X_bottom, которое было написано на нижней карте и коровы бегут расстояние X_bottom.
ФД беспокоиться, чтобы коровы не сильно устали и могли вернуться домой. Если коровы убегут больше чем на расстояние K (0<=K<=floor(M/2)) от стартовой позиции, то они не смогут вернуться домой.
Гарантируется, что если ФД играет корректно, он всегда может обеспечить чтобы коровы вернулись домой, вне зависимости от ходов, которые делает Беси. Для каждого раунда Ваша задача - определить, какую половину карт должен выбирать ФД, чтобы вне зависимости от ходов Беси, коровы всегда могли вернуться домой. Беси делает ход, описанный на вводе, а Вы должны продолжить в следующий раунд. Заметим, что несмотря на то, что ходы Беси заданы на входе, Вы должны определить ходы для ФД, которые будут работать вне зависимости от выбора Беси и эти ходы были эффективны, как если бы ФД не знал ходы Беси.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: три разделенных пробелами целых числа N, M, K
* Строка 2: N символов. Если i-ый символ есть 'T', значит Беси выберет верхние две карты в этом раунде, иначе если i-ый символ есть 'B', это значит что Беси выберет две нижние карты на этом раунде.
* Строки 3..2+N: каждая строка содержит 8 целых чисел, представляющих 8 карт, которые будут использованы в этом раунде, сверху вниз.
Формат выходных данных
* Строка 1: Строка из N символов, где i-ый символ есть 'T' если ФД должен выбрать верхние 4 карты и 'B', если ФД должен выбрать нижние 4 карты в i-ом раунде. Если существует несколько способов, чтобы коровы вернулись домой, выберите лексикографически наименьший (строка, ему соответствующая должна быть наименьшей в алфавитном порядке).
Примечание
Коровы должны закончить точно в том месте, где начали, чтобы они могли вернуться домой. Заметим, что ФД не принимает во внимание ходы Беси, иначе он мог выбрать нижнюю половину оба раза.
Примеры
№Входные данныеВыходные данные
1 
2 2 0
TT
1 0 0 0 0 0 0 1
0 1 1 1 0 0 1 0
 
TB
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет