Codeforces #74

上次腦殘之後，人品突然挺好的…

A: 問每個參賽者的答題的分數，成功及失敗的挑戰，問比賽的贏家是誰。保証只有一個贏家。極點頹題。

B: 捉迷藏遊戲。查票員會從火車的頭卡至尾卡不斷的來回檢查，每個時刻只會移動一個車廂。逃票人則在火車移動的時候選擇留守同一車廂，或向附近一車廂移動。如果火車停站了，他可以先行離開車廂，並能進入任意一個車廂，假設這個步驟是不看耗時的。現在給了查票員和逃票人的最初位置，和查票員的行走方向，並保証最後一個時刻是終點站，問給定每個時刻火車是到站還是行走中，逃票人能否不被查票員逮著？即使一定被逮到，最遲必定在甚麼時候被逮著？其實處理上有點麻煩的，對於火車移動的時刻，逃票人的移動有最多3個選擇，並且對查票員的前後移動跟逃票人的距離進行排序，然後往最遠距離的一點移動。如果該距離只能是0的話則會被抓。對於火車停站的時刻，逃票人永遠可以躲在查票員背對的盡頭的車廂，當然，若查票員已站在頭卡或尾卡，則必須站在該對面盡頭即可。寫的時候人品超好，一次就寫對了…

C: 問一個　$N \times M$ 的板，問有多少條不同的桌球的彈道。球的移動遵從45度的斜線運動，碰壁的話會改變方向。卡了很久沒能找到 $O(1)$ 算式…至放棄時想想不如直接寫程序計算一些數值再想想，但之前已經想到一件事﹕彈道必先會經過第一行的其中一個格子。寫的時候想到不用逐步移動，直接可以算出碰在那了。然後在第一行的起點經過剛好3次就能保証遍歷一條完整的彈道。跑的時候跟手算答案一致，無聊試試最大的情況 $N = M = 10^6$ ，竟然不消半晌就跑出答案了﹗後來猛然醒起寫的時候那個直接算出碰撞點可以讓算法變得很高效的…直接提交並通過了。早知一早放棄手寫，然後寫程序找答案還來得有效。後來看tourist的答案… $\text{gcd}(N-1, M-1)+1$ …徹底輸了。

D, E: 待補