Zadanie Trójkąty I OI - signal 11

Question

Siemka, mam problem z zadaniem Trójkąty z I OI (treść zadania).

W jednym z testów wypluwa błąd: 

• 2b process exited due to signal 11

Niestety nie jestem w stanie namierzyć błędu w mojej implementacji. Pomożecie?

#include <iostream>
#include <algorithm>

using namespace std;

struct Liczba {
	int lic, mia;

	bool operator < (Liczba &b) {
		return (b.lic * mia >= lic * b.mia);
	}
};

Liczba tab[10001];

bool sprawdz(Liczba &a, Liczba &b, Liczba &c) {
	Liczba ApB = {a.lic * b.mia + b.lic * a.mia, a.mia * b.mia}; // a + b
	Liczba ApC = {a.lic * c.mia + c.lic * a.mia, a.mia * c.mia}; // a + c
	Liczba BpC = {b.lic * c.mia + c.lic * b.mia, b.mia * c.mia}; // b + c

	if (ApB.lic * c.mia > c.lic * ApB.mia) // a + b > c
		if (ApC.lic * b.mia > b.lic * ApC.mia) // a + c > b
			if (BpC.lic * a.mia > a.lic * BpC.mia) // b + c > a
				return 1;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i ++) {
		char c;
		cin >> tab[i].lic >> c >> tab[i].mia;
	}

	sort(tab + 1, tab + n + 1);

	Liczba a, b, c;
	a = tab[1];
	b = tab[2];
	c = tab[n];

	if (sprawdz(a, b, c))
		cout << "TAK";
	else
		cout << "NIE";
}

 

Answer 1

Operator < musi określać "strict weak ordering" żeby std::sort zadziałał. W szczególności relacja musi być antysymetryczna, czyli jest x < y to nie prawda, że y < x. Twój operator< tego nie spełnia. Zamiana <= na < wewnątrz definicji operatora< wystarczy, żeby otrzymać strict weak ordering

Comments

Tak trochę przy okazji operatorów. A dlaczego jak mamy seta struktury to nie potrzeba operatora == np do finda, tylko < wystarcza?

I czy jak mamy np seta / sorta to można zamiast operatora < napisać <= lub > lub >=?

---

Stąd wynika, że wciąż wystarczy sam strict weak ordering, czyli a i b uznane są za równoważne jesli !(a < b) && !(b < a). By default set i sort korzysta chyba z std::less do porównywania, więc trzeba zdefiniować operator<

Answer 2

Kilka rzeczy:

1 - jak sprawdzasz czy da się zbudować trójkąt z 3 patyków, to wystarczy, że 2 najmniejsze są większe od trzeciego, bo jak dwa najmniejsze są większe, to inne które są większe od tych największych tym bardziej dadzą wiekszą sumę.  Funkcja sprawdzająca może wyglądać tak:

bool sprawdz(Liczba &a, Liczba &b, Liczba &c) {
    Liczba ApB = {a.lic * b.mia + b.lic * a.mia, a.mia * b.mia}; // a + b

    if (ApB.lic * c.mia > c.lic * ApB.mia) // a + b > c
        return 1;
    return 0;
}

Po drugie, jak sortujesz tablicę i sztywno definiujesz jej rozmiar, to prosisz się o kłopoty. Lepiej wrzuć sobie na vector, posortuj jak Bóg przykazał i problemy znikły.

Te 2 rzeczy opisane powyżej do dobre praktyki, które warto pisać, żeby nie prosić się o kłopoty.

I teraz skupmy się na twoim operatorze. Zauważ, że ty w nim napisałeś warunek, żeby sortował od największych.

return (b.lic * mia >= lic * b.mia);

A jak sprawdzasz czy da się zbudować trójkąt, to sprawdzasz najmniejszy, drugi najmniejszy i największy. A ty do funkcji przekazujesz 1,2,N, czyli największy, drugi największy i najmniejszy, co już z założenia jest złe. (Przy założeniu, że usuwamy z funkcji te 2 if-y i zostawiamy nową wersję, tylko A+B > C)

I teraz apropo twojego operatora:

bool operator < (Liczba &b) {
        return (b.lic * mia >= lic * b.mia);
    }

Ja jakoś bardzo na składni operatorów w C++ się nie znam, więc nie wiem czy ten twój jest poprawny(są na forum napewno osoby, które się znają, więc one mogą się wypowiedzieć), ale jak zmieniłem na taki jak ja piszę, to przeszło na 100, więc raczej jest zły. Ogólnie jak zaczynałem uczyć się programować i algorytmiki, to przyjąłem stałą konwencję pisania operatorów i przy ponad 400 zadaniach się na niej nie zawiodłem(pisząc tą konwensją) , więc podejrzewam, że jest dobra (Prosiłbym o potwierdzenie osoby znającej się z składnią C++). Zakładam, że sortuję od najmniejszych, żeby sprawdzić w procedurze patyczki o numerach 1,2,N.

Mniej więcej schemat jak piszę operator wygląda tak:

 bool operator < (const Liczba &liczba) const
 {
        return (lic * liczba.mia < liczba.lic * mia);
 }

- są 2 consty ten drugi chyba jest obowiązkowy, nie piszę &b, tylko &liczba, w sensie nazwa structa tylko z małej

- zawsze jako pierwszą w porównywaniu porównuję licz, a nie liczba.licz

- unikam <=, >= itp,  tylko piszę <, > itp. (jesli to mozliwe)

w twoim operatorze nie ma constów, co wydaje mi się, byc błedne, i też co jest podejrzane, to że najpierw sprawdzasz b.lic, a nie lic.

 

Myśłę, że błędem w twoim kodzie mogło być to sortowanie z stałym rozmiarem tablicy o jeden większym, w sensie ten element nie używany gubił porządek, dlatego jest to proszenie o problemy i lepiej zrobić to normalnie na vectorze. Sprawdziłem i po poprawieniu tego przechodzi na 100.

Comments

Ten sam błąd:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Liczba {
	int lic, mia;

	bool operator < (const Liczba &b) const {
		return (b.lic * mia >= lic * b.mia);
	}
};

bool sprawdz(Liczba &a, Liczba &b, Liczba &c) {
	Liczba ApB = {a.lic * b.mia + b.lic * a.mia, a.mia * b.mia}; // a + b

	if (ApB.lic * c.mia > c.lic * ApB.mia) // a + b > c
		return 1;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	vector <Liczba> vec(n);

	for (int i = 0; i < n; i ++) {
		char c;
		cin >> vec[i].lic >> c >> vec[i].mia;
	}

	sort(vec.begin(), vec.end());

	Liczba a, b, c;
	a = vec[0];
	b = vec[1];
	c = vec[n - 1];

	if (sprawdz(a, b, c))
		cout << "TAK";
	else
		cout << "NIE";
}

 

---

tutaj wyniki w formie obrazka:

---

Błąd jest w operatorze.

Napisałeś tak:

return (b.lic * mia >= lic * b.mia);

po 1 - operator ma <, a ty zwracasz <= z tego (najprawdopodobniej leci signal).

A po drugie, to chcesz posortować od najmniejszych a nie od największych. Albo posortuj od najmniejszych, albo zamiast przekazywać 0,1, N-1, przekazuj N-1, 1, 0

Zamiast przekazać A, B, C, ty przekazujesz C, B, A do funkcja sprawdzającej, czy z patyków można ułożyć trójkąt.

---

no wlasnie nie, bo ja dobrze sortuje...

zmienilem tylko w kodzie z >= na > i dziala.

---

no tak wsm racja, to jest analogiczne, do tego co ja opisałem.

---

Poprawcie mnie, ale tu wystarczy mieć posortowane 2 pierwsze wartości i wyliczoną max()/min() z reszty (chyba że coś pokręciłem). Stąd raczej nie sort() a nth_element()

https://en.cppreference.com/w/cpp/algorithm/nth_element

Bo wystarczy częściowe sortowanie.

BTW. W ~30 linii lepiej przy znanym n, zrobić na wektorze reserve() a nie przekazywać ilość do konstruktora. W tym drugim przypadku uruchamia domyślne konstruktory Liczba x n.

Answer 3

Jeszcze dopowiedziałbym, że to zadanie można zrobic w czasie O(N), zamiast sorta zapamietujesz 2 najmniejsze i największy na zmiennych. Lub dla 2 najmniejszych masz seta który ma zawsze 2 najmniejsze elementy, żeby nie bawić się w ifowanie. A największą jest jedna, więc spoko.

Podobny motyw z spamietywaniem kilku największych / największych na zmiennych był w zadaniach deski z OIJ i deski kontratakują z OIJ. Też można było posortować, ale szybciej wchodził właśnie ten trik.