| III Mistrzostwa Wielkopolski w Programowaniu Zespołowym | 2-3 grudnia 2005 |
|
|
Do państwa MWPZ od pewnego już czasu należy wyspa, która ze względu na trudne warunki geoklimatyczne jest od zawsze niezamieszkała. Jedyne co się na niej działo, to różnego rodzaju badania naukowe, z których też nic szczególnego nie wynikało. Ale właśnie ostatnio się to zmieniło! Otóż na wybrzeżu tej wyspy odkryto bardzo zdrowe prądy geotermiczne, które mają bardzo zbawienny wpływ na zdrowie ludzi. Czy prawda to, czy ktoś chce na tym zarobić - trudno powiedzieć. Co jednak jest pewnikiem - wyspa z dnia na dzień zmienia swoje oblicze. Przyjeżdża coraz więcej ludzi, którzy chcą pobyć trochę na tym dobroczynnym wybrzeżu. Powstają hotele, restauracje, porty morskie... Wszystko rozwija się tak prędko, że bardzo odczuwalny i dotkliwy stał się problem braku sieci komórkowej na wyspie. Brak zasięgu powoduje znaczące straty z powodu niezadowolonych turystów, więc firmy, które otworzyły swoje biznesy na wyspie zwróciły się do Ciebie z prośbą o napisanie programu, który pomoże obsługiwać ich powstającą sieć komórkową.
Sieć ta będzie bardzo specyficzna. Ponieważ wnętrze wyspy jest absolutnie niedostępne, sieć ma być użytkowana tylko na wybrzeżu i tylko na samym wybrzeżu budowane są nadajniki. Jak w każdej sieci komórkowej, także w tej trzeba rozwiązywać podstawowy problem telefonii komórkowej - dwa sąsiednie nadajniki nie mogą obsługiwać rozmów na tej samej częstotliwości. Jest to spowodowane tym, że sąsiednie nadajniki mają pewien obszar, w którym nadają „wspólnie” tzn. dociera sygnał i z jednego i z drugiego. Gdyby te nadajniki obsługiwały rozmowę na tej samej częstotliwości, a jeden z rozmówców znajdował się, lub przemieścił się w obszar „wspólny” wtedy słyszałby w telefonie dwie rozmowy - swoją i swojego odpowiednika z nadajnika obok. Każde dwa sąsiednie nadajniki mają takie miejsce „wspólnego nadawania”, gdyż ich zasięg jest bardzo zbliżony do koła, a przecież nikt nie chce, żeby te koła były styczne, gdyż wtedy pozostawałyby między nimi obszary bez zasięgu. Koła te więc przecinają się. Dodatkowo, za każdą wykorzystywaną częstotliwość płaci się wojsku pewną określoną w umowie kwotę. Im dłużej daną częstotliwość wykorzystujemy w sieci komórkowej, tym więcej płacimy. Czyli chcemy wykorzystywać tych częstotliwości jak najmniej.
Zadanie więc polega na tym, aby projektowany przez Ciebie system umiał, znając strukturę sieci (będącej w tym przypadku zawsze pewną ilością nadajników rozmieszczonych na wybrzeżu okrągłej wyspy - jak to widać na rysunku) oraz ilość rozmów obsługiwanych przez każdy z nadajników, przydzielić częstotliwości do każdego z nich, przy pomocy jak najmniejszej łącznej liczby różnych częstotliwości.
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych, Każdy zestaw danych składa się z dwóch linii. W pierwszej znajduje się N - liczba nadajników na wyspie (3 ≤ N ≤ 20000), a w drugiej znajduje się N dodatnich liczb całkowitych, oddzielonych spacjami, nie większych niż 100, z których każda oznacza liczbę rozmów odbywających się w danej chwili w odpowiednim nadajniku. Uwaga! Oczywiście pierwszy nadajnik na liście sąsiaduje z ostatnim.
Dla każdego zestawu danych prawidłową odpowiedzią powinna być w pierwszej linii minimalna liczba częstotliwości, którą w danej chwili trzeba wykupić od wojska, a w następnych N liniach należy wypisać konkretne częstotliwości przypisane do kolejnych z nadajników. Ważne jest, żeby częstotliwości oznaczać kolejnymi dodatnimi liczbami całkowitymi, czyli przypisywać do nadajników liczby od 1 do maksymalnej częstotliwości. Kolejność częstotliwości pojawiających się na wyjściu nie ma znaczenia, podobnie jak to, które częstotliwości przypiszemy do którego z nadajników. Ważne jest jedynie, aby tak przypisane częstotliwości spełniały warunki na prawidłowe przeprowadzanie rozmów, oraz nie przekraczały wartości największej częstotliwości.
2 3 7 5 3 4 9 2 3 8
15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 1 2 3 4 5 6 7 8 10 13 9 10 2 5 9 11 12 13 14 15 16 17