[c++]potrzebny "nauczyciel" ;D

[errorplus 22]

Witam, tak jak w temacie potrzebuję kogoś kto pomógł by mi i wyjaśnił pewien problem w zadaniu.

Mam do napisania taki oto program: http://oi.edu.pl/old/php/show.php?ac=p870600&module=show&file=zadania/oi12/lot

 

tylko jest mały problem w tym, że za ch**iny ludowe nie mogę dojść do tego jaki warunek ustalić w pętli, która "porównywała" by wartości.

 

Dane pobieram do jednej tablicy dwuwymiarowej takim oto sposobem:

 

 

int n;
cin>>n;
int plan[n][n];

   for(int i=0; i<n; i++){
      cin>>plan[i][i]; 
   }
 

No i problem tkwi w tym, iż nie wiem jak zrobić aby program "porównywał" wartości w kolejnych przebiegach pętli.

1 przebieg - "porównanie"  1do2, 2do3, 3do4, 4do5, 5do1

2 przebieg - "porównanie"  2do3, 3do4, 4do5, 5do1, 1do2

3 przebieg - "porównanie"  3do4, 4do5, 5do1, 1do2, 2do3, 

4 przebieg - "porównanie"  4do5, 5do1, 1do2, 2do3, 3do4 

5 przebieg - "porównanie"  5do1, 1do2, 2do3, 3do4, 4do5

(napisałem na podstawie przykładu podanego w zadaniu).

 

 

pisze słowo "porównanie" w cudzysłowach, bo wiadome, że nie jest to dosłowne porównanie, chodzi o te przejścia między adresami w pętlach (bo myślałem o zagnieżdżeniu ) a wewnątrz nich oczywiście stosowne warunki itp.

 

Nie wiem czy dokładnie wyjaśniłem o co mi chodzi, ale dokładnie nie wiem jak to opisać

Jeżeli ktoś zrozumie o co mi chodzi i byłby w stanie mi pomóc to strasznie byłbym wdzięczny. Nie wiem też czy aby na pewno wybrałem dobrą metodę rozwiązania tego problemu, ale z wiedzą, którą przekazują nam w szkole nie potrafię do tego podejść inaczej dlatego może ktoś wskaże inną drogę rozwiązania tego problemu

 

 

[szatkus 282]

 

No i problem tkwi w tym, iż nie wiem jak zrobić aby program "porównywał" wartości w kolejnych przebiegach pętli. 1 przebieg - "porównanie"  1do2, 2do3, 3do4, 4do5, 5do1 2 przebieg - "porównanie"  2do3, 3do4, 4do5, 5do1, 1do2 3 przebieg - "porównanie"  3do4, 4do5, 5do1, 1do2, 2do3,  4 przebieg - "porównanie"  4do5, 5do1, 1do2, 2do3, 3do4  5 przebieg - "porównanie"  5do1, 1do2, 2do3, 3do4, 4do5 (napisałem na podstawie przykładu podanego w zadaniu).

Pomyśl nad innym sposobem, bo ten nie zmieści się w czasie. 

[slawek1990 6]

Napisz do mnie na PW, może coś wymyślimy

[kropka89 16]

"W czasie podróży Bajtazar musi poruszać się po okręgu, stale w wybranym jednym z dwóch kierunków." - przez to zdanie rozumiem że powinno być 10 przebiegów a nie 5

 

Co do rozwiązania to zrób sobie pętle while a w niej odliczaj 5 kroków a i osobno licz index tablicy. Jeśli index == N-1, ustaw N na 0

Albo zrób sobie struktury/klasy i wskaźnikami sobie podróżuj po stacjach. Najwygodniejszy sposób.

[Gość Szczawson]

Co do rozwiązania to zrób sobie pętle while a w niej odliczaj 5 kroków a i osobno licz index tablicy. Jeśli index == N-1, ustaw N na 0 Albo zrób sobie struktury/klasy i wskaźnikami sobie podróżuj po stacjach. Najwygodniejszy sposób.

 

 

A co do zadania ... uwazam ze jest banalne jak na olimpiade z programowania. Jesli nic nie potrafisz wymyslic to tym lepiej dla Ciebie - masz wyzwanie i zadanie. Jak stworzysz jakis kod co robi cokolwiek to moge CI podpowiedziec. NIestety nie zrobiles jeszcze nic wiec nie mozemy CI pomoc. Sorki w koncu to olimpiada

Edytowane 6 Kwietnia 2013 przez Szczawson

[errorplus 22]

Nie jest to zadanie na olimpiadę ani na żaden konkurs tylko jest to zadanie archiwalne i robię je jak napisałem do szkoły. Ale niestety w szkole za dużo nas nie uczą, wręcz można powiedzieć, że większość co umiem to samemu się dowiedziałem. 30 zadań z treningu zrobiłem i zostałem poproszony o zmierzenie się z którymś zadaniem archiwalnym z II etapu olimpiady.

 

I oczywiście nie oczekiwałem gotowego całego kodu, także luzik tam u góry ;P Miałem pomysł na to zadanie (tak jak opisałem w pierwszym poście), a że nie wiedziałem czy jest dobry i jak do końca go zrealizować to zwróciłem się dlatego na forum .

Edytowane 6 Kwietnia 2013 przez errorplus

[Malwin 16]

Dlaczego c++, w treści zadania nie ma narzuconego języka albo już niedowidzę

Edytowane 6 Kwietnia 2013 przez Malwin

[errorplus 22]

Dlatego, iż jest to język który jest w programie nauczania mojej szkoły. I robię to do strony main.edu.pl

[szatkus 282]

Rano zrobiłem działającą (100/100) implementację, więc mogę teraz coś więcej napisać.

Tak jak pisałem sprawdzenie wszystkich możliwych podróży nie zmieści się w czasie (moje to O(nlogn)). Musisz to zrobić sprytniej, dobierać punkty startowe w odpowiedniej kolejności i opierać się na wcześniejszych wynikach, żeby nie musieć za każdym razem iterować po całym okręgu.

 

Powodzenia

[errorplus 22]

Coś takiego też przyszło mi do głowy, ale pomyślałem sobie, że może być to za cięższa opcja dla mnie niż sprawdzenie wszystkiego Ale co tam, nie ma rzeczy niemożliwych, przysiądę dzisiaj i pomyślę troszkę nad tym  

Dzięki

[Malwin 16]

 

Rano zrobiłem działającą (100/100) implementację, więc mogę teraz coś więcej napisać.

Tak jak pisałem sprawdzenie wszystkich możliwych podróży nie zmieści się w czasie (moje to O(nlogn)). Musisz to zrobić sprytniej, dobierać punkty startowe w odpowiedniej kolejności i opierać się na wcześniejszych wynikach, żeby nie musieć za każdym razem iterować po całym okręgu.

 

Powodzenia

 

 

Tylko po co optymalizować jak nie ma o tym mowy w zadaniu, chyba że umyka mi ten fragment

[errorplus 22]

zadanie musi być zaakceptowane tutaj. main.edu.pl/pl/archive/oi/12/lot pamięć jest ograniczona do 32mb

[szatkus 282]

Pamięć nie ma tu nic do rzeczy. Po prostu sprawdzanie wszystkich możliwości dałoby złożoność O(n^2), co dla testów, gdzie n = 1000000, da baaardzo dużo powtórzeń. Podejrzewam, że czas wykonania byłby liczony w minutach, a przypominam, że limit czasowy to 1 sekunda

[errorplus 22]

Nie ma co się rozrczulać trzeba brać się za myślenie i pisanie

[Alfons 30]

Popatrz na sortowanie bąbelkową

[Malwin 16]

OK. Na tej drugiej stronie faktycznie limit 32MB, co jednak nie stanowi problemu bo jest to badzo dużo pamięci. Dużo obliczeń i porównań można robić na tych samych danych i w miejscu. Ale dalej nie widzę ogarniczenia czasowego, więc nie wiem skąd niektórzy wytrzasneli czas 1s. Pomijając, przypadek dla maksymalnego n = 1 000 000 i gdzie dla każdej stacji by sie dało zrobić kółko bo jest więcej paliwa niż wymaga droga to na zwykłym komputerze jest to niemożliwe

[szatkus 282]

Ta jedna sekudna mi się uroiła, bo to w takich zadaniach jest najczęstszy limit i nawet nie zwróciłem uwagi, że nie jest nigdzie podany. Po spojrzeniu w raport zgłoszenia, okazuje się, że limit dla dużych testów to aż 3 sekundy

A jeśli chodzi o rozpatrywanie największego przypadku brutem to wedle moich zgrubnych obliczeń na przeciętnym kompie zajęłoby to jakieś kilka godzin, więc nie tak znowu niemożliwe  Ale na pewno więcej niż zajęło mi wymyślenie i napisanie bardziej efektywnego algorytmu.

Edytowane 7 Kwietnia 2013 przez szatkus

[Malwin 16]

Niemożliwe odnosiło się do 1 sekundy, a nie do otrzymania wyników w rozsądnym czasie. Co nie zmienia faktu, żeby działało w 3 sekundy dla pesymistycznych danych też się nie da. Dodatkowo takie ograniczenie czasowe jest lekko bez sensu, pomijając już wartość czy to 3s czy 300s, bo dla różnych komputerów jest wartości mogą sie znacznie różnić.

[szatkus 282]

A to ciekawe, bo moje rozwiązanie jak i rozwiązania 163 innych osób dały radę zmieścić się w 3 sekundach dla 1 mln stacji. Dokładnie to 0.68 sekundy, u mnie na laptopie trochę gorzej, 0.75s, ale to tylko Brazos

[Malwin 16]

Dobra przetestowałem i przyznaje w 3s da się zmieścić. Problemem było zmieszczenie się w 1s. gcc bez dodatkowych opcji optymalizacji 1.27s, z -O2 0.49s na ARM1176JZF-S 850MHz. Na lapku nie testowałem, bo nie mam gcc w tym momencie

[kropka89 16]

Popatrz na sortowanie bąbelkową

a jak chcesz tutaj podpiąć sortowanie jeśli kolejne punkty są od siebie zależne?

[darasz89 190]

używanie tablic w problemie zakładającym cykliczność podczas przeszukiwania danych jest strzałem w stopę - w pewnym momencie należy rozwiązać problem indeksowania offsetowego [np. gdy zaczynamy od stacji 3: 3 -> 4 -> 5 -> 1 -> 2 -> 3], co tylko niepotrzebnie komplikuje sytuację

 

w związku z powyższym najlepiej zaimplementować listę cykliczną, można to zrobić na 2 sposoby: albo używając tablicy danych, albo wskaźników

z tablicą jest prościej, wystarczy stworzyć strukturę zawierającą 2 pola: wartość i indeks_nastepnego, podczas wczytania ostatniego elementu indeks_nastepnego = 0; dzięki temu można szybko i bez problemów przeszukiwać cały zbiór danych bez potrzeby martwienia się o wartości indeksów

 

także powodzenia

Edytowane 8 Kwietnia 2013 przez darasz89

[errorplus 22]

Zrobiłem na 80pkt , nie przechodzi mi w całości testu 1a i 4. Posiedzę nad tym jeszcze trochę, a jeżeli nie dojdę to może ktoś z was będzie miał pomysł na ten problem

[Alfons 30]

U mnie na PC kiedyś jeden skrypt 0.20 sekundy na lapku 0.8 sekundy a na konkursie na niby lepszym procku tylko 4 sekundy ...

[waszak 4]

Stare to zadanie kiedyś, to 80 to mogło być nawet i 60 pktów. Zadanie nie jest trudne, ale musisz sobie wypisać fakty związane z ilością paliwa i drogami. Podpowiem, że rozwiązaniem jest algorytm zachłanny. I pierwszym oczywistym w nim faktem jest, ze jeśli sumaryczna ilość paliwa < sumarycznej długości dróg, to opowiedź jest nie. Inne fakty, są już ciut trudniejsze i dotyczą zależności pomiędzy stacjami a i b.