Emocjonująca rozgrywka w węża MWP3_3E

bzdura

bzdura

bzdura

Niby racja, ale nie do końca. warto też wiedzieć, że na starym forum jest długi wątek o tym zadaniu [aż 53 posty na czterech stronach - malutkie kadraciki z cyferkami, po prawej stronie, na samym początku i na końcu strony <-- klikać].

Tylko trzy? Bardzo zdrowe podejście. Brawo!

bzdura

Wczoraj spróbowałem to zrobić, program alokuje, nie ma nic globalnego, jedna ładna funkcja, wektory, pary, wprawdzie 0.07, ale jest. Jeśli chodzi o wymagania czasowe to nie zgodzę się z narbejem. Przy takich zadaniach powinno być napisane "da się wykonać w języku C i jego nadzbiorach". Nikt nie zrobił tego zadania w językach innych niż C/C++ (jedno pascal z czasem 0.25). Poza tym zadanie "emocjonujące"

Edit: jeszcze trochę zmian i jest 0.05

Nie potrzeba uzasadniać powodu założenia wątku, ale jeśli ktoś chce, to warto to robić z większym sensem

Tak na marginesie, oba posty wyżej dostały po jednym Like [sorry więcej nie mogłem ].

To że nie ma rozwiązań w innych językach świadczy tylko, że nikt nie rozwiązał tego zadania w innym języku programowania, ale autor nie może i nie musi wiedzieć czy istnieje taka możliwość czy nie, więc nie może napisać:

Miało tam być "tylko" ?, bo jeżeli nie, to przecież jeżeli jest inaczej [np także z innych powodów], to w metryce zadania jest linijka: dostępne języki. Jeżeli jest tam all, to raczej napewno można w c/c++ ale nie oznacza, że w każdym innym też się da.

Więc jeżeli autor wątku pisze, że mimo absurdalnego limitu i straconego czasu, jednak udało mu się jakoś zaliczyć [w c99] to zadanie i jeszcze dostać przy okazji na pierwszą stronę rankingu, to czy to nie jest jakaś kompletna bzdura?
I czy nie lepiej, zamiast tracić, poświęcić odrobinę czasu na oglądanie telewizji lub spacer czy naukę np języka chińskiego?

@filystyn mógłby stwierdzić, że właśnie o to mu chodziło i że czepiam się słówek. Tak czepiam się, ale programowanie polega na pewnej ścisłości i dokładności, więc tu też powinniśmy, bo w przeciwnym wypadku, ktoś może skwitować wypowiedź jednym krótkim: to jakaś bzdura.

PS
Mam/miałem 3 powody używania zmiennych globalnych. Teraz mam tylko 2, ale i tak staram się tego nie robić i używać tylko zmiennych lokalnych.

PS 2
limit 0.1 jest na pojedyńczy test, więc uzyskany czas rozwiązania zadania, po zsumowaniu wynikw wszystkich testów, może wynieść np 0.38

PS 3
Wynik 0.04 w tym zadaniu to było za mało, aby utrzymać się dłużej na 1 stronie rankingu dla tego zadania, bardzo mi przykro .

PS 4
W miarę wolnego czasu i zainteresowania, z przyjemnością wyjaśnię moje stanowisko w innych aspektach postu @filystyn'a , tam gdzie napisałem bzdura.

bzdura

bzdura

bzdura

Ciekawy jestem [ale nie tak bardzo], kiedy zaczniesz się pytać, zamiast wypisywać bzdury?

Nic nie ma za darmo i za free, a malutkie kłamstewka mają krótkie i malutkie nóżeczki.

PS
Jeżeli nie chce Ci się zerować tablicy w pętli, to może sobie potestuj, albo poczytaj o takiej konstrukcji:

int main () {
      int tab[100000] = {0};  // czy to jest za darmo, półdarmo,  czy nie?

Jeżeli chcesz zachwalać zmienne globalne, to może najpierw poczytaj o zaletach i wadach zmiennych globalnych i lokalnych w jakiejś porządnej książce.

Miało tam być "tylko" ?, bo jeżeli nie, to przecież jeżeli jest inaczej [np także z innych powodów], to w metryce zadania jest linijka: dostępne języki.

Pogubiłem się w tym zdaniu, ale wyjaśniam o co mi chodziło, a chodziło o to, że ten sam program napisany identycznie (co do algorytmu) w różnych językach ma inny czas wykonania, a czas na zadanie nie jest per język. To też C/C++ często są wiodące. Na przykład pomimo usilnych prób nie znalazłem tak szybkiego inputu i outputu w Pythonie (a próbowałem bibliotek typu "os" czy "sys" i znacznie szybszych sposobów niż standardowe "print") jak w C++ "cout" i "cin" przy wykorzystaniu znanych "sztuczek". Nie obwiniam tutaj niczego ani nikogo, a na pewno nie autora zadania, który przecież nie ma obowiązku domyślania się czasów w innych językach. Ot tak stwierdziłem znaną prawdę, że są języki o różnym czasie przetworzenia tego samego algorytmu i instrukcji de facto wykonujących to samo (pewnie zależy to od jakości kompilatora, np. PyPy daje kopa względem samego CPython, a obsługują ten sam język).

Zaznaczam, że mogłem coś pomylić, rano jest, a w pracy nie mam zlecenia to sobie piszę.

Ponieważ powyższa dyskusja nijak nie podpowiada w rozwiązaniu, a archiwum spoj nie chce mi się otworzyć http://213.192.104.217/phpBB3-spoj-pl-backup/viewtopic.php?f=1&t=1803&start=3019 odświeżam temat.
Zadanie zrobiłem i na tablicach i na LIST i kombinowałem już z różnymi typami zmiennych i zawsze mam przekroczono limit czasu:
http://ideone.com/tyGKpN23
Ostatni pomysł to nie czyszczenie listy w pętli tylko komendą lista.clear(); ale to też nie przyspieszyło programu dostatecznie.
Brakuje mi już kolejnych pomysłów jak przyspieszyć mój program.
Poproszę o podpowiedź, bądź działający link do archiwum starego forum z dyskusją o podobnym problemie z tym zadaniem.

Trochę przyspieszeń jakie udało mi się wykonać:
http://ideone.com/5XXj5029

Teraz masz błędną odpowiedź na teście na którym dotąd nie dochodziłeś. Nie jestem pewny czy dlatego, że od początku miałeś źle czy dlatego, że ja skracając Twój kod czegoś nie pojąłem (a jest czego nie pojąć: jem, leb, zyje, kaput, umarlem, bede_Zyl).

check i waz to 2 zmienne ktorym przypisuje wartosc przed i po usunieciu pozycji zmiennej leb czyli punktu gdzie waz aktualnie sie przemiescil.
Jesli check i waz beda rozne o 1 to znaczy ze waz ugryzl sie w ogon i zmienna kaput oznacza poprostu koniec gry.
Zmienna jem informuje program czy usunac ostatni element z listy ( waz sie odsuwa z ostatniej pozycji czy nie ) czy powiekszyc o niego weza.
wspolrzedne weza zamiast X=0, y=0 zapisalem w jednej cyfrze 100000100000 itd. zeby miec jedna liste tylko.
Poza tym robiles zapisy ktorych nie uzywalem nigdy, badz nie rozumiem ich dzialania,
for(char rozkaz : data) - petla bez średnikow z dwukropkiem i na char? myslalem ze na kursie dowiedzialem sie o wszystkich petlach FOR a tu niespodzianka??
kolejne:
czy uzywanie '\n'; zamiast endl; przyspiesza program?
i ostatnie:
cin>>n;
while (n--) to tez cos nowego ale akurat zrozumiale i pomyslowe - zaczne stosowac...
czy masz jeszcze jakies pytania o dzialanie programu, bo mimo ze probojesz to nadal po tym co napisales nie potrafie skonczyc programu

Nowość od standardu z 2011 roku. Mało kto zna, a unikasz jednej zmiennej:
http://en.cppreference.com/w/cpp/language/range-for14

Podobnie unikam dodatkowej jednej zmiennej przy pomocy while(n--). Oczywiście nie zawsze się da.

Tak, omijasz bufor:

czy masz jeszcze jakies pytania o dzialanie programu, bo mimo ze
probojesz to nadal po tym co napisales nie potrafie skonczyc programu

Ominąłem Ci też zmienną jem odpowiednio spreparowanym ifem. Dalej nie wiem co jest źle i nie dałem rady nic wymyślić. Zastanawiam się czy na pewno druga cyfra 1 w ciągu 100000100000 w końcu nie naskoczy na pierwszą (czy tam odwrotnie), ale to tylko przypuszczenia (osobiście zrobiłem to na std::pair czyli x=0 y=0 właśnie).

A jeśli chodzi o Twoje zmienne... polecam Ci książkę Czysty kod6. Po niej (przerobieniu, a nie pobieżnym przeczytaniu) pisze się o wiele lepszy kod. Np. nie używa się zmiennych raz angielskich raz polskich (już nie mówiąc o mieszaniu dwóch języków w jednej zmiennej ktoradead).

Tak więc moja podpowiedź by wykonać to zadanie spróbuj rozbić jednak współrzędne.

ja bym sugerował rezygnację z list - są kosztowne w obsłudze - zwykłe tablice (dokładnie 2 ) użyte we właściwy sposób rozwiązują problem z przekroczeniem czasu.

Moje rozwiązanie nie korzysta z cin, ani nawet scanf, a z fast I/O. To nie zaszkodzi poprawić, choć może zrobiłem to tylko po to by wyśrubować czas... nie pamiętam.

Moje rozwiązanie nie korzysta z getline. Chyba gdzieś na starym forum wyczytałem, że getline nie przejdzie. Jednak znowu - memoria fragilis est.

W moim kodzie wykonuję ify dla każdej litery, a w nich ifuję dokładnie cztery możliwe przypadki. Za każdym razem wykonuję stosunkowo proste operacje, które nie kosztują wiele czasu.

Jeżeli dobrze rozumiem patrząc na szybko na kod, pod sam koniec jeszcze jeden if w rodzaju "czy właśnie się zjadłem". W tym momencie przerywam przetwarzanie danych - podaję odpowiedź oraz czym prędzej wczytuję i zapominam pozostałe znaki, które już nie będą miały znaczenia.

Bardziej chyba nie jestem w stanie Ci pomóc...

Chodzi Ci o to:
http://www.algorytm.edu.pl/fast-i-o.html10 ?
to niestety mam to:
"Powyższe funkcje zadeklarowane są w bibliotece cstdio ale mogą być niezdefiniowane w niektórych kompilatorach, np. w Def C++." a korzystam z Code Blocks
A co do pomocy to pomogłeś tym zdaniem:
"W moim kodzie wykonuję ify dla każdej litery, a w nich ifuję dokładnie
cztery możliwe przypadki. Za każdym razem wykonuję stosunkowo proste
operacje, które nie kosztują wiele czasu."
Mam już pomysł i jutro spróbuję wykonać.....

Fast IO obejmuje ogół metod związanych z szybkim wczytywaniem i wypisywaniem danych. Jest to istotne właściwie wyłącznie na potrzeby konkursów i zadań algorytmicznych, choć porządne zadania są na ogół "zabezpieczone" przed takimi "chwytami" odpowiednio dobranymi testami i limitami czasu. Szczęśliwie zabezpieczenia są po to aby je łamać i np. wiedząc, że bardzo trudnym jest rozróżnienie rozwiązania zadania konkursowego działającego w O(n) od działającego w O(nlogn), a także mając świadomość, iż metody fast IO mogą nawet sprawić, że rozwiązanie o gorszej złożoności uzyska czasy lepsze niż rozwiązanie o lepszej złożoności, można "obejść" sędziego.

Opisaną sytuację wymyśliłem samemu, ale jestem prawie pewny, że bardziej praktyczny opis stworzył Stańczyk ("algorytmika Stańczyk" i znajdziesz), który podał swoje metody fast IO, a także napisał jak przy ich użyciu podołał zadaniu, które powinno być rozwiązane w O(n), a on umiał je zrobić jedynie w O(nlogn) i nic lepszego do końca konkursu nie przyszłoby mu do głowy.

Dla mnie to nie jest problem - wystarczy przejść na g++, a przy okazji rozwijać swoją wiedzę o systemach operacyjnych przechodząc na coś lepszego niż Windows Inna sprawa, że jak wynika z mojego wcześniejszego postu, fast IO obejmuje także inne rozwiązania. Sam uważam, że metody podane we wstawionym przez Ciebie linku są na prawdę świetne, ale jednak używam ich zmodyfikowanej, wg mnie lepszej wersji.

Cieszę się, jeżeli uważasz, że Ci pomogłem. Drugie zdanie jest jednak kluczowe jeżeli chodzi o ewentualne AC. Poza tym mój kod to nie tylko ify, co również zaznaczyłem. No ale wymyślenie jak rozwiązać problem to już zadanie dla Ciebie

Udało się, mój wąż w końcu zmieścił się w limicie czasu, punkt dla tarpauwatratar za najlepszą podpowiedź.
Na zamknięcie tematu dodam że zadanie wymaga bardzo abstrakcyjnego myślenia do napisania pomysłowego rozwiązania.
Robiłem już o wiele łatwiejsze zadania w kategorii średnie niż to w kategorii łatwe.