B. Train

Codeforces
IDCF74B
Time2000ms
Memory256MB
Difficulty
dpgamesgreedy
English · Original
Chinese · Translation
Formal · Original
A stowaway and a controller play the following game. The train is represented by _n_ wagons which are numbered with positive integers from 1 to _n_ from the head to the tail. The stowaway and the controller are initially in some two different wagons. Every minute the train can be in one of two conditions — moving or idle. Every minute the players move. The controller's move is as follows. The controller has the movement direction — to the train's head or to its tail. During a move the controller moves to the neighbouring wagon correspondingly to its movement direction. If at the end of his move the controller enters the 1\-st or the _n_\-th wagon, that he changes the direction of his movement into the other one. In other words, the controller cyclically goes from the train's head to its tail and back again during all the time of a game, shifting during each move by one wagon. Note, that the controller always have exactly one possible move. The stowaway's move depends from the state of the train. If the train is moving, then the stowaway can shift to one of neighbouring wagons or he can stay where he is without moving. If the train is at a station and is idle, then the stowaway leaves the train (i.e. he is now not present in any train wagon) and then, if it is not the terminal train station, he enters the train again into any of _n_ wagons (not necessarily into the one he's just left and not necessarily into the neighbouring one). If the train is idle for several minutes then each such minute the stowaway leaves the train and enters it back. Let's determine the order of the players' moves. If at the given minute the train is moving, then first the stowaway moves and then the controller does. If at this minute the train is idle, then first the stowaway leaves the train, then the controller moves and then the stowaway enters the train. If at some point in time the stowaway and the controller happen to be in one wagon, then the controller wins: he makes the stowaway pay fine. If after a while the stowaway reaches the terminal train station, then the stowaway wins: he simply leaves the station during his move and never returns there again. At any moment of time the players know each other's positions. The players play in the optimal way. Specifically, if the controller wins, then the stowaway plays so as to lose as late as possible. As all the possible moves for the controller are determined uniquely, then he is considered to play optimally always. Determine the winner. ## Input The first line contains three integers _n_, _m_ and _k_. They represent the number of wagons in the train, the stowaway's and the controller's initial positions correspondingly (2 ≤ _n_ ≤ 50, 1 ≤ _m_, _k_ ≤ _n_, _m_ ≠ _k_). The second line contains the direction in which a controller moves. "to head" means that the controller moves to the train's head and "to tail" means that the controller moves to its tail. It is guaranteed that in the direction in which the controller is moving, there is at least one wagon. Wagon 1 is the head, and wagon _n_ is the tail. The third line has the length from 1 to 200 and consists of symbols "0" and "1". The _i_\-th symbol contains information about the train's state at the _i_\-th minute of time. "0" means that in this very minute the train moves and "1" means that the train in this very minute stands idle. The last symbol of the third line is always "1" — that's the terminal train station. ## Output If the stowaway wins, print "Stowaway" without quotes. Otherwise, print "Controller" again without quotes, then, separated by a space, print the number of a minute, at which the stowaway will be caught. [samples]
一名偷渡者和一名管理员玩以下游戏。 列车由 #cf_span[n] 节车厢组成,从车头到车尾依次编号为 #cf_span[1] 到 #cf_span[n]。偷渡者和管理员初始时位于两节不同的车厢中。每分钟,列车处于两种状态之一:行驶或静止。每分钟双方都会移动。 管理员的移动规则如下:管理员有一个移动方向——朝车头或朝车尾。在移动时,管理员根据其方向移动到相邻的一节车厢。如果在移动结束时管理员进入第 #cf_span[1] 节或第 #cf_span[n] 节车厢,则他会将移动方向反转为相反方向。换句话说,在整个游戏过程中,管理员会周期性地从车头移动到车尾再返回,每分钟移动一节车厢。注意,管理员在任何时候都恰好有一种可能的移动方式。 偷渡者的移动取决于列车的状态。如果列车正在行驶,则偷渡者可以移动到相邻的一节车厢,或者原地不动。如果列车停靠在车站且处于静止状态,则偷渡者离开列车(即不再位于任何一节车厢中),然后,如果不是终点站,他会重新进入列车的任意一节 #cf_span[n] 节车厢中(不一定回到刚离开的车厢,也不一定进入相邻车厢)。如果列车连续多分钟处于静止状态,则每一分钟偷渡者都会离开并重新进入列车。 确定双方的移动顺序:如果当前分钟列车正在行驶,则先由偷渡者移动,然后管理员移动;如果当前分钟列车静止,则先由偷渡者离开列车,然后管理员移动,最后偷渡者重新进入列车。 如果在某一时刻偷渡者与管理员位于同一节车厢,则管理员获胜:他迫使偷渡者缴纳罚款。如果偷渡者最终到达终点站,则偷渡者获胜:他在移动时离开车站,且永不返回。 在任何时刻,双方都知道对方的位置。双方均采取最优策略。具体而言,如果管理员会获胜,则偷渡者会尽量延迟失败的时间;而由于管理员的所有可能移动都是唯一确定的,因此他始终被视为采取最优策略。请确定获胜者。 第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k],分别表示列车的车厢数、偷渡者和管理员的初始位置(#cf_span[2 ≤ n ≤ 50],#cf_span[1 ≤ m, k ≤ n],#cf_span[m ≠ k])。 第二行包含管理员的移动方向。"to head" 表示管理员朝车头方向移动,"to tail" 表示管理员朝车尾方向移动。保证在管理员当前移动方向上至少存在一节车厢。第 #cf_span[1] 节车厢为车头,第 #cf_span[n] 节车厢为车尾。 第三行是一个长度为 #cf_span[1] 到 #cf_span[200] 的字符串,由字符 "0" 和 "1" 组成。第 #cf_span[i] 个字符表示第 #cf_span[i] 分钟时列车的状态:"0" 表示列车正在行驶,"1" 表示列车静止。第三行的最后一个字符始终为 "1",表示终点站。 如果偷渡者获胜,输出 "Stowaway"(不含引号);否则,输出 "Controller"(不含引号),然后空一格,输出偷渡者被抓住的分钟数。 ## Input 第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k],分别表示列车的车厢数、偷渡者和管理员的初始位置(#cf_span[2 ≤ n ≤ 50],#cf_span[1 ≤ m, k ≤ n],#cf_span[m ≠ k])。第二行包含管理员的移动方向。"to head" 表示管理员朝车头方向移动,"to tail" 表示管理员朝车尾方向移动。保证在管理员当前移动方向上至少存在一节车厢。第 #cf_span[1] 节车厢为车头,第 #cf_span[n] 节车厢为车尾。第三行是一个长度为 #cf_span[1] 到 #cf_span[200] 的字符串,由字符 "0" 和 "1" 组成。第 #cf_span[i] 个字符表示第 #cf_span[i] 分钟时列车的状态:"0" 表示列车正在行驶,"1" 表示列车静止。第三行的最后一个字符始终为 "1",表示终点站。 ## Output 如果偷渡者获胜,输出 "Stowaway"(不含引号);否则,输出 "Controller"(不含引号),然后空一格,输出偷渡者被抓住的分钟数。 [samples]
**Definitions** Let $ n \in \mathbb{Z} $ be the number of wagons, with positions $ \{1, 2, \dots, n\} $, where $ 1 $ is the head and $ n $ is the tail. Let $ m \in \{1, \dots, n\} $ be the initial position of the stowaway. Let $ k \in \{1, \dots, n\} $ be the initial position of the controller, with $ m \ne k $. Let $ d \in \{\text{head}, \text{tail}\} $ be the initial direction of the controller. Let $ T = t_1 t_2 \dots t_L $ be a binary string of length $ L \in [1, 200] $, where $ t_i \in \{0, 1\} $, representing the train’s state at minute $ i $: - $ t_i = 0 $: train is **moving**; - $ t_i = 1 $: train is **idle** (and $ t_L = 1 $, the terminal station). Let $ s_i \in \{1, \dots, n\} \cup \{\text{out}\} $ be the stowaway’s position at the start of minute $ i $ (before move). Let $ c_i \in \{1, \dots, n\} $ be the controller’s position at the start of minute $ i $. Let $ d_i \in \{\text{head}, \text{tail}\} $ be the controller’s direction at the start of minute $ i $. **State Transition Rules** At minute $ i $: 1. **If $ t_i = 0 $ (moving):** - Stowaway moves: $ s_i \to s_{i+1} \in \{s_i - 1, s_i, s_i + 1\} \cap \{1, \dots, n\} $. - Controller moves: - If $ d_i = \text{head} $, then $ c_{i+1} = \max(c_i - 1, 1) $; if $ c_{i+1} = 1 $, then $ d_{i+1} = \text{tail} $. - If $ d_i = \text{tail} $, then $ c_{i+1} = \min(c_i + 1, n) $; if $ c_{i+1} = n $, then $ d_{i+1} = \text{head} $. - If $ s_{i+1} = c_{i+1} $, controller wins. 2. **If $ t_i = 1 $ (idle):** - Stowaway leaves train: $ s_i \to \text{out} $. - Controller moves (same rule as above): - $ c_{i+1} = \begin{cases} \max(c_i - 1, 1) & \text{if } d_i = \text{head} \\ \min(c_i + 1, n) & \text{if } d_i = \text{tail} \end{cases} $, - Update $ d_{i+1} $ if $ c_{i+1} \in \{1, n\} $. - Stowaway re-enters: $ s_{i+1} \in \{1, \dots, n\} $ (any wagon). - If $ s_{i+1} = c_{i+1} $, controller wins. **Win Conditions** - **Controller wins** at the first minute $ i $ such that $ s_i = c_i $ after both players have moved. - **Stowaway wins** if $ i = L $ (last minute, terminal station) and the stowaway leaves the train and does not re-enter (per problem: “never returns there again”). **Objective** Determine the winner under optimal play: - Controller plays deterministically (only one move possible). - Stowaway, if not caught, plays to **maximize the time until capture** (or win). - If stowaway can reach minute $ L $ without being caught, output “Stowaway”. - Else, output “Controller” and the minute $ i \in \{1, \dots, L\} $ when $ s_i = c_i $. **Formal Objective** Compute the minimal $ i \in \{1, \dots, L\} $ such that, under optimal stowaway strategy, $ s_i = c_i $. If no such $ i < L $ exists, then stowaway wins.
Samples
Input #1
5 3 2
to head
0001001
Output #1
Stowaway
Input #2
3 2 1
to tail
0001
Output #2
Controller 2
API Response (JSON)
{
  "problem": {
    "name": "B. Train",
    "description": {
      "content": "A stowaway and a controller play the following game. The train is represented by _n_ wagons which are numbered with positive integers from 1 to _n_ from the head to the tail. The stowaway and the con",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF74B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A stowaway and a controller play the following game.\n\nThe train is represented by _n_ wagons which are numbered with positive integers from 1 to _n_ from the head to the tail. The stowaway and the con...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一名偷渡者和一名管理员玩以下游戏。\n\n列车由 #cf_span[n] 节车厢组成,从车头到车尾依次编号为 #cf_span[1] 到 #cf_span[n]。偷渡者和管理员初始时位于两节不同的车厢中。每分钟,列车处于两种状态之一:行驶或静止。每分钟双方都会移动。\n\n管理员的移动规则如下:管理员有一个移动方向——朝车头或朝车尾。在移动时,管理员根据其方向移动到相邻的一节车厢。如果在移动结束时管理员进...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of wagons, with positions $ \\{1, 2, \\dots, n\\} $, where $ 1 $ is the head and $ n $ is the tail.  \nLet $ m \\in \\{1, \\dots, n\\} $ be the initial...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments