AT_hokudai_hitachi2019_2_a Problem C
题目描述
你将参与一个模拟配送任务，任务中需要通过移动车辆在一个图上执行订单。这个图是一个简单无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合（包括商店和顾客的所有位置），\( E \) 是边集合（代表连接各顶点的道路）。每个顶点 \( u \in V \) 由 1 到 \( |V| \) 编号，顶点 1 是商店，其他顶点是顾客。
### 时间与空间限制
- **时间**：在每一个时间步 \( t \)，满足 \( 0 \leq t < T_{\max} \)，你需要决定从时刻 \( t \) 到 \( t+1 \) 的行为。
- **空间**：图 \( G = (V, E) \) 是一个简单无向图，所有的车辆移动和订单生成都在图中进行。
- **商店和顾客位置**：顶点 1 是商店，其余顶点则是顾客地址。
- **道路**：每条边 \( \{u, v\} \) 将顶点 \( u \) 和 \( v \) 直接连通，边的长度为 \( d_{u, v} \geq 1 \)。
### 图的生成
地图基于下面的算法随机生成（本次比赛的图生成算法与之前不同）:
- 图 \( G \) 是在一个 \( 25 \times 25 \) 的二维平面上生成的。
- 南北和东西方向分别有一条高速路，高速路上邻近顶点间的距离为 1。
- 南北方向有铁路穿过图。
- 高速路和铁路将图划分成 6 个区域。
- 每个顶点默认订单频率为 1，但某些区域内的顶点频率为 2。高速路上的顶点以及商店所在的顶点不会产生订单（订单频率为 0）。
- 在高速路上行驶速度是普通路径的 4 倍（相当于距离缩短为四分之一）。
### 车辆位置与移动规则
- **车辆位置**：车辆的位置可以是某个顶点 \( u \) 或者位于边 \( \{u, v\} \) 上，即从 \( u \) 向 \( v \) 移动了距离 \( x \) \( (0 < x < d_{u,v}) \)。
- **车辆行动**：你可以选择以下两种行为之一：
- `stay`：停留在当前位置；
- `move w`：移动到顶点 \( w \) 的方向，距离为 1。
选择 `move w` 时，必须满足：
- \( w \) 是 \( V \) 内的一个顶点；
- 车在顶点 \( u \) 上时，边 \( \{u, w\} \) 必须在 \( E \) 中；
- 车在边 \( \{u, v\} \) 上时，必须是 \( w = u \) 或 \( w = v \)。
### 订单及相关说明
- **订单信息**：包括订单ID、配送目标顶点 \( v \)、订单生成时间 \( t \)。
- **订单生成**：新的订单会在 \( 0 \leq t \leq T_{\mathrm{last}} = 0.95 \times T_{\max} \) 的时间内以概率 \( p_{\mathrm{order}}(t) \) 生成。生成时目标顶点成为 \( i \) 的概率为 \(\frac{f_i}{\sum_{k} f_k}\)，其中 \( f_i \) 为顶点 \( i \) 的订单频率。
### 事件说明
- **交通拥堵**：可能会在高速路的不同方向发生。在拥堵的方向行驶时车辆只能以 10% 的概率前进。
- **车辆故障**：临时通知 `WARNING t` 会警示可能的故障发生，如果在 \( t \) 步内回到商店，故障可恢复；否则会在下一步时通知 `BROKEN`，之后 300 步内车辆无法移动。
- **订单取消**：超过 \( T_{\text{wait}} = 2000 \) 步未完成配送的订单可能被取消。
- **红绿灯等候**：可能会在非高速路顶点进入高速路时遇到红绿灯，等候是与时间同步确定的。
### 评分标准
每个测试用例的得分累加起来即为你的程序得分。比赛期间共有 30 个测试用例，赛后会有 100 个新测试用例进行最终评分。得分计算公式如下：
\[ \text{Score} = \sum_{i \in D} (T_{\max})^2 - (\text{waitingTime}_i)^2 \]
其中：
- \( D \) 是在 \( t = T_{\max} \) 前完成配送的订单集合。
- \( \text{waitingTime}_i = \text{deliveredTime}_i - \text{orderedTime}_i \) 表示第 \( i \) 个订单的等待时间。
### 输入格式
初始输入：
- 第一行: \( |V| \)（顶点数量）、\( |E| \)（边数量）。
- 接下来 \( |E| \) 行：每行表示一条边信息：\( u_i \ v_i \ d_{u_i, v_i} \ e_{u_i, v_i} \ e_{v_i, u_i} \)。
- 接下来一行: 各顶点订单频率 \( f_1, f_2, \ldots, f_{|V|} \)。
- 接下来 4 行：每行是某方向高速路的交通拥堵开始预估时间 \( t_{d,1}, \cdots, t_{d,4} \)。
- 一行: 信号灯周期 \( P_{\text{light}} \)。
- 一行: 车辆故障警告持续时间 \( T_{\text{warning}} \)。
- 最后一行: 最大时间步数 \( T_{\max} \)。
每步输入：
- 第一行: 车辆状态 `CAR_STATUS`。
- 第二行: 各方向拥堵状态 \( \mathrm{jam}_{1}, \mathrm{jam}_{2}, \mathrm{jam}_{3}, \mathrm{jam}_{4} \)。
- 第三行: 新取消订单数 \( N_{\text{cancel}} \)。
- 接下来 \( N_{\text{cancel}} \) 行：每行是一个被取消的订单 ID。
- 第四行: 新订单数 \( N_{\text{new}} \)。
- 接下来 \( N_{\text{new}} \) 行：每行是一个新订单，格式为 \( \mathrm{new\_id}_i \ \mathrm{dst}_i \)。
- 第五行: 新装载商品数 \( N_{\text{put}} \)。
- 接下来 \( N_{\text{put}} \) 行：每行是一个新装载商品对应的订单 ID。
### 输出格式
每步输出：
- 一行：行动 `command`。
- 若选择 `stay`，输出 `-1`。
- 若选择 `move w`，输出目标顶点编号 \( w \)。
### 数据范围与提示
- 初始数据范围：
- \( T_{\text{max}} = 10000 \)
- \( |V| = 625 \)
- \( 1.5 |V| \leq |E| \leq 2|V| \)
- 所有点和边信息为整数，且给定图是连通的。
- 顶点 1 不产生订单（\( f_1 = 0 \)）。
- 每步输入：
- 车辆状态是 `NOT_BROKEN`, `WARNING t`, 或 `BROKEN`。
- 拥堵状态为 0 或 1。
- 行动有效范围：整数 `-1` 和 \( 1 \leq w \leq |V| \)。
- 每步输出：
- 反馈为 `OK`, `NG`, `JAM`, 或 `WAIT t`。
以上优化过的描述让语言更贴近中文习惯，便于理解和跟踪问题要求和输入输出格式。
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无
说明/提示
### 時間・空間について
- **時間**: $ t $ は $ 0\ \leq\ t\ $ \mathrm{verdict} $ $ N_{\text{achieve}} $ $ \mathrm{achieve\_id}_1 $ $ \mathrm{achieve\_id}_2 $ $ \vdots $ $ \mathrm{achieve\_id}_{N_{\text{achieve}}} $
- $ \mathrm{verdict} $ は、時刻 $ t $ における車の行動が実行可能であるかを表す文字列であり、以下の $ 4 $ 種類のいずれかである。
- `OK`: 行動は実行可能であり、車は行動に従って動く(もしくはとどまる)ことを表す。
- `NG`: 行動は実行不可能であり、`NG` が出力された場合、コンテスタントはプログラムを即座に終了させなければならない。即座に終了させた場合は `WA` (不正解) となることが保証されるが、そうでない場合の動作は未定義である。
- `JAM`: 渋滞によって車が進めなかったことを表す。(渋滞方向への移動であっても、車が進めれば `OK` が出力される)
- `WAIT t`: 行動は実行可能であり、車が所望の頂点に移動したことを表す。ただし、赤信号のため次の $ t $ ステップの間、その場にとどまらなくてはならない。その間、コンテスタントコードは `-1` を出力しなければならない。 `-1` を出力しなければ `NG` となる。なお、信号待ちに該当する頂点に移動した場合であっても、青信号であれば `OK` が出力される。
- $ N_{\text{achieve}} $ は、その時刻において配達が完了した注文の数を表す。
- その時点で車が店にいなければ、$ N_{\text{achieve}} $ は $ 0 $ である。
- 続く $ N_{\text{achieve}} $ 行で、配達が完了した注文情報が与えられる。$ i $ 行目の注文情報は、注文 ID が $ \mathrm{achieve\_id}_i $ であることを表す。
また、$ T_{\max} $ 回目の行動に対するジャッジからの入力を受け取ったあと、あなたは **プログラムを即座に終了させなければならない。**
### 入出力制約
- 入力で与えられる数値はすべて整数である
- 出力はすべて整数でなければならない
#### 初期化
- $ T_{\text{max}}\ =\ 10000 $
- $ |V|\ =\ 625 $
- $ 1.5\ |V|\ \leq\ |E|\ \leq\ 2|V| $
- $ 1\ \leq\ u_{i},\ v_{i}\ \leq\ |V| $ $ (1\ \leq\ i\ \leq\ |E|) $
- $ 1\ \leq\ d_{u_i,\ v_i}\ \leq\ \lceil\ 4\sqrt{2|V|}\ \rceil $ $ (1\ \leq\ i\ \leq\ |E|) $
- $ 0\ \leq\ e_{u_i,\ v_i},\ e_{v_i,\ u_i}\ \leq\ 6 $ $ (1\ \leq\ i\ \leq\ |E|) $
- 与えられるグラフは自己ループ・多重辺が存在せず、連結であることが保証される
- $ f_1\ =\ 0 $
- $ f_i\ \in\ \left\{0,\ 1,\ 2\ \right\} $ ($ 2\ \leq\ i\ \leq\ |V| $)
- $ 0\ \leq\ t_{d,1}\ \leq\ t_{d,2}\ \leq\ t_{d,3}\ \leq\ t_{d,4}\ \lt\ T_{\text{max}} $ $ (1\ \leq\ d\ \leq\ 4) $
- $ 50\ \leq\ T_{\text{warning}}\ \leq\ 120 $
- $ 10\ \leq\ P_{\text{light}}\ \leq\ 30 $
#### 繰り返し処理
- $ \mathrm{CAR\_STATUS}\ \in $ $ \{ $ `NOT_BROKEN`, `WARNING t`, `BROKEN`$ \} $
- $ \mathrm{jam}_{1},\ \mathrm{jam}_{2},\ \mathrm{jam}_{3},\ \mathrm{jam}_{4}\ \in\ \{0,1\} $
- $ 0\ \leq\ N_{\text{new}}\ \leq\ 1 $
- $ 1\ \leq\ \mathrm{new\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{new}}) $.
注意: 上で説明されたルールに従って注文が生成されたとき、発生する注文の件数の最大値は $ T_{\text{last}}\ +\ 1 $ となる。ゆえに、$ \mathrm{new\_id}_{i} $ の取りうる値は $ 1 $ から $ T_{\text{last}}\ +\ 1 $ までの整数である。
- ジャッジからの出力全体を通して、注文ID $ \mathrm{new\_{id}}_i $ はそれぞれ相異なる整数である
- $ 2\ \leq\ \mathrm{dst}_i\ \leq\ |V| $ $ (1\ \leq\ i\ \leq\ N_{\text{new}}) $
- $ 0\ \leq\ N_{\text{cancel}}\ \leq\ T_{\text{last}}+1 $
- $ 1\ \leq\ \mathrm{cancel\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{cancel}}) $.
- $ 0\ \leq\ N_{\text{put}}\ \leq\ T_{\text{last}}+1 $
- $ 1\ \leq\ \mathrm{put\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{put}}) $.
- 時刻 $ t $ におけるあなたの行動を表す整数は $ -1 $ または $ 1\ \leq\ w\ \leq\ |V| $ を満たす整数 $ w $ でなければならない
- $ \mathrm{verdict}\ \in\ \{ $`OK`, `NG`,`JAM`, `WAIT t`$ \} $
- $ 0\ \leq\ N_{\text{achieve}}\ \leq\ T_{\text{last}}+1 $
- $ 1\ \leq\ \mathrm{achieve\_id}_{i}\ \leq\ T_{\text{last}}+1 $ $ (1\ \leq\ i\ \leq\ N_{\text{achieve}}) $.
- - - - - -
### 入出力例
以下では入出力例を用いて、コンテスタント側とジャッジ側の挙動を説明する。
- **グラフ** : 以下では $ 16 $ 頂点、 $ 18 $ つの辺をもつグラフを例として挙げる。
- **スピードウェイ**: 下図の黒い頂点で表す。以下のように $ 4 $ つの方向がある。
- $ d=1 $ : $ 3\to7\to11\to15 $
- $ d=2 $ : $ 15\to11\to7\to3 $
- $ d=3 $ : $ 9\to10\to11\to12 $
- $ d=4 $ : $ 12\to11\to10\to9 $.
- 時間ステップ $ 0 $ から $ 8 $ : 車は頂点 $ 14 $ を訪問し、注文(ID: $ 1 $) の配達を行う。この間、頂点 $ 16 $ で発生した注文がキャンセルされる。配達経路を赤い矢印で示す。渋滞によりステップ $ 4 $ から $ 5 $ の間、車は動けない。
- 時間ステップ $ 8 $ から $ 14 $ : 車の故障警告 `WARNING 5` が発生し、修理のため車は店(頂点 $ 1 $ )を目指す。しかし、頂点 $ 9 $ で信号待ち( `WAIT 2` )が発生し、ステップ $ 11,\ 12 $ で車は動けない。
- 時間ステップ $ 13 $ で頂点 $ 1,\ 9 $ の間で車が故障し、`BROKEN` の通知を受け取る。
- 時間ステップ $ 14 $ :車の故障中に実行不可能な行動を行ったため、`NG` が出力される。
注意: この例はわかりやすさのために作られたものであり、制約条件は満たさない。
時間 コンテスタント ジャッジ 説明 ```
16 18
5 1 2 0 0
2 3 2 5 6
2 6 4 0 0
3 4 2 6 5
3 7 1 1 2
4 8 4 0 0
1 6 2 0 0
1 9 2 5 6
7 11 1 1 2
9 10 1 3 4
9 13 2 6 5
9 14 2 6 5
10 11 1 3 4
11 12 1 3 4
11 15 1 1 2
12 16 2 6 5
14 15 2 5 6
15 16 2 6 5
0 1 0 1 1 2 0 1 0 0 0 0 1 1 0 1
3 167 311 913
63 617 791 837
325 473 893 915
156 387 627 849
6
5
10000
```
はじめに、ジャッジ側からデータが与えられる
$ 1 $ 行目: グラフは $ |V|\ =\ 16 $ 個の頂点と $ |E|\ =\ 18 $ つの辺から構成される
次の $ 18 $ 行 (行 $ 2 $ - $ 19 $) は、グラフの辺に関する情報を表す。例えば、
$ 2 $ 行目: 頂点 $ 5 $ と頂点 $ 1 $ の間の距離が $ 2 $ で、$ 4 $ 番目の数字 $ 0 $ は、$ 5\to\ 1 $ 方向の道が通常の道であることを示し、最後の $ 0 $ は $ 1\to\ 5 $ 方向の道も通常の道であることを示す
$ 3 $ 行目: 頂点 $ 2 $ と頂点 $ 3 $ の間の距離が $ 2 $ で、$ 4 $ 番目の数字 $ 5 $ は、$ 2\to\ 3 $ の方向に進むと通常の道からスピードウェイに入ることを示し、最後の $ 6 $ は $ 3\to\ 2 $ 方向に進むとスピードウェイから通常の道に戻ることを示す
$ 6 $ 行目: 頂点 $ 3 $ と頂点 $ 7 $ の間の距離が $ 1 $ で、$ 4 $ 番目の数字 $ 1 $ は、$ 3\to\ 7 $ の方向がスピードウェイの方向 $ d=1 $ に対応することを示し、最後の $ 2 $ は $ 7\to\ 3 $ の方向がスピードウェイの方向 $ d=2 $ に対応することを示す
$ 20 $ 行目: 各頂点における注文発生頻度を示す
$ 21 $ 行目: 方向 $ d=1 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す
$ 22 $ 行目: 方向 $ d=2 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す
$ 23 $ 行目: 方向 $ d=3 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す
$ 24 $ 行目: 方向 $ d=4 $ の渋滞開始時刻の目安($ i=1,...,4 $)を示す
$ 25 $ 行目: 信号の周期 $ P_{\text{light}}=6 $ を示す
$ 26 $ 行目: 車の故障警告期間 $ T_{\text{warning}}=5 $ を示す
$ 27 $ 行目: 時間ステップの最大値 $ T_{\max}=10000 $ を示す $ 0\ \rightarrow\ 1 $ ```
NOT_BROKEN
0 0 0 0
0
1
1 14
1
1
```
時刻 $ t=0 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに $ 1 $ つの注文があった
$ 5 $ 行目: 新規注文のIDは $ 1 $ であり、届け先は頂点 $ 14 $ である
$ 6 $ 行目: 車は店に居るので、 $ 1 $ つの注文に対応する荷物を車に積んだ
$ 7 $ 行目: 荷物に対応する注文IDは $ 1 $ である ```
9
```
コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 1\ \rightarrow\ 2 $ ```
NOT_BROKEN
0 0 0 0
0
1
2 16
0
```
時刻 $ t=1 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに $ 1 $ つの注文があった
$ 5 $ 行目: 新規注文のIDは $ 2 $ であり、届け先は頂点 $ 16 $ である
$ 6 $ 行目: 車は店に居ないので、荷物は車に積まれなかった ```
9
```
コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める ```
OK
0
```
車はスピードウェイに入った。このとき信号は青である。したがって、最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 2\ \rightarrow\ 3 $ ```
NOT_BROKEN
0 0 0 0
0
0
0
```
時刻 $ t=2 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
10
```
コンテスタントは車を頂点 $ 10 $ に向けて距離 $ 1 $ だけ進める ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 3\ \rightarrow\ 4 $ ```
NOT_BROKEN
0 0 0 0
0
0
0
```
時刻 $ t=3 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
11
```
コンテスタントは車を頂点 $ 11 $ に向けて距離 $ 1 $ だけ進める ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 4\ \rightarrow\ 5 $ ```
NOT_BROKEN
1 0 0 0
0
0
0
```
時刻 $ t=4 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞がスピードウェイの方向 $ d=1 $ で発生している
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
15
```
コンテスタントは車を頂点 $ 15 $ に向けて距離 $ 1 $ だけ進めようとする ```
JAM
0
```
最初の行は車が渋滞により進めなかったことを示す。そのため、車は頂点 $ 11 $ にとどまる。$ 2 $ 行目は配達が行われなかったことを表す $ 5\ \rightarrow\ 6 $ ```
NOT_BROKEN
1 0 0 0
0
0
0
```
時刻 $ t=5 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞がスピードウェイの方向 $ d=1 $ で発生している
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
15
```
コンテスタントは車を頂点 $ 15 $ に向けて距離 $ 1 $ だけ進めようとする (依然としてこの方向には渋滞が発生している) ```
OK
0
```
最初の行は車が運良く進めたことを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 6\ \rightarrow\ 7 $ ```
NOT_BROKEN
1 0 0 0
0
0
0
```
時刻 $ t=6 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞がスピードウェイの方向 $ d=1 $ で発生している
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
14
```
コンテスタントは車を頂点 $ 14 $ に向けて距離 $ 1 $ だけ進める ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 7\ \rightarrow\ 8 $ ```
NOT_BROKEN
0 0 0 0
1
2
0
0
```
時刻 $ t=7 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は正常な状態である (`NOT_BROKEN`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 1 $ である
$ 4 $ 行目: キャンセルされた注文のIDは $ 2 $ である
$ 5 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 6 $ 行目: 荷物は車に積まれなかった ```
14
```
コンテスタントは車を頂点 $ 14 $ に向けて距離 $ 1 $ だけ進める ```
OK
1
1
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は $ 1 $ つの注文が配達されたことを示す。$ 3 $ 行目は配達された注文のIDが $ 1 $ であることを示す $ 8\ \rightarrow\ 9 $ ```
WARNING 5
0 0 0 0
0
0
0
```
時刻 $ t=8 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は故障警告状態であり、あと $ 5 $ ステップで故障する (`WARNING 5`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
9
```
コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 9\ \rightarrow\ 10 $ ```
WARNING 4
0 0 0 0
0
0
0
```
時刻 $ t=9 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は故障警告状態であり、あと $ 4 $ ステップで故障する (`WARNING 4`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
9
```
コンテスタントは車を頂点 $ 9 $ に向けて距離 $ 1 $ だけ進める ```
WAIT 2
0
```
最初の行は車の行動が実行可能であることを示す。したがって車はスピードウェイ上の頂点 $ 9 $ に到達する。しかし赤信号のため、 $ 2 $ ステップの間、車は現在の頂点にとどまらなければならない。$ 2 $ 行目は配達が行われなかったことを表す $ 10\ \rightarrow\ 11 $ ```
WARNING 3
0 0 0 0
0
0
0
```
時刻 $ t=10 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は故障警告状態であり、あと $ 3 $ ステップで故障する (`WARNING 3`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
-1
```
赤信号のため、コンテスタントは頂点 $ 9 $ に車をとどめなくてはならない (とどめなかった場合、 `NG` となる) ```
WAIT 1
0
```
最初の行は車の行動が実行可能であることを示す。しかし赤信号のため、$ 1 $ ステップの間、車は現在の頂点にとどまらなければならない。$ 2 $ 行目は配達が行われなかったことを表す $ 11\ \rightarrow\ 12 $ ```
WARNING 2
0 0 0 0
0
0
0
```
時刻 $ t=11 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は故障警告状態であり、あと $ 2 $ ステップで故障する (`WARNING 2`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
-1
```
赤信号のため、コンテスタントは頂点 $ 9 $ に車をとどめなくてはならない (とどめなかった場合、 `NG` となる) ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 12\ \rightarrow\ 13 $ ```
WARNING 1
0 0 0 0
0
0
0
```
時刻 $ t=12 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は故障警告状態であり、あと $ 1 $ ステップで故障する (`WARNING 1`)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
1
```
コンテスタントは車を頂点 $ 1 $ に向けて距離 $ 1 $ だけ進める (信号待ちは終了) ```
OK
0
```
最初の行は車の行動が実行可能であることを示す。$ 2 $ 行目は配達が行われなかったことを表す $ 13\ \rightarrow\ 14 $ ```
BROKEN
0 0 0 0
0
0
0
```
時刻 $ t=13 $ で以下の情報が与えられる:
$ 1 $ 行目: 車は故障状態となった。(`BROKEN`) (コンテスタントは行動 `-1` を出力しなければならない)
$ 2 $ 行目: 渋滞は発生していない
$ 3 $ 行目: 新たにキャンセルされた注文の数は $ 0 $ である
$ 4 $ 行目: 新たに発生した注文の数は $ 0 $ である
$ 5 $ 行目: 荷物は車に積まれなかった ```
1
```
コンテスタントは車を頂点 $ 1 $ に向けて距離 $ 1 $ だけ進めようとする ```
NG
```
最初の行は車の行動が実行不可能であることを示す(車が故障中にも関わらず動かそうとしたため)。コンテスタントはプログラムを終了させなければならない。(もしコンテスタントが一つ前のステップで車を店に戻せていたら、車は修理され、車の状態は正常状態 `NOT_BROKEN` となっていた)。$ 2 $ 行目は配達が行われなかったことを表す ### 出力の flush について
この問題では出力を flush する必要がある。例として、主要言語において `-1` と出力して flush する例は以下の通りである。
#### C++
```
std::cout
Java
System.out.println("-1");
Python 3.4
print("-1", flush=True)
```
### サンプルコード C
この問題について、以下のツールキット一式は[ここ](https://img.atcoder.jp/hokudai-hitachi2019-2/2feac369fc0c9ac899efd364b4714c14.zip)からダウンロードできます。
- 入力サンプルジェネレータ
- テスター
また、ビシュアライザも[ここ](https://img.atcoder.jp/hokudai-hitachi2019-2/cb1bbbd4fef5d202b3707dcee0212d37.zip)にご用意しております。