Hej!
Rozwiązywałem ostatnio zadanie pt. Kafelki z ubiegłorocznej edycji Olimpiady informatycznej gimnazjalistów
Treść zadania:
Piotrek jest nowym administratorem systemu Olimpiady Informatycznej
Gimnazjalistów. Jednym z jego obo- wiązków jest opieka nad serwerownią.
Pomieszczenie musi spełnić szereg kryteriów zarówno technicznych, jak i
estetycznych. Aby zapewnić poprawne działanie serwerów, ważne jest, aby podłoga
została pokryta no- woczesnymi kafelkami chłodzącymi.
Piotrek może wybrać jeden z n rodzajów kwadratowych kafelków. Zakładamy, że
kafelków danego rodza- ju można kupić dowolnie wiele, ale nie wolno w jakikolwiek
sposób zmieniać ich wymiarów. Piotrek musi rozpatrzyć wszystkie rodzaje kafelków,
którymi da się całkowicie wyłożyć podłogę i zdecydować, które kupi. Niestety,
nigdy nie był w serwerowni, i nie wie, jakie ma ona wymiary. Pomóż młodemu
administratorowi i napisz program, który dla zadanych wymiarów podłogi w
serwerowni wyliczy, ile różnych rodzajów kafelków może użyć.
Wejście:
W pierwszym wierszu standardowego wejścia zapisano dwie liczby naturalne n i m
(1 <= n, m <= 200 000), oznaczające odpowiednio liczbę rodzajów kafelków i liczbę
zapytań o wymiary serwerowni. W drugim wierszu zapisano n liczb naturalnych xi
(1 <= xi <= 106), oznaczających długość boku i-tego rodzaju kafelków.
W ko-lejnych m wierszach zapisano po jednej parze liczb naturalnych ai, bi (1 <= ai, bi <= 106),
oznaczających zadane wymiary. W testach wartych 50% punktów możesz założyć,
że podłoga serwerowni jest zawsze kwadratem (ai = bi).
Wyjście:
W i-tym wierszu wyjścia powinna znaleźć się jedna liczba naturalna, oznaczająca
liczbę różnych rodzajów kafelków, którymi można wyłożyć podłogę o wymiarach
zadanych w i-tym zapytaniu.
Najprostsze rozwiązanie problemu to po prostu sprawdzenie czy dany rozmiar pokoju jest podziely bez reszty przez i-ty kafelek, ale będzie to rozwiązanie o złożoności m * n => ok. O(n^2), więc w tego typu konkursie nie byłoby to zbyt wysoko punktowane.
Wymyśliłem, że można by to zoptymalizować w taki sposób, że tablicę z wartościami kafelków sortujemy rosnąco quicksortem, i sprawdzamy czy NWD wymiarów pokoju jest podzielny przez i-ty kafelek iterując do czasu aż i-ty kafelek jest mniejszy bądź równy NWD wymiarów pokoju. Jest jednak pewien problem. Mianowicie przy najbardiej pesymistycznym założeniu (czyli takim, że wszystkie kafelki będą mniejsze od NWD każdego pokoju) ten algorytm będzie jeszcze mniej wydajny niż najprostszy o którym wspomniałem wyżej.
Moje pytanie jest następujące - czy w takim przypadku warto "zaryzykować", że zestawy danych będą w miarę optymistyczne i algorytm będzie działał znacząco szybciej niż O(n^2)? Dzięki za pomoc ;)