• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie OIG - Kafelki

0 głosów
134 wizyt
pytanie zadane 26 lipca 2018 w Algorytmy przez niezalogowany
edycja 26 lipca 2018

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 ;)

komentarz 26 lipca 2018 przez RafalS VIP (112,950 p.)
O(n2) to kiepska zlozonosc na olimpiadzie gimnazjalnej :D?

1 odpowiedź

0 głosów
odpowiedź 27 lipca 2018 przez GRT_2017 Użytkownik (500 p.)
Witaj,

Moim zdaniem opisywane przez ciebie rozwiązanie nie zdobyłoby dużo więcej punktów niż rozwiązanie siłowe. Nie liczyłbym na przychylność testów. Oczywiście można spróbować je zoptymalizować, stosując różnego rodzaju heurystyki. Ja rozwiązywałbym to zadanie następująco:

1. Zliczyć wystąpienia rozmiarów kafelków

2. Wykorzystaj pomysł z sitem Eratostenesa tzn. dla wszystkich możliwych wymiarów serwerowni, sprawdź ile spośród rozmiarów kafelków je dzieli

3. Na zapytania odpowiadaj za pomocą algorytmu Euklidesa, odwołuje się do odpowiednich komórek tablicy

Jeżeli chodzi o pytanie czy warto ryzykować? Twoje rozwiązanie działa w pesymistycznej złożoności O(n*m*log(k)), gdzie k to maksymalny wymiar serwerowni. Nie jest to dużo wolniej od O(n*m), więc uważam, iż warto zaryzykować.

Pozdrawiam

Podobne pytania

0 głosów
1 odpowiedź 106 wizyt
pytanie zadane 4 lutego w Algorytmy przez Whistleroosh Obywatel (1,740 p.)
0 głosów
0 odpowiedzi 78 wizyt
pytanie zadane 12 sierpnia 2018 w C i C++ przez Ban45zx Początkujący (430 p.)
0 głosów
2 odpowiedzi 188 wizyt
pytanie zadane 23 listopada 2016 w Algorytmy przez Piotr Ponikwia Początkujący (330 p.)
Porady nie od parady
Zadając pytanie postaraj się o szczegółowe opisanie problemu oraz udostępnienie wszystkich istotnych informacji (kody źródłowe, zrzuty ekranu itp.).Opisanie problemu

66,393 zapytań

113,148 odpowiedzi

239,530 komentarzy

46,659 pasjonatów

Przeglądających: 304
Pasjonatów: 13 Gości: 291

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...