Cześć. Mam problem z zadaniem "Sumy i różnice" z ILOCAMP 2011 (grupa początkująca, dzień 1). Jego treść znajduje się na tej stronie http://main.edu.pl/pl/archive/ilocamp/2011/sir
Mój problem polega na tym, iż nie mam pojęcia jak rozwiązać te zadanie. Bardzo was proszę o jakiekolwiek podpowiedzi lub coś co nakierowałoby mnie na rozwiązanie.
wpisujesz liczby do pętli, a potem for (int i=0;i<[ilosc liczb];i++) i pod spodem for (int j=i+j;j<[ilosc liczb];j++) wtedy wszelkie możliwe kombinacje tych liczb będą pod tab[i] oraz tab[j].
Twoje rozwiązanie ma złożoność kwadratową, więc jest stanowczo za wolne (wg. treści zadania, za takie rozwiązanie jest tylko 25% punktów).
Wy sobie żartujecie, prawda?
a-b > a+b
0 > 2b
0 > b
b < 0
Więc zachodzi to dla każdej pary liczb gdzie b < 0. Mam nadzieję że umiecie policzyć przynajmniej ile takich par będzie...
Zliczasz ilość liczb ujemnych.
Odpowiedź: (ilość liczb-1)(ilość liczb ujemnych) - złożoność liniowa.
Natomiast jeżeli dla danych:
-2 2 2
poprawną odpowiedzią jest: 1, czyli tylko jedna para (2,-2) się liczy, to trzeba najpierw posortować i zliczyć niepowtarzające się ilości (pomijamy jeżeli taka jak poprzednia).
Ale niestety złożoność wtedy spada do O(nlog(n));
Odpowiedz na poniższe pytania:
-Kiedy różnica liczb całkowitych jest większa od ich sumy?
Podpowiedź: zależy to od tylko jednej z tych liczb.
-Jeśli dane jest m liczb to ile par może powstać z n-tą liczbą?
Podpowiedź: n-ta liczba nie tworzy pary tylko z samą sobą.
Podpowiedź do zadania: nie trzeba zapamiętywać żadnych liczb poza aktualnie rozpatrywaną.
Poza tym szybko napisałem to zadanie i można nie zwracać uwagi na to czy występują dwie takie same liczby w zbiorze danych. Tj. Nie ma problemu jeśli dwie pary liczb będą takie same o ile powstały z innych elementów podanych. Poza tym, jak już wspomniałem, nie musimy znać innych liczb niż aktualnie dana. Samo zadanie zrobić można na trzech zmiennych, bez tablic.