------------------------------------------------------
| PROBLEMA 42: SOARECELE SI PISICA |
| DEADLINE: Vineri, 3 martie 2000 |
| TIMP DE IMPLEMENTARE: nelimitat |
| PUNCTAJ: 70 dex |
| TIMP DE EXECUTIE: 10 secunde |
------------------------------------------------------
Se da un graf nedirectat si 3 noduri speciale in graful respectiv. Primul
nod este nodul de unde pleaca pisica, al doilea este nodul de unde pleaca
soarecele si al treilea este casa soarecelui. In fiecare moment pisica si
soarecele ocupa fiecare exact un nod in graf. Pisica si soarecele se muta
alternativ (pisica se muta prima data) catre un nod alaturat fata de
pozitia curenta. Pisica cashtiga daca ajunge sa fie in acelasi nod cu
soarecele. Soarecele cashtiga daca ajunge acasa inainte sa fie prins.
Jocul este remiza daca cei 2 jucatori ajung intr-o pozitie in care au mai
fost.
Tu trebuie sa scrii un program care determina daca pisica are strategie
de cashtig.
INPUT:
n 0<=n<=200, n numarul de noduri
X_{0,0} X_{0,1} ... X_{0,n-1} matricea de adiacenta a grafului
... X_{i,j}=1 iff exista muche intre i si j
X_{n-1,0} X_{n-1,1} ... X_{n-1,n-1}
m numarul de teste (tripleti a b c)
a_1 b_1 c_1 a - nodul de unde pleaca pisica
... b - nodul de unde pleaca soarecele
a_m b_m c_m c - casa soarecelui
0<=a,b,c<n; 0<m<=100
Ieshirea consta in m linii, pe linia #i, 1 daca pisica are strategie pt
testul #i, 0 altfel
OUTPUT:
0 sau 1 testul 1, 1 daca pisica are
... strategie de cashtig, 0 altfel
0 sau 1 testul m...
|
|
