[Algorytmy] Rozstawianie na planie kwadratu

SciTuber
Użytkownik
Użytkownik
Posty: 51
Rejestracja: 19 sty 2016, o 15:57
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 15 razy

[Algorytmy] Rozstawianie na planie kwadratu

Post autor: SciTuber » 13 lis 2017, o 21:40

Witam,
mam problem z poniższym zadaniem: http://ki.staszic.waw.pl/task.php?name=zol - wydaje mi się, że trzeba zastosować tu algorytm wyszukiwania binarnego, acz nie mam za bardzo pomysłu na najbardziej wydajne podejście do zadania - nie przychodzi mi znalezienie jakiejś zależności, mógłbym prosić o jakąś wskazówkę?
Ostatnio zmieniony 14 lis 2017, o 03:32 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.

Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmy] Rozstawianie na planie kwadratu

Post autor: Afish » 14 lis 2017, o 03:33

Jeżeli możliwe jest rozstawienie żołnierzy na kwadracie o boku \(\displaystyle{ t}\), to możliwe jest też rozstawienie ich na kwadracie o boku \(\displaystyle{ u \ge t}\). Wyszukiwanie binarne + podejście zachłanne powinno dać dobre rozwiązanie.

SciTuber
Użytkownik
Użytkownik
Posty: 51
Rejestracja: 19 sty 2016, o 15:57
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 15 razy

Re: [Algorytmy] Rozstawianie na planie kwadratu

Post autor: SciTuber » 14 lis 2017, o 15:40

Afish pisze:Jeżeli możliwe jest rozstawienie żołnierzy na kwadracie o boku \(\displaystyle{ t}\), to możliwe jest też rozstawienie ich na kwadracie o boku \(\displaystyle{ u \ge t}\). Wyszukiwanie binarne + podejście zachłanne powinno dać dobre rozwiązanie.
Dziękuję za odpowiedź. Czy w takim razie poprawnym działaniem będzie znalezienie najdłuższego boku kwadratu z możliwych (równy ilości rzędów), obliczenie ilości wszystkich żołnierzy i znalezienie najmniejszej potęgi liczby całkowitej z przedziału <liczba żołnierzy; kwadrat ilości rzędów>? Szczerze powiedziawszy, to nie jestem do końca przekonany do tego rozwiązania, a do głowy nic innego mi nie przychodzi.
Pozdrawiam.

Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmy] Rozstawianie na planie kwadratu

Post autor: Afish » 14 lis 2017, o 15:49

SciTuber pisze:znalezienie najdłuższego boku kwadratu z możliwych (równy ilości rzędów), obliczenie ilości wszystkich żołnierzy i znalezienie najmniejszej potęgi liczby całkowitej z przedziału <liczba żołnierzy; kwadrat ilości rzędów>
A po co tak? Maksymalanie rzędów może być \(\displaystyle{ 10^9}\), minimalnie może być jeden rząd, możemy ruszać z wyszukiwaniem binarnym. Dokładna stała nas nie boli, najwyżej zrobimy kilka dodatkowych obrotów, ale logarytm z maksymalnej liczby rzędów jest tak mały, że spokojnie możemy wziąć z dużym naddatkiem, a dzięki temu nie bać się, że popełnimy głupi błąd przy wyznaczaniu granic wyszukiwania binarnego.

SlotaWoj
Moderator
Moderator
Posty: 4211
Rejestracja: 25 maja 2012, o 21:33
Płeć: Mężczyzna
Lokalizacja: Kraków PL
Podziękował: 2 razy
Pomógł: 757 razy

Re: [Algorytmy] Rozstawianie na planie kwadratu

Post autor: SlotaWoj » 14 lis 2017, o 15:55

Zadanie pochodzi ze strony Kółka Informatycznego w XIV LO im. S. Staszica w Warszawie.

Temat zadania:
Żołnierze z całej bazy (bynajmniej nie chodzi o bazę danych!) spieszą się na apel. Powinni ustawić się na planie kwadratu, tak, żeby każdych dwóch żołnierzy mieszkających w tym samym budynku stało na apelu obok siebie, czyli w tym samym rzędzie kwadratu. Ponadto, żołnierze z poszczególnych budynków muszą stać po kolei, tzn. poczynając od pierwszego rzędu: pierwszy budynek, drugi budynek, itd. Pomóż znaleźć najmniejszą długość boku takiego kwadratu.
Jeżeli czterech mieszka w tym samym budynku, to razem w jednym rzędzie, ale nie obok siebie. Relacja stania obok siebie w języku polskim nie jest przechodnia. Obok siebie, tzn łokieć w łokieć. Staszic się w grobie przewraca.

ODPOWIEDZ