PDF《Toy Train玩具火》

International Olympiad in Informatics

2017 July

28 C August 4,

2017 Tehran, Iran Day

1 Tasks train Chinese (CHN) Toy Train玩具火 Arezou和她的兄弟Borzou是 胞胎.

他 收到的生日 物是一套好玩的玩具火 .他 用它建了一 有 站和 段向道的 路系 . 些 站的 是到.每段 道都始于某一 站, 然后 于同一 站或其他 站.每 站至少 有一段 道以它 起.其中有些 站是充 站. 何 ,如果火 抵某充站,它都 被充到 . 火 有足 的力地段道,但是如果不再充 的 ,在即 入第 段道它就 因 已用光而停 . 每 站都有一 道 ,可以扳向任一以 站起的道.火某站出,向的 正是 站的 所扳向的 道. 胞胎打算用他 的火 玩游.他 已 分完了所有的 站:每 站要么 Arezou,要么 Borzou.游 里面只有一列火 .游始,列火 停在 站 ,并且充 了.游,站的有者把 站的扳向某 以起的道. 后他 火 ,火 也就 始沿 道行 . 何 ,在火 首次 入某一 站,站的 有者都要扳定 站.一旦扳定,它就 保持 不 直到游 束.因此,火 如果 到了某 曾的站,就沿与之前相同的 道出站. 由于 站 量是有限的,火 的行 最都落入某 路. 路是指一系列不同的 站 ,其中火 在离 站 ()后 上向站的道, 在离 站后上向站的道.一 路可能只包括一 站(此),即火 站 出后又 上了 向的道. 如果火 能行跑完,Arezou就了.否火最后 把 用光而停 , Borzou就了. 句 ,如果在 站 中至少有一 充站,且使得火 能不地充 而沿 路跑 完,Arezou .否 ,它就 最把用光(有可能是在沿 路跑好几圈 后),Borzou . 在 你一 的 路系 .Arezou和Borzou 玩游.其中在第 游中( ),火 最初停在 站上.你的任 是, 每一 游 ,判 是否 Borzou怎么 玩,Arezou都必胜. 你需要 下面的函 : Train (1 of 3) ?int[] who_wins(int[] a, int[] r, int[] u, int[] v)? : 度的.如果Arezou 有站,;

否 Borzou 有站,且 . : 度的.如果 站 是充 站, .否.和: 度的.于所有 ,存在某一 向道,其起 , . 函 需要返回一 度的.于每 ,如果在火 最初停在 站的游中,不管Borzou怎么玩,Arezou都能 , 的值 1.否 的值 0. 例子 ?who_wins([0, 1], [1, 0], [0, 0, 1, 1], [0, 1, 0, 1])? 里有 站.Borzou 有充 站.Arezou 有站,但是它不是充 站. 里有4段道和,其中 表示一 以站起、站的向道. 考火最初停在 站 的游 .如果Borzou 站的扳向 道 ,那么火 就沿形道完(注意, 站 是一 充站).在 种情 下,Arezou .否 ,如 果Borzou把站的扳向 道,Arezou可以把 站的扳向 道.的,火 在 站之 不停.Arezou 是 ,因 站 是充 站,火跑完.因此, Borzou怎么玩,Arezou都.根据 似的 ,在火 最初停在 站 的游 中, Borzou怎么玩,Arezou也都 .因此,函 返回 . 据范 和限制 . . 至少 有一 充站. 每 站至少 有一段 道以它 起.可能 有某 道的起 和 是相同的(即). 所有 道 不同.也就是 ,不存在 的下和(),使得 且.于所有 ,都有 . 子任 Train (2 of 3) 1. (5分) 于所有 ,都有 或者 . 2. (10分) . 3. (11分) Arezou 有所有 站. 4. (11分) Borzou 有所有 站. 5. (12分) 充 站的 量1. 6. (51分) 任何限制. 分程序 例 分程序 例 按照下述格式 取入据: 第行: 第行: 第行: 第行( 于所有 ): 分程序 例 按照下述格式打印出who_wins的返回 果: 第行: Train (3 of 3)