以下是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
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||