d692. 矢量星球 - 快速版本
Tags :
Accepted rate : 13人/26人 ( 50% ) [非即時]
評分方式:
Tolerant

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

Content

以下是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參加隊伍都輕而易舉的在時間內通過了上面的題目

但是你希望程式可以跑得更快, 更有效率一點!!

 

想個更有效率的方法解決這題吧! 

Input

每一組遊戲由兩個整數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結束。

Output

如果羅敷已經贏了,就印出一行Rofu;

如果小瀠已經贏了就印出一行Yin;

如果還無法決定,就印出一行Hakuna matata。

Sample Input #1
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
Sample Output #1
Hakuna matata
Rofu
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <50M
Hint :
Tags:
出處:
NPSC 2010 高中組決賽 修改 [管理者: magrady (元元) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」