W tym artykule przedstawiam jedno z ulubionych zadań mojego autorstwa. Zostało ono użyte na zawodach CEPC '03 [2] (Central European Programming Contest) jako zadanie F (chociaż w trakcie pracy było nazywane raczej foo — skrót od Football). Dla pierwszej drużyny, która wysłała prawidłowe rozwiązanie, była ufundowana dodatkowa nagroda — piłka nożna. Podczas całych zawodów udało się to trzem drużynom: z Akademii Górniczo-Hutniczej, z Uniwersytetu Wrocławskiego, i z Uniwersytetu Warszawskiego. Najszybsza była drużyna z AGH i to ona wygrała piłkę, natomiast drużyna z UW wygrała cały konkurs (dzięki czemu awansowała do finałów).
Eryk ma klasyczną piłkę nożną złożoną z 32 kawałków skóry — 12 czarnych pięciokątów i 20 białych sześciokątów. Każdy pięciokąt styka się z 5 sześciokątami, a każdy sześciokąt styka się z 3 pięciokątami i 3 sześciokątami. Eryk narysował wielokąt (tzn. linię zamkniętą bez samoprzecięć) na krawędziach między kawałkami skóry. Wielokąt podzielił kulę na dwie części, Eryk pomalował jedną z nich na zielono.
Masz dany opis wielokąta. Czy umiesz policzyć liczbę białych, czarnych, i zielonych kawałków skóry na piłce?
W pierwszej linii wejścia podana jest liczba n oznaczająca liczbę wierzchołków wielokąta. W drugiej podane jest n liczb całkowitych a1, a2, ..., an oddzielonych spacjami. Liczba ai (równa 1 lub 2) jest liczbą zielonych kawałków stykających się w i-tym wierzchołku wielokąta. Bok wielokąta łączący n-ty i pierwszy wierzchołek zawsze leży między dwoma sześciokątami.
Należy wypisać trzy liczby b, w i g. Są to odpowiednio liczby czarnych, białych, i zielonych kawałków.
Dla wejścia:
21
1 2 1 2 1 2 1 1 1 2 2 1 1 1 1 2 2 2 1 1 1
prawidłową odpowiedzią jest:
11 15 6
Jak widzimy, w zadaniu przydaje się wyobraźnia przestrzenna. Może być przydatne narysowanie struktury piłki nożnej, ale jak to zrobić na kartce? Autor jednego z rozwiązań wzorcowych używał do tego pomarańczy. Pomarańcze były dostępne również podczas zawodów, także my (czyli sędziowie monitorujący przebieg zawodów i odpowiadający na pytania) zastanawialiśmy sie, czy któraś z drużyn również wpadnie na ten pomysł...
W rzeczywistości nie trzeba było rysować na pomarańczy, można było rysować mapę piłki nożnej na płaszczyźnie. Chyba najwygodniejszy do tego jest rzut stereograficzny, czyli wyjmujemy jedną ze ścian piłki (np. pięciokątnych), patrzymy do jej wnętrza przez wyjętą ścianę, i rysujemy, co widzimy.
Istnieje kilka różnych rozwiązań tego zadania. Zaczniemy od najbardziej bezpośrednich, skończymy na najbardziej trikowych.
Rozwiązaniem bezpośrednim jest rozpisanie całej struktury piłki nożnej w jakiejś tablicy, rysowanie wielokąta na tej strukturze, i policzenie, które ściany (pięciokąty i sześciokąty) są wewnątrz wielokąta, które na zewnątrz. Chyba najprościej to zrobić w ten sposób, że wierzchołkami grafu są ściany, a krawędziami są krawędzie między nimi. Taki graf ma 32 wierzchołków i 90 krawędzi, także daje się go rozrysować w trakcie 5 godzin zawodów (być może przy pomocy pomarańczy), ale teraz nie będziemy tego robić. Rysowanie wielokąta polega na tym, że zaznaczamy krawędzie, po których przeszliśmy. Potem wystarczy policzyć wierzchołki każdego rodzaju w każdej z dwóch spójnych składowych grafu, który powstaje po eliminacji zaznaczonych krawędzi. Być może można sobie jakoś uprościć zadanie korzystając z wielu symetrii piłki nożnej (dzięki którym moglibyśmy wpisywać tylko część grafu, reszta byłaby symetryczna).
Opis piłki z zadania jest jednoznaczny — jeśli na piłce będziemy rysować pięciokąty i sześciokąty tak, żeby każdy pięciokąt stykał się z 5 sześciokątami, a każdy sześciokąt z 3 pięciokątami i 3 sześciokątami na przemian, to otrzymamy prawidłową strukturę piłki nożnej (z 12 pięciokątami i 20 sześciokątami). Łatwo to sprawdzić na płaszczyźnie — rysujemy najpierw pięciokąt, do każdego z jego boków dobudowujemy sześciokąt, tam, gdzie sześciokąty się stykają dobudowujemy nowe pięciokąty, itd. — otrzymamy wtedy oczywiście rzut stereograficzny piłki. Jeśli dobrze pamiętam, to rozwiązanie zwycięskiej drużyny z UW było oparte właśnie na tym spostrzeżeniu — samodzielnie budowało graf piłki nożnej zgodnie z podanymi zasadami. Dokładnych szczegółów nie będę podawał, gdyż kolejne rozwiązanie jest ciekawsze; zainteresowani mogą spróbować samemu zaimplementować taki pomysł.
Policzmy, ile kątów leżących przy brzegu wielokąta na jego zewnątrz jest czarnymi kątami pięciokątów, a ile jest białymi kątami sześciokątów. Przykładowo, dla wielokąta z przykładu mamy 18 czarnych kątów (położonych przy wierzchołkach numer 1, 2, 3, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21) i 16 białych kątów (1, 3, 4, 5 dwa razy, 6, 7, 8, 9, 12, 13, 14, 15, 19, 20, 21). Oznaczmy liczbę czarnych kątów przez eb, białych kątów przez ew. Okazuje się, że rozwiązanie
daje się policzyć, znając same liczby n, eb i ew (n to n z zadania, czyli liczba wierzchołków zielonego wielokąta). W dodatku liczby, o które prosi nas zadanie, zależą w sposób liniowy od tych trzech wartości.
Jak policzyć eb i ew? Jest to stosunkowo proste. Wszystkie wierzchołki piłki nożnej (jest ich 60) są jednakowe: stykają się w nich 2 sześciokąty i 1 pięciokąt. Możemy wejść do takiego wierzchołka z 3 stron (między sześciokątami, na lewo od pięciokąta, albo na prawo od pięciokąta). Wiedząc, z której strony wchodzimy, i w którą stronę skręcamy (zgodnie z liczbą ai podaną na wejściu), możemy policzyć, ile kątów zewnętrznych przy naszym wierzchołku jest białych, ile jest czarnych, i z której strony wchodzimy do kolejnego wierzchołka. Budując coś w rodzaju automatu skończonego o trzech stanach otrzymujemy krótki program liczący.
(Autor zadania był miły i podał kierunek skrętu dla każdego wierzchołka na brzegu, chociaż w zasadzie nie trzeba było podawać kierunku skrętu dla ostatniego wierzchołka. Trochę to upraszcza rozwiązanie, chociaż bez tego też dałoby sobie poradzić, bo wiemy, że na końcu musimy skręcić w taką stronę, by być znów między dwoma sześciokątami.)
Poniższe rozwiązanie nie liczy n, eb i ew, tylko bezpośrednio wyznacza, o ile zmieniają się wartości b, w i g po przejściu każdego wierzchołka. Niektóre współczynniki w funkcji liniowej nie są całkowite, dlatego zamiast liczyć b, w, g działamy na ich dziesięciokrotnościach.
int tab[3][2][4] = {
{{+10,+15,-25,1},{-10,-15,+25,2}},
{{+10,+15,-25,0},{-10,-20,+30,1}},
{{+10,+20,-30,2},{-10,-15,+25,0}}
};
int main() {
int state = 0;
int n, i, k;
int black = 60, white = 100, green = 160;
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &k); k--;
black += tab[state][k][0];
white += tab[state][k][1];
green += tab[state][k][2];
state = tab[state][k][3];
}
printf("%d %d %d\n", black/10, white/10, green/10);
return 0;
}
A jak znaleźć liniową zależność między n, eb i ew? Można to zrobić na dwa sposoby.
Ten wzór chyba powinien być znany wszystkim lepszym zawodnikom: dla grafu płaskiego (albo narysowanego na sferze, jak w naszym zadaniu) liczba wierzchołków N, liczba ścian F i liczba krawędzi M spełniają równanie N+F = M+2. Na przykład, zanim pomalujemy piłkę nożną, było 32 ścian, 60 wierzchołków, i 90 krawędzi (32+60 = 90+2). Wzór Eulera albo związana z nim charakterystyka Eulera może nieoczekiwanie przydać się do trikowego rozwiązania jakiegoś problemu (zwykle liczenie ścian jest trudne, a wierzchołków i krawędzi bardzo łatwe; jeśli w zadaniu chodzi o liczenie ścian, to wzór Eulera łatwo daje nam rozwiązanie. Trzeba tylko uważać, żeby obszary z zadania były rzeczywiście ścianami, czyli nie dało ich się podzielić krawędzią tak, by obszar się nie rozpadł — jest to równoważne temu, że graf jest spójny). Innym ciekawym przykładem programu korzystającego z charakterystyki Eulera jest ten program [4], który należy kompilować z opcją -Dif=while. (Przykładowym wejściem do programu jest ten plik [5] , a wyjaśnienie jest tutaj [6].)
Jak z niego skorzystać w naszym zadaniu? Połączmy wszystkie ściany pomalowane na zielono w jedną. Nie wiemy, ile jest wierzchołków, przy których nie ma zielonej ściany. Oznaczmy tą liczbę przez m. Czy jesteśmy w stanie policzyć wartości, o których mówi wzór Eulera?
Liczba wierzchołków naszego grafu to n+m (jest n wierzchołków ściany zielonej i m wierzchołków bez ściany zielonej).
Liczba ścian to b+w+1 (b czarnych ścian, w białych ścian, i 1 zielona ściana).
Liczba krawędzi to połowa n+5b+6w (ściana zielona ma n krawędzi, każda czarna 5, a każda biała 6; każdą krawędź liczymy tutaj 2 razy).
Ze wzoru 2N+2F=2M+4 otrzymujemy, że 2n+2m+2b+2w+2 = n+5b+6w+4.
Teraz policzmy kąty. Białych kątów jest 6w, licząc osobno białe kąty na brzegu i wewnątrz czarno-białego wielokąta, otrzymujemy, że 6w = ew + 2m. Analogicznie, 5b = eb + m. Ten układ 3 równań i 3 niewiadomych daje się rozwiązać. Otrzymujemy liniową zależność na b, w, g od n, eb i ew.
Inspiracją do tego zadania było pewien fakt z geometrii sfery (czyli moim celem jako autora zadania było wymyślenie zadania, które dałoby się łatwo rozwiązać znając ten fakt). Wyobraźmy sobie, że Ziemia ma promień 1, i rysujemy na niej trójkąt sferyczny, którego dwa wierzchołki leżą na równiku w odległości 90 stopni od siebie, a trzeci jest na biegunie. Każdy kąt tego trójkąta ma 90 stopni, czyli suma jest 270 stopni - o 90 stopni, czyli π/2, za dużo. Dla małych trójkątów suma kątów jest bliska 180 stopni; nasz trójkąt jest bardzo duży, jego pole to 1/8 powierzchni sfery, czyli π/2. Możemy też wziąć dopełnienie naszego trójkąta; to też jest trójkąt sferyczny, którego każdy kąt ma 270 stopni, czyli jego suma kątów, 810 stopni, to o 630 stopni = 3,5π za dużo; pole tego trójkąta to 7/8 powierzchni sfery, czyli 3,5π.
Ogólnym faktem jest, że pole trójkąta sferycznego jest równe nadwyżce jego sumy kątów nad 180 stopni (i ogólnie, pole n-kąta jest równe nadwyżce sumy kątów nad 180(n-2)). Ten fakt uogólnia się także w pewien sposób na inne zakrzywione powierzchnie niż sfera o promieniu 1, zamiast pola należy policzyć całkę z krzywizny (twierdzenie Gaussa-Bonneta).
Jak to wykorzystać w naszym zadaniu? Rozważmy biało-czarny wielokąt. Oznaczmy kąt pięciokąta przez 2α, a sześciokąta przez β. Wiemy, że 2α + 2β = 2π, czyli π = α+β. Pole pięciokąta to A = 10α - 3π = 7α - 3β. Pole sześciokąta B = 6β - 4π = 2β - 4β. Natomiast suma kątów naszego wielokąta to s = ebα + ewβ. Pole to s - (n-2)(α+β) = bA + wB. Wartości α i β nie są nam znane, ale możemy je potraktować w sposób symboliczny, czyli osobno wziąć fragmenty z α i z β, otrzymując układ dwóch równań z dwoma niewiadomymi, który również się daje łatwo rozwiązać (i daje prawidłowe rozwiązanie zadania). Trzeba trochę pomyśleć, dlaczego α i β możemy rzeczywiście traktować symbolicznie — przecież tak możemy robić tylko, gdy nasz wzór działa dla każdych α i β, a u nas mają one ustalone wartości. Jednak α i β możemy trochę zmienić, rysując na piłce trochę mniejsze lub trochę większe pięciokąty.
Oryginalnie zadanie zgłosiłem w 2 wariantach. W drugim wariancie struktura piłki była inna: na każdej ścianie dwunastościanu foremnego połączono punkt środkowy z każdym jego wierzchołkiem, otrzymając bryłę o 72 wierzchołkach, której ściany to 60 trójkątów. Tą wersję zadania chyba trudniej zrobić przez rozrysowanie, budowę, albo ze wzoru Eulera; jednak bardzo łatwo jest je zrobić korzystając ze wzoru z geometrii sfery (tym razem pole trójkąta jest znane — 1/60 powierzchni sfery, jak również miary wszystkich kątów - 1/5 albo 1/6 kąta pełnego, zatem nie musimy rozwiązywać żadnego układu równań ani traktować nieznanych wartości w sposób symboliczny).
Odnośniki:
[1] http://informatyka.wroc.pl/node/177
[2] http://cepc.mimuw.edu.pl/
[3] http://pl.wikipedia.org/wiki/Wz%C3%B3r_Eulera
[4] http://www.ioccc.org/2004/kopczynski.c
[5] http://www.ioccc.org/2004/kopczynski-10
[6] http://www.ioccc.org/2004/kopczynski.hint