Polish version    English version  
  Obozy Olimpiady


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
III obóz 2002
IV obóz 2003
V obóz 2004
VI obóz 2005
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Obóz im. A. Kreczmara 2002

Zadanie: sum
Autor: Tomasz Malesiński
Gra w sumowanie

dzień drugi 6 sierpnia 2002

Gra w sumowanie jest grą dla dwóch graczy. Toczy się ona na planszy z narysowanym spójnym grafem nieskierowanym. W każdym wierzchołku grafu zapisana jest liczba całkowita. Przed rozpoczęciem gry losowany jest wierzchołek startowy i ustawiany jest w nim pionek. Gracze mają początkowo po zero punktów. Gracze wykonują ruchy na przemian. Ruch polega na dodaniu liczby znajdującej się w wierzchołku, na którym stoi pionek do liczby punktów gracza wykonującego ruch, a następnie, o ile to możliwe, przesunięciu pionka do sąsiedniego wierzchołka po krawędzi, po której nie przesuwano jeszcze pionka. Jeśli nie można przesunąć pionka w ten sposób, to gra się kończy i wygrywa gracz, który zgromadził więcej punktów. Jeśli liczby punktów są równe, gra kończy się remisem.

Powiemy, że wierzchołek zapewnia istnienie strategii wygrywającej, jeśli w momencie, gdy pionek znajdzie się w tym wierzchołku (niekoniecznie po raz pierwszy), gracz, który ma wykonać ruch, może wygrać niezależnie od tego, jaki jest wierzchołek startowy, jakie ruchy obydwaj gracze wykonywali wcześniej i jakie ruchy będzie później wykonywał przeciwnik.

Zadanie

Twoim zadaniem jest znalezienie wierzchołków zapewniających istnienie strategii wygrywającej na planszach opisanych w plikach sumi.in (1 <= i <= 10) i zapisanie ich w plikach sumi.out. W tym zadaniu oceniane będą jedynie te pliki wyjściowe, a nie program.

Wejście

W pierwszym wierszu pliku wejściowego zapisane są dwie liczby całkowite n i m, gdzie n oznacza liczbę wierzchołków, a m liczbę krawędzi. Wierzchołki są ponumerowane od 1 do n. W następnych n wierszach zapisane są pojedyncze liczby całkowite. Liczba znajdująca się w wierszu o numerze i+1 jest liczbą znajdującą się w i-tym wierzchołku grafu. W następnych m wierszach są po dwie liczby całkowite. Liczby w wierszu o numerze n+i+1 są numerami wierzchołków połączonych i-tą krawędzią.

Wyjście

W pierwszym wierszu pliku wyjściowego powinna znaleźć się liczba k równa liczbie wierzchołków zapewniających istnienie strategii wygrywającej. W kolejnych k wierszach powinny znaleźć się uporządkowane rosnąco numery tych wierzchołków.

Przykład

Dla pliku wejściowego sum0.in:

6 6
1
10
1
1
1
0
1 2
2 3
3 4
4 5
5 2
6 1

poprawną odpowiedzią jest plik wyjściowy sum0.out:

2
2
4

Pozostałe wierzchołki nie zapewniają istnienia strategii wygrywającej, bo po rozpoczęciu gry dowolną z następujących sekwencji ruchów nie istnieje strategia wygrywająca dla gracza, który ma wykonać następny ruch:

2, 5, 4, 3, 2, 1
1, 2, 5, 4, 3
1, 2, 5
1, 6



Wersja do druku