MWP3_1B1 - Dlaczego rozwiązanie błędne?

wątpię, by ktokolwiek sprawdził poprawność twojego programu - strasznie długi i zagmatwany

mam natomiast uwagi:

1) używanie typów rzeczywistych, gdy dane są całkowite to proszenie się o kłopoty (to moja stała uwaga)

w szczególności porównanie (a / b) * (c / d) == -1 może dać inny wynik niż a * c == - b * d
bo np. (a / b) * (c /d) może być równe -0.99999999999999999

także sprawdzanie czy kąt pomiędzy odcinkami == 90 poprzez atan2() jest wątpliwe

efektem tych dwóch powyższych, może być nierozpoznanie układu dwóch bierek jako L, a następnie rozpoznanie jako V

2) funkcje L i V powinny być bardziej do siebie podobne - różnia się przecież tylko kątem pomiędzy bierkami

Odpisuję po latach. Mój program, który dostał AC ma inną wartość dla testu numer 8 (V zamiast -). Oraz inny iloczyn, ale raczej mój jest poprawny (więcej zer na końcu, a w iloczynie występuje wiele dziesiątek i pięćdziesiątek).

Coby kiedyś nie zniknęło z ideone wklejam testy:

input.txt53 (9.6 KB)
output.txt38 (1.5 KB)

Niby że co!? Jak twoje wklejenie może zapobiec czemukolwiek? Jak zniknie forum to razem z twoim wklejeniem. I co discuss ma wspólnego z ideone.com oraz pl.spoj.com?

W pierwszej linii wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 10) określająca ilość par bierek.

Wiec tamten test jest raczej błędny i jest bezznaczenia, jaki jest iloraz oraz pewnie w takim razie wynik dla 8 zestawu.

Nie pojmuję o czym piszesz, nic nie pisałem o zniknięciu forum. Napisałem, żę jeżeli zniknie z ideone, padnie ideone, albo autor tematu usunie swój link do ideone to wklejam po to testy by były na forum.

Wiec tamten test jest raczej błędny i jest bezznaczenia, jaki jest iloraz oraz pewnie w takim razie wynik dla 8 zestawu.

Rozumiem, że w zadaniu będzie (1 ≤ N ≤ 10), ale dlaczego z tego powodu wynik dla 8 zestawu miałby być bez znaczenia? I jaki iloraz w ogóle?

Nie ogarniam o czym piszesz. Niemniej... chciałem by testy były dostępne na forum to je wkleiłem. Napisz co zrobiłem źle, bo nie wiem... czy ja czegoś oczywistego nie dostrzegam?

Ja też nie zrozumiałem o czym pisałeś. Przeczytałem tylko twój post, a nie zwróciłem w ogóle uwagi na wcześniejsze [i na umieszczone tam linki do ideone]. Teraz zrozumiałem

Mimo to, iloraz w tamtym teście [błędnym] a więc i twoim, jest bez znaczenia, bo, jeśli się nie mylę max =:
10*{L} = L*L*L.... = 50**10 = 97656250000000000

Co do zestawu bierek nr 8, to w takim razie ok [teraz wiem do czego się odniosłeś] - ale ocxzywiście nie sprawdzam tego - wierzę Ci na słowo.

Na pewno chodzi Ci o iloraz?

Oczywiście że tak

Oczywiście, że tak, masz rację, ale nie wymagaj za dużo odemnie, o tak wczesnej porze

PS
Chociarz, rzeczywiście, iloraz jest zupełnie bez znaczenia, jaki tam on by niebył

PS 2
Co do znikającedgo forum, to odniosłem się do wątku: http://discuss.spoj.com/t/old-spoj-forum/12301

tu był kod

AC

Test:

2
-6972 -1134 2372 3381
8640 3272 708 4918
-4378 6434 5139 -1959
171 -8850 -3760 -3614

Mój out:

-
-
1

Twój out:

X
X
100

Dzięki Ci bardzo! Wystarczyło zmienić int na long long int

Polecam poczytać o iloczynie wektorowym 2D: http://www.algorytm.edu.pl/olimpiada-informatyczna/iloczyn-wektorowy.html15

Niepotrzebnie. Wszelkie problemy i zadania można rozwiązać na wiele sposobów i chociaż jedne sposoby będą lepsze a inne trochę gorsze, to najważniejsze, abyś rozwiązał czy dążył do tego swoim własnym sposobem. A ocena co jest lepsze jest czasami subiektrywna. W komentarzu, na który się powołujesz, @mariusz193 zaleca, do tego zadania, używanie zmiennych całkowitych. I to jest słuszne, ale jeżeli zrobiłeś inaczej i uzyskałeś AC, to też jest super, chociaż zmienne całkowite, są po prostu szybsze i często wystarczają do rozwiązania wielu problemów [zadań].
Porównaj np mój komentarz do zadania: FR_12_18 - Liczba monet

Z kilku komentarzy powyżej twojego pytania, wynika, że np r_inf to uzyskał, więc równie dobrze, twoje pytanie możnaby odwrócić, czy naprawdę ktoś rozwiązał to zadanie nie używając zmiennych całkowitych? [wiem, tak Ty ]

@quenthui, podał link, ale możliwe, że początkujący nie bardzo potrafi z niego w pełni wykorzystać.

Więc np tak:

1. IF Sprawdzamy czy bierki mogą utworzyć cyfrę L lub V, a więc najpierw, czy istnieje co najmniej jeden wspólny punkt. Jeżeli tak, to sprawdzamy jaki bierki tworzą kąt, korzystając np z iloczynu wektorowego. Jeżeli były dwa wspólne punkty - to jaki kąt?
2. ELSE IF Jeżeli w pkt 1. stwierdzimy, że nie ma żadnych wspólnych pktów, a więc ani L ani V, to może bierki tworzą cyfrę X?
   Jak to srawdzić? Korzystając z opisu iloczynu wektorowego i odręcznego rysunku. Jeżli punkty drugiej bierki leżą po przeciwnych stronach pierwszej [jedna na lewo, a druga na prawo] oraz punkty pierwszej bierki też leżą na po przeciwnych stronach bierki drugiej, to tworzą one cyfrę X. W sumie aby to stwierdzić, wykonujemy max cztery iloczyny wektorowe, prawda?
3. ELSE, bierki nie stworzyły żadnej cyfry.

Nie wiem czy to było konkretnie do mnie czy bardziej do ogółu, ale pozwolę sobie skomentować

Blockquote Niepotrzebnie. Wszelkie problemy i zadania można rozwiązać na wiele sposobów i chociaż jedne sposoby będą lepsze a inne trochę gorsze, to najważniejsze, abyś rozwiązał czy dążył do tego swoim własnym sposobem.

Nie wiem czy się zgodzę z Tobą Ja na przykład się mega podjarałem jak zobaczyłem ten “trik” z iloczynem wektorowym. Szansa że sam bym na to wpadł nie była duża, a wolę się rozwijać poznając nowe rzeczy (bez względu na to czy kiedykolwiek użyje tego gdzieś poza Spojem :D) niż rozwiązując kilkadziesiąt kolejnych zadań często “przepałowanych” tylko dla uzyskania AC. Ja rozumiem że radzenie sobie samemu z problemami, ćwiczenie cierpliwości itd też ma swoje plusy, ale czasem chyba można poprosić o pomoc żeby ruszyć dalej (dobra może ja czasem za często proszę )
(Tak na marginesie rozwiązałem to zadanko po przeczytaniu tego linku )

Trik to pojęcie względne. Akurat w przypadku omawianego tricku związanego z iloczynem wektorowym, jest on tak znany i tak prosty w użyciu (przynajmniej w 2D), że uznaje się go za wiedzę dość elementarną. Rozwiązywanie zadań robionych pod tę sztuczkę bez jej znajomości mija się z celem.

Proszenie o pomoc nie jest problemem. Ba - jest wskazane. Choć spotkałem się pośród starszych speców od AjTi z takim podejściem do projektu:

1. możesz zadać pierwsze pytanie bo niczego nie wiesz,
2. możesz zadać drugie pytanie bo złożona odpowiedź, którą udzielono Ci za pierwszym razem musi zostać przetrawiona,
3. jak pytasz po raz trzeci to nie ma sensu Ci odpowiadać bo zapytasz po raz czwarty

Zadania łatwe są w dużej mierze do “przepałowania”. Od średnich robi się bardziej wesoło. Tak w zasadzie zadania łatwe, jak już ogarniasz kodowanie, wymagają wyłącznie cierpliwości i chęci.

Na koniec kilka innych tricków, które przychodzą mi do głowy, a na których ludzie często wypieprzają się na SPOJu

1. Robienie czegoś samemu, następnie kopiowanie i wklejanie do kolejnych zadań. Dotyczy to zwłaszcza funkcji sortujących albo różnych innych, de facto bibliotecznych rozwiązań. Jeżeli masz taką możliwość + chęć nauki to ok - zrób raz własnego sorta, pobaw się, ale przechodząc do kolejnych zadań korzystaj z możliwości języka a nie twórz własny.
2. Eliminacja Gaussa dla układów równań liniowych. To klasyka, a ludzie często nie wiedzą jak zabrać się za układ równań i kombinują jak koń pod górę.
3. Problem plecakowy i wydawanie reszty. To akurat na tyle kultowe, że fajnie o tym wiedzieć coś więcej i nie walić zachłannymi algorytmami bez sensu.
4. Flood fill. W zasadzie pierwsza myśl gdy jesteś na środku szachownicy (tablicy) zwłaszcza z “bajerami” typu ściany (labirynt). Proste w implementacji, nie wymaga wiedzy o grafach/BFS bo zwyczajnie “to widać”. Ewentualnie można sobie pograć w Sapera.
5. brak wiedzy o źródłach takich jak np. oeis.org4 . Często masz “wizję”, po godzinie widzisz pięć kolejnych liczb w jakimś dzikim ciągu i czujesz, że to się da jakoś prosto wygenerować, ale nie wiesz jak ani czy Twoja intuicja jest dobra. To dobre miejsce do jej zweryfikowania.
6. Jest sobie jakiś punkt na płaszczyźnie w metryce Manhattan. Masz też dość skomplikowany układ poziomych i pionowych kresek wyznaczających coś typu ściany budynków. Pytanie brzmi czy punkt jest wewnątrz jakiegoś budynku. Problem kultowy choć mniej niż iloczyn wektorowy, ale również prosty.
7. Fajnie umieć zapisać graf do tablicy i po nim przejść. Wysiłek niewielki, żadnych cudów ogarniać nie musisz, ale już dostajesz niewielkim wysiłkiem (mało nauki) świetne narzędzie do trzaskania nieraz złożonych problemów. Może i niewydajnie, ale już poprawnie. Po dodaniu iluś tricków, o które mniejsza, grafy pozwalają rozwalić niemalże wszystko. Ba - często widzisz, że dany problem jest grafowy, choć może nie widzisz finalnego algorytmu.

Mistrzostwo niestety żadnego z wymienionych nie znałem … więc albo to jest klasyka tylko dla informatyków a nie koniecznie dla osób z innym wykształceniem albo ja zmarnowałem sporą część swojego życia Więc jakbyś kiedyś przypomniał sobie coś jeszcze i zechcesz dopisać to będę wdzięczny Plus macie jakieś książki z których można się takie rzeczy dowiedzieć ? Ja znalazłem przy innym poście jedną “wprowadzenie do algorytmów” , będzie dobra “na start” czy coś innego polecacie ?
P.S Ok jednak eliminacje Gaussa się uczyłem ale pamięć zawodna

Z książkami jest ciężko. Ja zawsze polecam te wykłady: https://www.youtube.com/channel/UCUUbh9zSmNy8RD4LJRiHGFQ11. Nagrania są w słabej jakości, ale kontent pierwsza klasa.

Jest jeszcze ten kanał: https://www.youtube.com/channel/UC3iG4wr8CiCAGvKF_-e4Jrg9, gdzie są wykłady z algorytmiki i opis rozwiązań różnych zadań (nie ze spoja). Zawsze można podpatrzeć jakieś rozwiązania.