d692: 矢量星球 - 快速版本
標籤 :
通過比率 : 57% (12 人 / 21 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2010-04-09 16:43

內容

以下是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
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <50M
提示 :
標籤:
出處:
NPSC 2010 高中組決賽 修改 [編輯:
magrady (元元)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」