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

Algorytmika C++

0 głosów
103 wizyt
pytanie zadane 14 stycznia w Algorytmy przez pasjonat_algorytmiki Obywatel (1,140 p.)
Mam problem z algorytmem w zadaniu z 2 etapu OIG z przed około 10 lat. Link: https://szkopul.edu.pl/problemset/problem/isVbAEInYlrdxQNvE6mEnS9i/site/?key=statement

Zrobiłem już pierwszą część zadania. Pozostaje mi najtrudniejsze mam Vector liczb typu long long i muszę znaleźć ile jest kombinacji liczb które podzielone na 3 osobowe grupy ( każda dodana do siebie) dają większą wartość niż k czyli np. 15. Wiem, że mogę łatwo to zrobić 3 pętlami, jednak wtedy złożoność czasowa będzie zdecydowanie za duża (3000 * 3000 * 3000) A mam maksymalnie 2,5 sekund limitu czasu. Vector może mieć maks 3000 elementów.

Nie przychodzi mi nic do głowy.
komentarz 14 stycznia przez Oscar Nałogowiec (26,410 p.)

Pamiętaj, że te 2.5 sekundy dotyczyło komputerów 10 lat temu smiley

1 odpowiedź

0 głosów
odpowiedź 14 stycznia przez Whistleroosh Nałogowiec (34,060 p.)
edycja 14 stycznia przez Whistleroosh
Spróbuj policzyć dystanse jakie mogą pokonać wszystkie rakiety złożone z pierwszego i drugiego modułu. Teraz zastanów się, czy dla dowolnego trzeciego modułu x, jesteś w stanie jakoś szybko policzyć ile jest rakiet złożonych z pierwszego i drugiego modułu i tego x, takich że łączna suma ich pokonanego dystansu jest większa od tego k. Postaraj się skorzystać z tego, że wcześniej policzyłeś wszsytkie rakiety 1+2 modułowe
komentarz 10 marca przez pasjonat_algorytmiki Obywatel (1,140 p.)
Tak udało mi się zrobić to tym sposobem. Sortuję pierwsze 2 moduły i 3 wyszukuję wyszukiwaniem binarnym pierwszy, która spełnia założenie. Z O(n*n*n) wartego 80pkt Robi się O(n*n* log n) Warte 100 pkt z dużym zapasem.

Dziękuję za odpowiedź!

Podobne pytania

0 głosów
1 odpowiedź 574 wizyt
pytanie zadane 17 marca 2017 w Algorytmy przez Patryk Raźny Nowicjusz (120 p.)
0 głosów
2 odpowiedzi 180 wizyt
pytanie zadane 10 listopada 2016 w Algorytmy przez BlueWee Użytkownik (730 p.)
0 głosów
0 odpowiedzi 132 wizyt

88,724 zapytań

137,337 odpowiedzi

306,832 komentarzy

58,909 pasjonatów

Motyw:

Akcja Pajacyk

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

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

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

...