Dzień dobry,
pierwszy raz biorę udział w tym konkursie w dodatku jestem początkującym programistą i mam problem z użyciem uruchomienia próbnego.
1.) Wklejam mój kod
2.) Wybieram zadanie
3.) Wybieram język (C++)
4.) Wybieram plik z wejściem pobrany z od jakiegoś użytkownika z innego tematu tego forum.
5.) Nie mam pojęcia co mam wybrać jako bibliotekę. Skąd mam wziąć kollib.h jakieś przykładowe?

Ja mam, ale działa tylko na Windowsie :)

Wszystkich nie sprawdzałem, tylko losowo wybrane po jednym z każdej wielkości, i się zgadzają. BTW, czy macie jakiś skrypt do testowania na dużej ilości plików?

Dzięki, posunęło się dalej, ale tym razem:

Compiling kollib.pas
Compiling message.pp
Linking solution_binary
solution_source.pas(109,1) Error: Error while linking
solution_source.pas(109,1) Fatal: There were 1 errors compiling module, stopping
Fatal: Compilation aborted

Może pogapię się jeszcze na instrukcje na stronach Potyczek...

Potwierdzam testy

Podejrzewam, że powinieneś jeszcze dodać plik z biblioteczką (kollib.pas).

Sortowałem po min(x1,x2) zarówno ciąg początkowy, jak i końcowy. Aby sprawdzić czy kolejność początkową można zamienić na końcową, przesuwałem początkowy ciąg "w nieskończoność" a następnie w kolejności, w jakiej mają stać wysyłałem samochody znów na początek parkingu.
Na drzewie przedziałowym (typu max), zawierającym wysokości samochodów sprawdzałem czy wśród samochodów na pozycjach (w tej nieskończoności) od 0 do i-1 jest taki, że uniemożliwi przejazd na początek parkingu. Oczywistym jest, że wystarczy sprawdzić największy, więc zapytanie to miało złożoność O(lg n). Następnie aktualizowałem drzewo, zamieniając wysokość i-tego samochodu na zero, też w czasie O(lg n). Wykonywałem to dla wszystkich samochodów, zatem złożoność taka, jak sortowania. O(n lg n).
Rozwiązanie całkiem przyjemne i krótkie, ponad połowę kodu zabrała mi implementacja drzewa przedziałowego.

Ja utrzymuję w drzewie (mapie) pary (x,w) w taki sposób by dla rosnących x-ów, w były malejące.

By uniknąć ifów mapa na początku zawiera: (-oo,oo), (oo,0). Wówczas opisane pary (x_j,w_j) oraz (x_k,w_k) zawsze istnieją.

Wstawienie nowej pary (x_i,w_i) wygląda następująco:
(1) znajdujemy (x_j,w_j) o najmniejszym x_j, x_j >= x_i. Jest to najszerszy samochód, który musimy ominąć. Jeśli się nie da to NIE.

(2) jeśli w_i > w_j dodajemy do drzewa parę (x_i,w_i). Jeśli x_i == x_j kasujemy parę (x_j,w_j) (lub po prostu zastępujemy jeśli użyliśmy mapy).

Jeśli dodaliśmy/zastąpiliśmy parę w kroku (2) wtedy:
(3) bierzemy parę (x_k,w_k) o największym x_k, x_k < x_i. Jeśli w_k <= w_i kasujemy parę (x_k, w_k). Jeśli usnęliśmy parę powtarzamy krok (3).

Oczywiście x-y, które wstawiamy to minimalny x samochodu w jednej z pozycji, a wstawiamy w kolejności niemalejących minimalnych x-ów w drugiej.

Czy to zabronione?? ;-)

Może lepsze byłoby wprowadzenie limitu zgłoszeń względem czasu?

Tzn. jedno zgłoszenie na 5 lub 10 min i ew. dodatkowe 5 zgłoszeń nieograniczonych limitem czasowym (pod koniec rundy mogą się przydać).

Innym pomysłem może też być "regeneracja" zgłoszeń, tzn. na start mamy określoną liczbę prób, wykorzystujemy je jak chcemy i np. co 15 min dodaje nam się jedna próba do naszej liczby prób (bez możliwości przekroczenia liczby początkowej).

Te pomysły powinny pozwolić na dużo większą liczbę prób, a jednocześnie mogą być odporne na wspomniane nadużycia.

> Co robię nie tak?

Używasz pascala :P

Można też dla każdego samochodu policzyć najbliższego sąsiada w lewo i w prawo, z którym się nie może wyminąć i prawdą jest, że jeśli nowy porządek zachowuje takie trójki to da się go osiągnąć.
Konieczne jest tu drzewo przedziałowe albo set, więc złożoność nlogn.

Kłaniam się.
Czy ktoś zechciałby opisać w miarę dokładnie jak powinien przebiegać taki test na stronie Potyczek?
Wybieram z menu 'Uruchomienie próbne -rozproszone', wskazuję mój plik kol.pas, wskazuję plik jeden z plików .in przysłanych w ramach rundy 4 (przy okazji wielkie dzięki dla autora!).
W treści mojego 'kol.pas' jest 'uses kollib, message;'
Po uruchomieniu sprawdzania - komunikat:
"kollib.pas(1,1) Fatal: Syntax error, "UNIT" expected but "end of file" found
Fatal: Compilation aborted"

Co robię nie tak?

Nawiasem mówiąc sądziłem, że organizatorzy testują to na jakich własnych danych wejściowych, nie mówiąc o bibliotekach interaktywnych.

Oczywiste jest, że samochody mogą zamienić swoją kolejność tylko wtedy, gdy ich łączna długość jest mniejsza lub równa szerokości parkingu. Zatem należy sprawdzić czy istnieje taka inwersja samochodów, że początkowo samochód A jest przed B, a potem odwrotnie, a oba te samochody są zbyt długie, by się wyminęły.

Ja to zrobiłem MergeSortem. W każdym kroku mając dwie podtablice posortowane (i sprawdzone, czy każdą z nich dało się poprawnie posortować), wystarczyło je połączyć w jedną, posortowaną. Nazwijmy lewą tablicę left[], a prawą right[], wreszcie tymczasową, dużą tablicę arr[].
Zgodnie z MergeSortem, wrzucamy do arr[] mniejszą z wartości left[i], right[j], gdzie i oraz j są ilościami już wrzuconych elementów z poszczególnych podtablic. W każdym momencie musimy jednak pamiętać maksymalny wrzucony element z tablicy right[], a w momencie wrzucania elementu z left[] porównujemy, czy długość wrzucanego samochodu jest poprawna, tj. czy max_right+długość_aktualnego_samochodu<=szerokość parkingu. Jeśli chociaż raz ten warunek jest fałszywy, zwracamy fałsz, w przeciwnym wypadku prawdę.
Złożoność jest taka, jak sortowania MergeSortem, czyli O(nlogn).
Nie wspomniałem o tym co prawda, ale oczywiście kryterium porównującym samochody jest ich końcowa pozycja: samochód A<samochód B wtedy i tylko wtedy, gdy samochód A ma być ustawiony na miejscu<od żądanego miejsca B.

zmień dostawcę internetu :)