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: a
Autor: Marcin Mucha
A: Malowanie

dzień czwarty 9 sierpnia 2002
Plik źródłowy: a.??? (np. pas, c, cpp)
Plik wejściowy: a.in
Plik wyjściowy: a.out

Architekt Numernabis buduje pałac dla Cezara. Rzecz jasna, taki pałac powinien posiadać mnóstwo komnat, najlepiej każdą w innym kolorze. Nowoczesna sztuka urządzania pałaców nakazuje, aby kolory komnat sąsiadujących ze sobą możliwie najbardziej się różniły (w ten sposób przechodząc między komnatami Cezar nie będzie się nudził).

Numernabis ponumerował wszystkie kolory liczbami od 1 do m (m jest jednocześnie liczbą komnat i liczbą dostępnych kolorów) w taki sposób, że kolorom bardzo się od siebie różniącym odpowiadają bardzo się różniące liczby. Przy ustalonym kolorowaniu komnat pałacu można dla każdego przejścia między komnatami obliczyć różnicę wartości kolorów komnat, które to przejście łączy. Numernabis chce zmaksymalizować sumę takich różnic liczoną po wszystkich komnatach, przy czym każda komnata ma być pomalowana innym kolorem.

Pałac ma idealny kształt n-kąta foremnego, a każda z komnat jest wielokątem wypukłym, którego wierzchołki leżą na obwodzie pałacu (ostatni krzyk mody). Po ponumerowaniu wierzchołków pałacu liczbami 1..n (zgodnie z kierunkiem ruchu słońca, kiedy patrzeć na nie z dachu pałacu), każdą komnatę można opisać przez ciąg numerów jej wierzchołków.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego a.in opis komnat pałacu,
  • znajdzie najlepszy układ kolorów komnat,
  • zapisze odpowiednią sumę różnic wartości kolorów w pliku tekstowym a.out.

Wejście

W pierwszym wierszu pliku tekstowego a.in znajdują się dwie liczby całkowite n, m (1 <= n <= 50000, 1 <= m < n-2), będące odpowiednio liczbą zewnętrznych ścian pałacu oraz liczbą komnat. W każdym z kolejnych m wierszy znajduje się opis jednej komnaty (i+1-szy wiersz zawiera opis i-tej komnaty). Opis pojedynczej komnaty jest ciągiem liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwszym elementem tego ciągu jest liczba ścian komnaty, a pozostałe elementy to numery wierzchołków komnaty wymienione w kolejności rosnącej.

Wyjście

Plik tekstowy a.out powinien zawierać dokładnie jeden wiersz. Wiersz ten powinien zawierać tylko jedną liczbę całkowitą - największą możliwą sumę różnic wartości kolorów dla danego pałacu.

Przykład

Dla pliku wejściowego a.in:

7 4
3 1 2 3
3 1 3 5
4 1 5 6 7
3 3 4 5

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

6



Wersja do druku