Krzysztof Diks, Marcin Kubica

Tłumaczenie

Score

Score (wynik) jest grą dwuosobową, w której gracze przesuwają ten sam jeden pionek po planszy. Plansza do gry składa się z N pozycji ponumerowanych od 1 do N i strzałek. Każda strzałka prowadzi od jednej pozycji do innej. Każda pozycja należy do dokładnie jednego z graczy, którego nazywamy właścicielem tej pozycji. Dodatkowo każdej pozycji jest przypisana dodatnia wartość. Wszystkie wartości są różne. Pozycja 1 jest pozycją startową. Początkowo wynik (ang. score) każdego z graczy wynosi 0.

Reguły gry są następujące. Oznaczmy przez C pozycję pionka na planszy przed wykonaniem ruchu. Na początku gry C jest pozycją startową (nr 1). Ruch w grze polega na wykonaniu następujących czynności:

1. Jeśli wartość C jest większa niż aktualny wynik właściciela tej pozycji, to jego wynik wzrasta do wartości C. W przeciwnym przypadku wynik właściciela nie zmienia się. Wynik drugiego z graczy nie ulega zmianie.
2. Następnie właściciel C wybiera jedną ze strzałek wychodzących z aktualnej pozycji pionka i przesuwa go na pozycje, do której prowadzi strzałka. Nowa pozycją staje się aktualną pozycją pionka. Zwróć uwagę, że ten sam gracz może wykonać kilka kolejnych ruchów z rzędu.

Gra kończy się, gdy pionek powraca na pozycję startową. Zwycięzcą gry jest gracz z większym końcowym wynikiem.

Strzałki są zawsze poprowadzone w następujący sposób:

• Z każdej aktualnej pozycji pionka zawsze wychodzi co najmniej jedna strzałka.
• Każda pozycja P jest osiągalna z pozycji startowej, tzn. istnieje ciąg strzałek prowadzący z pozycji startowej do P.
• Masz gwarancję, że gra zawsze się kończy w skończonej liczbie ruchów.

Napisz program, który gra w Score i wygrywa. W każdej grze, w której będzie uczestniczył Twój program podczas testowania, ma on możliwość zwyciężyć, niezależnie od tego czy akurat rozpoczął grę, czy nie. Przeciwnik zawsze gra optymalnie, tzn. jeśli dasz mu tylko szansę, to wygra, a Twój program przegra.

WEJŚCIE/WYJŚCIE

Twój program wczytuje dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście. Twój program to gracz nr 1, natomiast przeciwnik to gracz nr 2. Po uruchomieniu Twój program powinien najpierw przeczytać następujące dane ze standardowego wejścia.

Pierwszy wiersz zawiera jedną liczbę całkowita - liczbę pozycji N, . Pozycje są ponumerowane od 1 do N. Każdy z kolejnych N wierszy zawiera N liczb całkowitych opisujących strzałki. Jeśli istnieje strzałka prowadząca od pozycji i do pozycji j, to j-tą liczbą w i-tym z tych wierszy jest 1, w przeciwnym przypadku 0.

Kolejny wiersz zawiera N liczb całkowitych opisujących właścicieli poszczególnych pozycji. Jeśli właścicielem pozycji i jest gracz nr 1 (Twój program), to i-ta z tych liczb jest równa 1, w przeciwnym przypadku i-ta liczba jest równa 2.

Kolejny wiersz zawiera N liczb całkowitych - wartości poszczególnych pozycji. Jeśli i-ta z tych liczb jest równa j, to wartością pozycji i jest j. Wszystkie wartości j są różne i spełniają nierówności .

Następnie rozpoczyna się gra.

Pozycją początkowa pionka jest pozycja nr 1. Twój program powinien grać następująco i zakończyć działanie po powrocie pionka na pozycję nr 1:

• Jeśli jest to ruch Twojego programu, to Twój program powinien wypisać na standardowe wyjście numer następnej pozycji P, .

• Jeśli jest to ruch przeciwnika, to Twój program powinien wczytać ze standardowego wejścia numer następnej pozyji P, .

Rozważmy następujący przykład. Plansza do gry jest przedstawiona na rysunku 1. Pozycje zaznacznone kółkami należą do gracza nr 1, a pozycje zaznacznone kwadratami należą do gracza nr 2. Wewnątrz każdej pozycji znajduje się jej wartość, a numer pozycji jest zapisany na zewnątrz. Poniżej przedstawiono rozgrywkę.

Po zakończeniu gry wynikiem Gracza 1 jest 3, natomiast Gracza 2 - 2. Gracz 1 wygrywa.

WYTYCZNE PROGRAMISTYCZNE

W przykładach poniżej target jest całkowitoliczbową zmienną oznaczającą pozycję.

Jeśli programujesz w C++ i korzystasz z iostreams, powinieneś stosować następującą konwencję czytania ze standardowego wejścia i pisania na standardowe wyjście:

cin>>target;
cout<<target<<endl<<flush;      

Jeśli programujesz w C lub C++ i korzystasz ze scanf i printf, powinieneś stosować następującą konwencję czytania ze standardowego wejścia i pisania na standardowe wyjście:

scanf ("
printf("

Jeśli programujesz w Pascalu, powinieneś stosować następującą konwencję czytania ze standardowego wejścia i pisania na standardowe wyjście:

Readln(target);
Writeln(target);

NARZĘDZIA

SPOSÓB OCENY