Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP3_1F1 - Relacja

Gimnazjalni koledzy Jasia postanowili zagrać w grę planszową, która składa się z wielu etapów. W każdym z etapów odbywa się rozgrywka, po zakończeniu której, aby przejść na wyższy poziom trzeba rozwiązać pewne dziwne zadanie matematyczne. Jaś chętnie by wziął udział w grze, ale nie bardzo potrafi rozwiązać to zadanie, gdyż nie uważał na lekcjach matematyki. Potrzebuje pomocy. Pomóż mu, pisząc odpowiedni program.

Treścią zadania jest odpowiedź na pytanie, jakie własności i jaki typ ma pewna relacja dwuargumentowa w zbiorze skończonym, składającym się nie więcej niż ze stu elementów. Za każdym razem relacja jest zdefiniowana w następujący sposób: jeżeli i-ty element jest w relacji z elementem j-tym, to na wejściu w osobnym wierszu pojawi się rozdzielona spacjami para liczb i oraz j. Liczba wierszy w zestawie danych jest równa liczbie par (i,j) dla których zachodzi relacja. O wielkości zbioru, w którym określona jest ta relacja można wnioskować na podstawie największej z liczb i lub j w parach.

Wynikiem działania programu będą, co najwyżej dwa wiersze. W pierwszym wierszu będą opisane własności relacji oddzielone spacją. Do oznaczenia własności relacji należy używać skrótów, w następującej kolejności:

  1. Z - zwrotność
  2. PZ - przeciwzwrotność
  3. S - symetria
  4. AS - antysymetria
  5. P - przechodniość
  6. SP - spójność
  7. X - żaden z powyższych

Jeżeli w pierwszym wierszu pojawiła się litera X, program kończy działanie. W przeciwnym przypadku, w wierszu drugim będzie opisany typ relacji. Do oznaczenia własności relacji należy używać oddzielonych spacjami skrótów, w następującej kolejności:

  1. RR - relacja równoważności
  2. RPL - relacja porządku liniowego
  3. RPCz - relacja porządku częściowego – można użyć tylko wtedy, gdy nie było RPL
  4. X - żaden z powyższych

Przykład:

Wejście:

2 3
2 9
3 4
5 7
5 9
6 7
7 8
8 3

Wyjście:

PZ AS
X

Dodane przez:Maciej Boniecki
Data dodania:2010-12-02
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:III Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.