#1026. 「USACO 2012.1 Gold」Cow Run

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
cowrun.in ≫ cowrun.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

农夫 John 和 Bessie 为奶牛们设计了一种新的运动游戏。奶牛们从同一位置开始,在一个长度为 的圆形跑道上奔跑,其中 。游戏进行 轮(),使用一副 张的牌,每张牌上写有一个数字 ,其中

每一轮,FJ 将顶部的 8 张牌移到一个单独的牌堆中,并选择顶部 4 张或底部 4 张牌供 Bessie 使用。然后 Bessie 从 FJ 选择的 4 张牌中选择顶部 2 张或底部 2 张牌。之后,FJ 报出顶部牌上的数字 ,奶牛们跑 的距离,其中 是奶牛们到目前为止跑过的总距离。接着 Bessie 报出底部牌上的数字 ,奶牛们再跑 的距离。

FJ 担心在运动后,奶牛们会太累而无法回到跑道的起点,如果它们离起点的距离超过 ,它们就无法回家,其中

可以保证,如果 FJ 正确地进行游戏,他总能确保奶牛们能够回家,无论 Bessie 做出什么选择!对于每一轮,你的任务是确定 FJ 应该选择哪一半的牌,以便无论 Bessie 从那时起做出什么选择,FJ 总能让奶牛们回家。Bessie 将根据输入提供的选择进行移动,然后你可以继续进行下一轮。注意,尽管 Bessie 的选择在输入中提供给你,但你需要为 FJ 指定无论 Bessie 选择什么都能奏效的策略(因此实际上 FJ 并不知道 Bessie 在她的回合中会做什么)。

输入格式 cowrun.in

* 第 1 行:三个用空格分隔的整数

* 第 2 行:一个长度为 的字符串。如果第 个字符是 'T',表示 Bessie 在第 轮中选择顶部 2 张牌。否则,第 个字符将是 'B',表示 Bessie 选择底部 2 张牌。

* 第 3 行到第 行:每行包含 8 个整数,表示该轮从顶部到底部使用的 8 张牌。

输出格式 cowrun.out

* 第 1 行:一个长度为 的字符串,其中第 个字符是 'T',如果 FJ 应该在第 轮中选择顶部 4 张牌;如果 FJ 应该选择底部 4 张牌,则为 'B'。如果有多种方法可以让奶牛们回家,选择字典序最小的(即字母顺序最小的字符串)。

样例

输入 #1

2 2 0 
TT 
1 0 0 0 0 0 0 1 
0 1 1 1 0 0 1 0

输出 #1

TB

数据范围与提示

奶牛们必须准确地回到起点才能回家。注意,FJ 事先不知道 Bessie 会做出什么选择。如果 FJ 知道,他每次都可以选择底部一半。