2011-06-28 16:14:59Morris
b254. C. 矢量星球
b254. C. 矢量星球
/**********************************************************************************/
/* Problem: b254 "C. 矢量星球" from 2009 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC (20ms, 4148KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-27 12:31:55 */
/**********************************************************************************/
#include<stdio.h>
int Vi[500][1000], Vd[500][1000], Vn[500];
int check(int k) {
int a, In1, In2, s;
for(a = 0; a < k; a++) {
In1 = 0, In2 = 0, s = 0;
while(In1 < Vn[a] && In2 < Vn[k]) {
if(Vi[a][In1] < Vi[k][In2]) In1++;
else if(Vi[a][In1] > Vi[k][In2]) In2++;
else
s += (Vd[a][In1++]*Vd[k][In2++]);
}
if(s) return (k&1) + 1;
}
return 0;
}
main() {
int n, m, a, b;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0) break;
int flag = 0;
for(a = 0; a < m; a++) {
scanf("%d", &Vn[a]);
for(b = 0; b < Vn[a]; b++)
scanf("%d:%d", &Vi[a][b], &Vd[a][b]);
if(flag == 0) flag = check(a);
}
switch(flag) {
case 0: puts("Hakuna matata"); break;
case 1: puts("Yin"); break;
case 2: puts("Rofu"); break;
}
}
return 0
內容 ：
我
們現在都生活在三維的世界裡，對更高維度的東西總是難以想像。但是在矢量星球中，他們的世界是個n個維度的空間。在這空間中，有種叫矢量的東西。它是一個
n-序對，代表一個點相對於星球中心的位置。 羅敷跟小瀠是矢量星球上的好朋友，他們最喜歡玩的遊戲就是「Orthogonoal
Family」，這個遊戲要怎麼玩呢？規則如下： 因為羅敷年紀比較小，所以從羅敷開始。接下來小瀠跟羅敷輪流做以下事情。 畫一條矢量v=(v1 ,
v2 , v3 , … , vn)。 檢查是否跟之前畫的矢量都垂直。如果是的話，就繼續。不然畫的那個人就輸了。
然而，他們已經大戰幾百回合，卻無法檢查是否遊戲已經結束了。看來檢查垂直這件事情似乎沒有這麼容易，因此她們想要請你寫一支程式幫忙。
兩條矢量u,v垂直，若寫成v=(v1 , v2 , v3 , … , vn), u=(u1 , u2 , u3 , … , un)，v1 u1+
v2 u2+ …vn un=0。 給你他們玩樂的紀錄，你要決定遊戲的結果。
輸入說明
：
每
一組遊戲由兩個整數n,m開頭的一行，代表在n維度的空間(0<n<100000)，已經玩了m個回合。(0<m<500)。接
下來是m行，每一行都由一個整數k(0<k<1000)代表這條線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
提示
：
出處
：
2009 NPSC 高中組決賽
做法 : 窮舉
把所有向量都拿出來試，參考 NPSC 補完計畫
做法 : 窮舉
把所有向量都拿出來試，參考 NPSC 補完計畫
/**********************************************************************************/
/* Problem: b254 "C. 矢量星球" from 2009 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC (20ms, 4148KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-27 12:31:55 */
/**********************************************************************************/
#include<stdio.h>
int Vi[500][1000], Vd[500][1000], Vn[500];
int check(int k) {
int a, In1, In2, s;
for(a = 0; a < k; a++) {
In1 = 0, In2 = 0, s = 0;
while(In1 < Vn[a] && In2 < Vn[k]) {
if(Vi[a][In1] < Vi[k][In2]) In1++;
else if(Vi[a][In1] > Vi[k][In2]) In2++;
else
s += (Vd[a][In1++]*Vd[k][In2++]);
}
if(s) return (k&1) + 1;
}
return 0;
}
main() {
int n, m, a, b;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0) break;
int flag = 0;
for(a = 0; a < m; a++) {
scanf("%d", &Vn[a]);
for(b = 0; b < Vn[a]; b++)
scanf("%d:%d", &Vi[a][b], &Vd[a][b]);
if(flag == 0) flag = check(a);
}
switch(flag) {
case 0: puts("Hakuna matata"); break;
case 1: puts("Yin"); break;
case 2: puts("Rofu"); break;
}
}
return 0