Zadanie Bierki (bie) - problem z implentacją

Question

Witam, dawno mnie tu nie było. Przychodzę z zapytaniem co może być źle w tej implementacji, ponieważ dla trzech przykładów wyrzuca bladną wartość.

LINK DO ZADANIA (SZKOPUŁ):https://szkopul.edu.pl/problemset/problem/KiEvCpZBaUNRCp6oTZx2oAQ4/site/?key=statement

BŁĘDY: 

IMPLEMENTACJA:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool trojkat(int& a, int& b, int& c)
{
	return a > 0 && b > 0 && c > 0 && a + b > c && a + c > b && b + c > a;
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int> vi(n);
	for (int i = 0; i < n; ++i) {
		cin >> vi[i];
	}

	sort(vi.begin(), vi.end());
	for (int i = 0; i <= n; ++i) {
		if (trojkat(vi[i], vi[i + 1], vi[n - 1])) {
			cout << n - i;
			return 0;
		}
	}
}

Z góry dzięki za pomoc, pozdro dla wszystkich.

Comments

Popraw warunek w pętli na:

for (int i = 0; i < n - 1; ++i)

 

int& a, int& b, int& c

W tym przypadku referencje nie mają sensu.

---

Uwzględniłem twoje poprawki, ale dalej te same błędy. Jakieś inne pomysły?

• 4 wiersz 1: wczytano '2931', a oczekiwano '2935'
• 6 wiersz 1: wczytano '8682', a oczekiwano '8686'
• 7 wiersz 1: wczytano '11299', a oczekiwano '11300'

---

Zapomniałem dodać, że chodzi o drugą pętle ;)

---

Nie no, domyśliłem się akurat... ale dalej nie działa.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool trojkat(int a, int b, int c) { return a > 0 && b > 0 && c > 0 && a + b > c && a + c > b && b + c > a; }


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int> vi(n);
	for (int i = 0; i < n; ++i)
		cin >> vi[i];

	sort(vi.begin(), vi.end());
	for (int i = 0; i < n - 1; ++i) {
		if (trojkat(vi[i], vi[i + 1], vi[n - 1])) {
			cout << n - i;
			return 0;
		}
	}
}

 

---

Spróbuj tak (może nie działać, bo nie mam dzisiaj głowy do takich rzeczy):

    bool trojkat(int a, int b, int c) { return a + b > c && a + c > b && b + c > a;  }
    /* ...  */

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

    for (int i = n - 1; i > 1; --i) {
        if (!trojkat(vi[i - 2], vi[i - 1], vi[i])) {
            cout << n - i << '\n';
            break;
        }
    }

Problem z tymi zadankami ze stron jest taki, że prawie zawsze mają za mało danych testowych. Jeden zestaw danych to za mało, by sprawdzić poprawność algorytmu.

---

Niestety to dalej nie to...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool trojkat(int a, int b, int c) { return a + b > c && a + c > b && b + c > a; }


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector <int> vi(n);
	for (int i = 0; i < n; ++i)
		cin >> vi[i];

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

	for (int i = n - 1; i > 1; --i) {
		if (!trojkat(vi[i - 2], vi[i - 1], vi[i])) {
			cout << n - i << endl;
			break;
		}
	}
}

 

---

A co tam jest napisane pod tymi tabelami?

---

Sorka myślałem, że to widać

0ocen wczytano EOF, a oczekiwano '28'
1ocen wczytano EOF, a oczekiwano '40'
2ocen wczytano EOF, a oczekiwano '60'
3ocen wczytano EOF, a oczekiwano '67'
4ocen wczytano EOF, a oczekiwano '75'

1 wczytano EOF, a oczekiwano '594'
2 wczytano EOF, a oczekiwano '1264'
3 wczytano EOF, a oczekiwano '470'
4 wczytano EOF, a oczekiwano '2935'
5 wczytano EOF, a oczekiwano '5287'
6 wczytano EOF, a oczekiwano '8686'
7 wczytano EOF, a oczekiwano '11300'
8 wiersz 1: wczytano '16954', a oczekiwano '8496'
9 wiersz 1: wczytano '19952', a oczekiwano '9934'
10 wiersz 1: wczytano '29875', a oczekiwano '14957'

---

Ten EOF zapewne stąd, że program nic nie zwraca, bo cout w pętli nigdy się nie wykonuje. Dlatego daj zamiast break wywołanie return 0;, a za pętlą cout << n << '\n';

Pozostaje kwestia nieprawidłowych wyników pomimo couta. Pewny jesteś swojego algorytmu?

---

Pozostaje kwestia nieprawidłowych wyników pomimo couta. Pewny jesteś swojego algorytmu?

Wydaje mi się, że powinien być prawidłowy (przynajmniej jak rozpisywałem go na kartce to wynik wychodził dobry)

Ten EOF zapewne stąd, że program nic nie zwraca, bo cout w pętli nigdy się nie wykonuje. Dlatego daj zamiast break wywołanie return 0;, a za pętlą cout << n << '\n';

• 0ocen wiersz 1: wczytano '50', a oczekiwano '28'
• 1ocen wiersz 1: wczytano '70', a oczekiwano '40'
• 2ocen wiersz 1: wczytano '100', a oczekiwano '60'
• 3ocen wiersz 1: wczytano '120', a oczekiwano '67'
• 4ocen wiersz 1: wczytano '150', a oczekiwano '75'

 

• 1 wiersz 1: wczytano '1000', a oczekiwano '594'
• 2 wiersz 1: wczytano '2000', a oczekiwano '1264'
• 3 wiersz 1: wczytano '800', a oczekiwano '470'
• 4 wiersz 1: wczytano '5000', a oczekiwano '2935'
• 5 wiersz 1: wczytano '8000', a oczekiwano '5287'
• 6 wiersz 1: wczytano '10000', a oczekiwano '8686'
• 7 wiersz 1: wczytano '15000', a oczekiwano '11300'
• 8 wiersz 1: wczytano '16954', a oczekiwano '8496'
• 9 wiersz 1: wczytano '19952', a oczekiwano '9934'
• 10 wiersz 1: wczytano '29875', a oczekiwano '14957'

---

Przeczytałem jeszcze raz to zadanie i jeśli je dobrze zrozumiałem, to ma być tak, że dowolnie wybrane trzy bierki mają tworzyć trójkąt, czyli każda z każdą.

Przetestuj to:

/* ... */

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

int c = n;
 
for (int i = n - 2; i > 0 && n > 2; --i) {
    if (!trojkat(vi[i - 1], vi[i], vi[n - 1])) {
        if(i != n - 2) --c, --n;
        else { c -= i - 1, break; }
    }
}
    
cout << c << '\n';

 

---

Działa, dzięki za pomoc. 

---

Wiesz chociaż, gdzie leżał błąd w twoim pomyśle (poza błędnym indeksowaniem)?

---

Na pewno indeksowanie jest inne, po za tym wydaje mi się, że to dlatego, że sprawdzałem tylko dla "największego" elementu tablicy. A w twoim algorytmie jeżeli dane nie spełniają warunku to ustawiasz największy element na index o jeden mniejszy niż był. Chyba to to, co nie?

---

Tak. W swoim algorytmie nie przewidziałeś sytuacji, gdzie najdłuższa bierka nie mogła tworzyć trójkąta z żadną inną bierką. Wystarczy pomniejszyć zbiór o tę bierkę i proces powtórzyć.

---

@asdbf123, Mam podobny problem, na tych samych testach mi nie przechodzi. Użyłem nieco innego algorytmu, gąsienicy. Może ktoś powie co jest źle w mojej implementacji?

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int bierki[30001];
int n,maksymalna_dlugosc = 0,poczatek_przedzialu = 0,koniec_przedzialu = 1;
int main(){
    fast
    cin >> n;
    for(int i = 0;i < n;i++)
        cin >> bierki[i];
    sort(bierki,bierki+n);
    while(koniec_przedzialu <= n){
        if(bierki[poczatek_przedzialu] + bierki[poczatek_przedzialu+1] > bierki[koniec_przedzialu]){
            if(maksymalna_dlugosc < koniec_przedzialu - poczatek_przedzialu)maksymalna_dlugosc = koniec_przedzialu - poczatek_przedzialu;
            koniec_przedzialu++;
        }
        else poczatek_przedzialu++;
    }
    cout << maksymalna_dlugosc;
}