c++ pomoc przy programie

Witam, potrzebuję jakichś porad przy programie:
http://ki.staszic.waw.pl/task.php?name=robaki

Nie wiem nawet jak się za niego zabrać

Pierwsza myśl (może być zupełnie bezużyteczna ;P)

• zakrywamy deskami spójne dziury z robakami w kolejności od największej ilości do najmniejszej (tzn od takiego kawałka gdzie obok siebie mamy najwięcej dziur z robakami)
• jeśli brakło gwoździ a są jeszcze nie zakryte dziury to znajdujemy takie dwie deski które "najtaniej" możemy połączyć (tzn między nimi jest jak najmniej wolnej przestrzeni), łączymy te dwie deski i zwracamy gwoździa do puli.

Dzieki ;)
Może jeszcze jakieś pomysły?

samael69x napisał(a)

Dzieki ;)
Może jeszcze jakieś pomysły?

A ty jakiś masz? Na razie widzę, że twój pomysł wygląda tak: po co mam coś zrobić sam, jak ktoś mógłby to zrobić za mnie. Chcesz gotowe rozwiązanie, żeby coś zaliczyć, czy chcesz się czegoś nauczyć, ale nie chce ci się myśleć? Może podziel się swoimi rozważaniami na ten temat.

@shalom - a może bez tego pierwszego kroku, tzn. Najpierw zakrywamy wszystko pojedynczymi kawałkami, a później łączymy najbliższe kawałki aż do momentu kiedy nam starczy gwoździ.

dla zadania przykładowego wyglądałoby to tak:

- - dziura
x - robak
O - deska

1. stan początkowy
-x-xx-xxx-xx

2. algorytm "nieekonomiczny"
-O-OO-OOO-OO

3. łączenie stykających się desek
-O-()-( )-()

4. brakuje 2 gwoździ - łączymy najbliższe
-(  )-(    )

do chodnik:
Sorry, ale jeżeli bym potrafił to zrobić to bym nie prosił o to was, siedziałem już nad tym programem i nie wpadał mi żaden pomysł. Mi nie chodzi o to żeby ktoś napisał za mnie gotowy program, tylko dał jakąś poradę tak jak to zrobił MSM. Zobrazował mi on wszystko w przejrzysty sposób i już powinienem sobie z tym poradzić.

Nie, no można i tak do tego podejść. To powiedz po co musisz ten program napisać? A może masz jakieś swoje przemyślenia na temat tych porad, np. masz już teraz lepszy pomysł?

program jest na dodatkowe zajecia z programowania, jestem ucznie technikum inf.
W tej chwili doszedłem do:
-zeruję tablicę
-wczytuję elementy tablicy i tab[elementu] ustawiam na 1 (dziury z robakami) (na przykładzie otrzymuję 010110111011)
-potem sprawdzam czy są robaki w sąsiednich dziurkach, jezeli tak to sumuję to i przenoszę do tablicy( wychodzi 01020302)

W tym momencie się zatrzymałem, musze liczyć puste dziurki i gdy ten odstępn jest najmniejszy powinienem łączyć deski w jedną dopóki liczba desek będzie równa k (troszkę zagmatwałem ale nie potrafię tłumaczyć)

Chyba najłatwiejsze rozwiązanie:

• to sumowanie bym sobie odpuścił i zostawił tablicę 0-1
• następnie przeglądasz tablicę od początku wpisując do tablicy np. 2 w miejsce gdzie wstawiasz deskę. Deski wstawiasz od samego początku zakrywając spójne kawałki i zmniejszając liczbę gwoździ. Jednocześnie pamiętasz gdzie odległość między dwiema deskami była najmniejsza. Kiedy skończą się gwoździe to łączysz dwie deski których pozycję zapamiętałeś i robisz kolejną iterację.
  To ma pesymistycznie O(n^2) złożoności. Jeśli chcesz szybciej to musiałbyś mieć np. kopiec/kolejkę priorytetową gdzie wrzucałbyś te odległosci między deskami. W ten sposób nie musiałbyś za każdym razem od nowa szukać tej minimalnej odleglosci, tylko wyciągałbyś ją z kopca. To by nam dalo O(nlogn).