以下是NPSC 2010 高中組決賽的題目: 矢量星球
http://zerojudge.tw/ShowProblem?problemid=b254
我們現在都生活在三維的世界裡,對更高維度的東西總是難以想像。但是在矢量星球中,他們的世界是個n個維度的空間。在這空間中,有種叫矢量的東西。它是一個n-序對,代表一個點相對於星球中心的位置。
羅敷跟小瀠是矢量星球上的好朋友,他們最喜歡玩的遊戲就是「Orthogonoal Family」,這個遊戲要怎麼玩呢?規則如下:
因為羅敷年紀比較小,所以從羅敷開始。接下來小瀠跟羅敷輪流做以下事情。
1. 畫一條矢量 v=(v1 , v2 , v3 , … , vn)。
2. 檢查是否跟之前畫的矢量都垂直。如果是的話,就繼續。不然畫的那個人就輸了。 然而,他們已經大戰幾百回合,卻無法檢查是否遊戲已經結束了。看來檢查垂直這件事情似乎沒有這麼容易,因此她們想要請你寫一支程式幫忙。
兩條矢量u,v垂直,若寫成 v=(v1 , v2 , v3 , … , vn), u=(u1 , u2 , u3 , … , un),v1*u1 + v2*u2 + …… + vn*un=0。
給你他們玩樂的紀錄,你要決定遊戲的結果。
雖然多數NPSC參加隊伍都輕而易舉的在時間內通過了上面的題目
但是你希望程式可以跑得更快, 更有效率一點!!
想個更有效率的方法解決這題吧!
每一組遊戲由兩個整數n,m開頭的一行,代表在n維度的空間(0<n<=1000000),已經玩了m個回合(0<m<=100000)。
接下來是m行,每一行都由一個整數k(0<k<=100)代表這條線v表成 (v1,v2,v3,…,vn) 有幾個vi非零,接下來會依序給予空白分開之整數對 ”i:d” 代表vi=d。(0<i<=n, d=1或-1) 一行中,後面的i一定比前面的大。
(每組測試資料中, 保證出現的數對總數不會超過一百萬組。)
n=m=0,代表input結束。
如果羅敷已經贏了,就印出一行Rofu;
如果小瀠已經贏了就印出一行Yin;
如果還無法決定,就印出一行Hakuna matata。
100 4 5 1:1 2:-1 3:1 4:1 5:1 2 1:1 2:1 1 6:1 1 7:-1 2 2 1 1:1 1 1:1 0 0
Hakuna matata Rofu
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|