Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1687-059a385e
この記事にトラックバックする(FC2ブログユーザー)

LiveArchive 4813 - Ingenious Metro (この記事を編集する[管理者用])

Source

ACM/ICPC Latin America - South America - 2010/2011
UVa: ACM ICPC Latin America Regional Contest (2010-10-24) (blog)
LiveArchive 4813
SPOJ 7763 [MILAR10] (2010-11-07 20:21追加)

問題概要

1次元平面上の整数座標の場所に,ワープスポットが100000個以下ある.
ワープスポットを1個選んで,現在位置から,ワープスポットに対して対称な位置に移動できる.
何度でも移動して良いとして,与えられた初期位置から終了位置まで移動できるかどうかを判定する問題.

解法

2つのワープスポットを使うことで,2つのワープスポットの距離*2だけ移動できる.
なので,スタート地点と終了地点の距離が,ワープスポット間の距離のGCDの2倍の倍数であれば移動可能.
また1回の移動で可能な場合も忘れず判定する.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1687-059a385e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。