szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 lis 2017, o 21:40 
Użytkownik

Posty: 46
Lokalizacja: Łódź
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ę?
Góra
Mężczyzna Offline
PostNapisane: 14 lis 2017, o 03:33 
Moderator

Posty: 2720
Lokalizacja: Kraków
Jeżeli możliwe jest rozstawienie żołnierzy na kwadracie o boku t, to możliwe jest też rozstawienie ich na kwadracie o boku u \ge t. Wyszukiwanie binarne + podejście zachłanne powinno dać dobre rozwiązanie.
Góra
Mężczyzna Offline
PostNapisane: 14 lis 2017, o 15:40 
Użytkownik

Posty: 46
Lokalizacja: Łódź
Afish napisał(a):
Jeżeli możliwe jest rozstawienie żołnierzy na kwadracie o boku t, to możliwe jest też rozstawienie ich na kwadracie o boku 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.
Góra
Mężczyzna Offline
PostNapisane: 14 lis 2017, o 15:49 
Moderator

Posty: 2720
Lokalizacja: Kraków
SciTuber napisał(a):
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ć 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.
Góra
Mężczyzna Offline
PostNapisane: 14 lis 2017, o 15:55 
Użytkownik

Posty: 3772
Lokalizacja: Kraków PL
Zadanie pochodzi ze strony Kółka Informatycznego w XIV LO im. S. Staszica w Warszawie.

Temat zadania:
Cytuj:
Ż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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Algorytmy] OIG VI - Apteka  Mike148  3
 [Algorytmy] schematy blokowe - zadanie 2  Insane  0
 [Prolog][Algorytmy]Tworzenie koniunkcyjnej postaci normalnej  damian0021  0
 [Algorytmy] Sortowanie linii w pliku  mariuszm  4
 [Algorytmy] Wyszukiwanie maksimum - zadanie 2  kalik  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl