UVa 13046 - Bus Collisions

Source

A Bangladeshi Contest at SUST(20151212)
UVa 13046

問題概要

この街は $30 \times 30$ のマス目の形をしている.
$2$ つのバスの周回ルートが与えられる.
$i$ 番目のバスのルートは $N_i$ 個からなるマスの列で $(X_1^{(i)}, Y_1^{(i)}), (X_2^{(i)}, Y_2^{(i)}), \ldots, (X_{N_i}^{(i)}, Y_{N_i}^{(i)})$ となっている.
ここで,隣り合うマスは上下左右のどちらかに真っすぐ行けば辿り着けるようになっている.
つまり,任意の $k$ に対して,$X_k^{(i)} = X_{(k+1)\ \mathrm{mod}\ N_i}^{(i)}$ または $Y_k^{(i)} = Y_{(k+1)\ \mathrm{mod}\ N_i}^{(i)}$ が成り立つ.
$i$ 番目のバスは,最初 $(X_1^{(i)}, Y_1^{(i)})$ のマスからスタートし,毎時間上下左右のどちらかのマスに移動し,順番に与えられたマスを最短時間で巡回するように移動する.
バスは同時に出発し,ある時間で $2$ つのバスが同じセルにたどり着くと,そこで衝突してストップしてしまう.
衝突するかどうか判定して,衝突するならば,どのマスで衝突するかを求める問題.

解法

一歩ずつシミュレーションすれば良い.
両方のバスが,最初のマスに同時に戻ってこれたなら,以下ループするから衝突はしない.
バスのルートの長さは,指定された隣り合うセルは高々 $30$ 程度しか離れていなくて,$30$ セルしか指定されないので,高々 $900$ ステップ程度の閉路.
よって,高々 $900^2$ ステップぐらいすれば,$2$ つのバスは最初に戻る.
時間計算量は,座標の範囲を $K = 30$ とすれば $O(K^2 N_1 N_2)$ 程度.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年09月25日07時51分51秒
Last modified: 2015年12月16日02時14分37秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: