Problem C : Pocket Ball †問題概要 †ポケットが四隅に配置されている正方形のビリヤード台があり、ポケットと正方形の辺にはそれぞれ固有の記号がついている。(1:左下,2:右下,3:右上,4:左上,N:上辺,E:右辺,W:左辺,S:下辺) 2つの数p,q(それぞれ1以上100以下の整数)が与えられる。 左下隅から(普通のxy座標系で)傾きがp/qの方向に玉を打ち出す。玉は壁に当たると入射角と反射角が等しくなるように跳ね返る。 玉が当たった壁を順番に出力し、最後に、入ったポケットを出力する。 難易度 †やや易。 解法 †実際は跳ね返るが、跳ね返らずに進み続けるとして考える。 正方形の一辺の距離を1として、 右方向に1進むごとに、EとWを交互に出力。(x = 2nを通過したらW,x = 2n+1を通過したらEを出力) 上方向に1進むごとに、NとSを交互に出力。(y = 2nを通過したらS,y = 2n+1を通過したらNを出力) 両方の座標が同時に整数となるとポケットに入り終了。そのポケットが右辺、左辺のどちらか、上辺、下辺かはそれぞれ分かるので、入ったポケットの番号も分かるだろう。 (単位時間あたり上向きに1/q,右向きに1/p進むとして上のようにすればよいだろう) 議論・その他 †ファイルを添付する † |