663. Sort 1 [PP0506A]

Dziękuję za odpowiedź. Rozumiem że mój kod nie jest piękny stylistycznie ale jakby nie było liczył poprawnie. Błędu nie znalazłem ale zmieniłem sortowanie quicksortem na sort() i teraz program przechodzi. Dlaczego tak jest nie wiem. W każdym razie miałem zaimplementowany normalny algorytm quicksort, który dawał mi poprawne odpowiedzi przy wszystkich testach jakie znalazłem.

Jeżeli Twój kod nie dostał AC to znaczy, że jednak gdzieś jest błąd. Trudny do znalezienia, ale na pewno obecny. W gruncie rzeczy może być wszędzie - jak zauważył narbej, Twój kod jest strasznie zawiły i nie trudno w nim o pomyłkę dla jakiegoś dzikiego testu. Ja dostałem AC pisząc własne sortowanie bąbelkowe. Chyba wyczytałem na forum, że to wystarczy.

Ciekawostka! Raczkowałem wtedy w obiektówce i stworzyłem takie coś:

struct pkt {
public:
   string str;
   int x,y,o,i; 
};

Widzę tu w najlepszym przypadku lukier składniowy na literę p a w najpewniejszym dowód niewiedzy programisty

Mój kod daje błędną odpowiedź. Ja nie widzę błędu i moje testy działają. Może ktoś inny go wyłapie.
http://wklej.org/id/2781980/45

moje rady:

1) okulista
2) więcej testów, np.:

1
9
a 3 30
b 3 40
c 3 50
d 2 7
e 2 6
f 2 5
g 1 300
h 1 200 
i 1 100

3) jakiś rozsądny podręcznik z C++
4) w przyszłości przekazywanie kodu przez ideone.com
5) nie nadużywanie first i second bo czytelność kodu zerowa

Witam. Mógłby ktoś podać kilkanaście testów z poprawnymi wynikami?

a po co ci kilkanaście losowych testów ?
do znalezienia błędu z zasady wystarcza jeden test, dla którego masz błędne wyniki

jeżeli naprawdę chcesz testować swój program na losowych danych to sam sobie napisz generator, a na czas testowania uzupełnij testowany program o wyprowadzanie odległości punktu od środka układu współrzędnych - wtedy od razu widać, czy wyniki są poprawne

Znaczy nie wiem czy robię dobrze ... Chciałbym się upewnić za pomocą testów z poprawnymi wynikami. Losowe generowanie mi tutaj nie pomoże Testy podstawowe są zbyt proste.

Debugowanie to jedna z najbardziej żmudnych i najważniejszych części pracy nad dowolnym programem komputerowym. Nie tak dawno napisałem sobie Sokobana - skurczybyk zaczął pchać ścianę a potem stał się niewidzialny

Testy podstawowe (zakładam, że chodzi CI o przykładowe wejście i wyjście) są złe gdy nie są proste. Ich celem jest pomoc w zrozumieniu sensu zadania a nie dostarczenie materiału do testów. Powiem więcej - raczej rzadko ma się do czynienia z sytuacją, że testy przykładowe albo zbliżone do nich służą do oceniania poprawności i wydajności programu.

http://pl.spoj.com/problems/DAPPLES/28

Test przykładowy jest prosty. To zadanie wraz z rozwiązaniem i testami jest dostępne na stronie zasugerowanej na samym dole zadania w części "Pochodzenie". Jeżeli chcesz to poświęć przyjemnosć myślenia nad tym problemem i poszukaj testów a zobaczysz wręcz kosmiczne różnice między banałem zasugerowanym w przykładzie a tym, z czym program będzie się musiał zmierzyć. Wiele osób nie zdaje sobie sprawy z faktu, że testy są możliwie złośliwe i uwzględniają najmniej przychodzące do głowy przypadki.

Oczywiście nie musisz tworzyć aż tak rozbudowanych testów. Chyba, że masz czas na ich ręczne rozwiązywanie Niemniej jakieś testy warto mieć.

Po tej moralizatorskiej gadce wezmę pod uwagę fakt, że jesteś początkujący i podam Ci jakiś prosty wymyślony na szybko test
In:

2
1 
Camelidae 123 321
5
LAMA 0 0
Alpaczka 999 1000
gUaNaKo -1000 -1000
Wikunia 1000 -10
wigon -100 1000

Out:

Camelidae 123 321 
LAMA 0 0 
Wikunia 1000 -10 
wigon -100 1000 
Alpaczka 999 1000 
gUaNaKo -1000 -1000

Z C++ mam doświadczenie 2 lata. Stworzyłem silnik 2D i jestem w trakcie robienia gry. Wiem także, że debugowanie jest integralną częscią projektu do wykrywania błędów czasu działania(runtime errors). Także nie jestem takim początkującym, ale przede mną jeszcze długa droga

Co do testów. Wszystkie, które napisałeś program przechodzi. Na ideone dostaję błąd alokowania(std::bad_alloc) przez co program nie przechodzi na spoju. Chciałem się upewnić czy algorytm jest na pewno poprawny i teraz jestem w stanie powiedzieć, że tak. Nie mogę niestety znaleźć za pomocą debugera błędu. W Visual Studio 2015 program uruchamia się bez zarzutów. Zatem jestem zmuszony wkleić kod, który jest prawie AC

Kod tutaj: AC

Mógłbyś looknąć ?

PS.
Musiałem dodać do input'u znak nowej linii, bo takie jest wymóg w treści zadania.

Czy na pewno? Gdyby tak było, na spoju miałbyś błąd sigsegv czy coś podobnego, a przecież masz tam błędną odpowiedź.

Po prostu odległość od pkt (0 0) liczy się tak: odległość = sqrt(x*x + y*y)
można też użyć funkcji: hypot(x,y).

Do celów porównywania odległości, można zrezygnować z obliczania pierwiastka i porównywać kwadraty odległości. Natomiast to co Ty porównujesz, to ... właśnie, właściwie nie wiem i może tu leży pies pogrzebany?

to rozwiązanie miałoby by sens, jedynie w przypadku, gdyby autor inaczej zdefiniował odległość

sprawdź dla punktów (8, 1) i (5, 6)

Właśnie o tym napisałem tylko innymi słowami

Miałem na myśli znajomego z tak zwango reala (tak, posiadam takowych... a przynajmniej takowego )

Ja lubię jeszcze używać pair reprezentując grafy ważone.

Witam! Problem nad którym się głowie już trochę czasu według SPOJ-a przekraczam dozwolony obszar pamięci(SIGSEGV) . Ale kompletnie nie wiem kiedy. Tablice dynamiczne tworze na początku pętli ilości testów do wykonania a na jej końcu uwalniam obszar pamięci. Dla jednego testu program nie sypie się, natomiast na 2 już tak, sortuje, wypisuje prawidłowo ale jak by miał problem z uwalnianiem pamięci i nie rozumiem tego CRASHA. Prosze o pomoc. Oto moj kod http://ideone.com/yAIlHV15.

porównaj wyniki dla takich dwóch testów, może wyciągniesz właściwy wniosek

pierwszy test

2
2
A 1 1
B 0 0
2
A 1 1
B 0 0

oraz drugi test

3
2
A 1 1
B 0 0
2
A 1 1
B 0 0
1
X 0 0