Cześć. Próbuję rozwiązać zadanie Lampy z 6 OIG http://main.edu.pl/pl/archive/oig/6/lam ale nie mam żadnego pomysłu. Mógłbym liczyć na jakąś podpowiedź z waszej strony :) ?
0
1
Nie masz żadnego pomysłu? No to proszę, algorytm turbo naiwny:
Żeby dodana lampa oświetliła najwięcej jak sie tylko da należy umieścić ją pośrodku największego ciemnego obszaru. Oczywiście w rzeczywistości nie jest to do końca prawda. Bo jeśli "dokładana" lampa miałaby sąsiada który już jest dołożony to w rzeczywistości lepiej byłoby zdjąć tego sąsiada, podzielić ciemny obszar na 3 części i powiesić tam te 2 lampy na punktach podziału.
W przypadku ogólnym:
- Jeśli największym ciemnym obszarem jest taki otoczony przez "stałe" lampy to wstawiamy nową lampę na jego środku
- Jeśli największy ciemny obszar sąsiaduje z dołożonymi lampami to należy je wszystkie zdjąć, dodać nową i powiesić w równych odstępach.
Algorytm raczej słaby, bo kwadratowy, ale pytałeś o "dowolny" pomysł ;)
Na oko kluczem do rozwiązania szybkiego będzie wyliczanie od razu ile lamp wieszać w danej dziurze, bez potrzeby takiej iteracji jak ta którą opisałem wyżej.
1
@Shalom
Twój pomysł jest bliski wzorcówce, wystarczy dodać jakiś kopiec/mapę(też przechodzi). Problem jest taki, po czym te drzewo ma sortować :)
1
@Brave Withelm czy to taki problem? W czasie O(1) można policzyć o ile zwiększy się oświetlony obszar po dodaniu nowej lampy do pewnej istniejącej dziury (dlatego że wystarczy policzyć ile oświetli n+1 lamp w dziurze o zadanym rozmiarze i odjąć od tego aktualnie oświetlony obszar). I tego użyłbym jako klucza w kolekcje priorytetowej / kopcu. Tzn niech wartością będzie delta oświetlenia po dodaniu lampy do danego obszaru. Wybieramy sobie maksa, dodajemy mu lampę, przeliczamy na nowo jego wartość i wrzucamy do kopca. I tak postępujemy aż się lampy nie skończą. W ten sposób mamy ładny zachłanny algorytm ;)
0
@Shalom
No tak :P
Chciałem jednak dać łagodnego hint'a @Archimondei :D a nie całe rozwiązanie d:
0
Dzięki za pomoc, rozumiem już jak ma wyglądać rozwiązanie, natomiast nie mam pojęcia jak mogę policzyć niedoświetlenie przed dodaniem jakiejkolwiek lampy.
1
Serio? Matematyka level szkoła podstawowa. Lampy maja 90 stopni strumienia światła więc każdy nieoświetlony obszar ZAWSZE jest trójkątem równoramiennym 45, 45, 90. Ciekawą własnością takiego trójkąta jest między innymi to, że jest on połową kwadratu i że jego boki to a, a*sqrt(2) i a*sqrt(2) gdzie a*sqrt(2) jest odległością między dwiema sąsiednimi lampami...
Dodatkowo pole takiego trójkąta to pole połowy kwadratu czyli a*a/2.
Jeśli więc przez x oznaczymy sobie odległość między dwiema sąsiednimi lampami to:
x = a*sqrt(2) więc a = x/sqrt(2)
pole = a*a/2 = x*x/4
Tak więc pole nieoświetlonego obszaru między dwiema sąsiednimi lampami które są od siebie oddalone o x wynosi x2/4