zadanie z potyczek algorytmicznych

Odpowiedz Nowy wątek
2013-03-28 15:12
0

witam nie wiem dlaczego mój program nie rozwiązuje dobrze zadania (rezultatem programu zawsze jest 1 albo 0 co jest niepoprawne) ze strony:
http://main.edu.pl/pl/archive/pa/2012/kre


#include <iostream>

using namespace std;

    long int tab[500000][3];
    long int n, wynik, pom1, pom2, pom3;

int main()
{
    wynik = 0;
    cin >> n;

    for (long int i = 0; i < n; i++)
    {
        cin >> tab[i][0] >> tab[i][1] >> tab[i][2];  // wpisanie x,y i r do tab
    }

    for (long int i = 0; i < n; i++)
    {
        for (long int j = i+1; j < n; j++)
        {
            pom1 = (tab[i][0] - tab[j][0])^2;   //obliczam z pitagorasa
            pom2 = (tab[i][1] - tab[j][1])^2;   //a^2+ b^2 = c^2
            pom3 = (tab[i][2] + tab[j][2])^2;   //

            if(pom3 == (pom1 + pom2))
            {
                wynik++;
            }
        }
    }

    cout << wynik;

    return 0;
}
edytowany 1x, ostatnio: pucio19, 2013-03-28 15:16

Pozostało 580 znaków

2013-03-28 15:21
0

^ to nie potęga tylko xor


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
faktycznie - ale dalej zły wynik - pucio19 2013-03-28 15:34
Rozumem że to na co ty zastąpiłeś ^ mamy wywróżyć? - _13th_Dragon 2013-03-28 15:36

Pozostało 580 znaków

2013-03-28 15:36
0

Wciąż nie działa.

Dla danych wejściowych:
4
0 0 5
8 6 5
-6 8 5
2 14 5

powinno wyjść 4 a mój program daje 1

W teście ze strony z zadaniem daje 0/10 pkt i komunikat

Program wywłaszczony


#include <iostream>

using namespace std;

    long int tab[500000][3];
    long int n, wynik, pom1, pom2, pom3;

int main()
{
    wynik = 0;
    cin >> n;

    for (long int i = 0; i < n; i++)
    {
        cin >> tab[i][0] >> tab[i][1] >> tab[i][2];  // wpisanie x,y i r do tab
    }

    for (long int i = 0; i < n; i++)
    {
        for (long int j = i+1; j < n; j++)
        {
            pom1 = (tab[i][0] - tab[j][0]) * (tab[i][0] - tab[j][0]);  //z pitagorasa
            pom2 = (tab[i][1] - tab[j][1]) * (tab[i][1] - tab[j][1]);   
            pom3 = (tab[i][2] + tab[j][2]) * (tab[i][2] + tab[j][2]);   

            if(pom3 == (pom1 + pom2))
            {
                wynik++;
            }
        }
    }

    cout << wynik;

    return 0;
}
edytowany 3x, ostatnio: pucio19, 2013-03-28 15:46
Pokaż pozostałe 6 komentarzy
Należy wymyślić odpowiedni algorytm i go zaimplementować. - _13th_Dragon 2013-03-28 16:33
nie rozwiązujcie zadania w komentarzach. - Rev 2013-03-28 16:35
rzeczywiście wyszedł poprawny wynik w ideone. A w moim pliku źródłowym po uruchomieniu dawało zły wynik - dopiero po skopiowaniu kodu i zapisaniu w innym pliku dało poprawny wynik. - pucio19 2013-03-28 16:37
@pucio19: jeżeli korzystasz ze starego Dev-C++ (4.9 bodajże), to nawet bym się nie dziwił... - Patryk27 2013-03-28 16:42
Tak korzystam z dev'a - pucio19 2013-03-28 16:53

Pozostało 580 znaków

2013-03-28 16:32

Warunek if(pom3 == (pom1 + pom2)) jest zły bo w zdaniu nie pytają ile jest par kręgów stycznych zewnętrznie, ale ile jest par kręgów, które mają punkt wspólny.
na dodatek (109)2 nie zmieści się w long int (32 bity), ale w long long int (64 bity).


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 4x, ostatnio: MarekR22, 2013-03-28 16:39
Też napisano że "Każde dwa kręgi stykają się w co najwyżej jednym punkcie" - więc warunek poprawny (o ile nie liczyć nie mieszczenia się w long long). - _13th_Dragon 2013-03-28 16:42
poszedłem na skróty i przeczytałem co ma być na wyjściu, nie cierpię tych bajtazarskich bajeczek. - MarekR22 2013-03-28 16:58

Pozostało 580 znaków

2013-03-28 16:48
0

MarekR22 zgadza się za mały typ danych trzeba dać long long int.
Ale po zmianie wciąż w teście wychodzi 0/10pkt (3 na 14 testów zaliczyło - 10 testów program wywłaszczony , 1 test zły wynik) i program wywłaszczony.

#include <iostream>

using namespace std;

long int tab[500000][3];
long int n, wynik;
long long int pom1, pom2, pom3;

int main()
{
wynik = 0;
cin >> n;

for (long int i = 0; i < n; i++)
{
    cin >> tab[i][0] >> tab[i][1] >> tab[i][2];  // wpisanie x,y i r do tab
}

for (long int i = 0; i < n; i++)
{
    for (long int j = i+1; j < n; j++)
    {
        pom1 = (tab[i][0] - tab[j][0]) * (tab[i][0] - tab[j][0]);  //z pitagorasa
        pom2 = (tab[i][1] - tab[j][1]) * (tab[i][1] - tab[j][1]);
        pom3 = (tab[i][2] + tab[j][2]) * (tab[i][2] + tab[j][2]);

        if(pom3 == (pom1 + pom2))
        {
            wynik++;
        }
    }
}

cout << wynik;

return 0;

}

Pozostało 580 znaków

2013-03-28 16:50
0

Nie bez powodu są to "potyczki algorytmiczne" - byle pierwsze lepsze rozwiązanie tutaj nie przejdzie, stąd masz wywłaszczenie programu.


trzeba będzie pomyśleć o innym algorytmie - pucio19 2013-03-28 16:53
mówiąc po informatycznemu naiwny algorytm ma złożoność obliczeniową o(n^2), a ty powinieneś wycisnąć co najmniej o(n log n) - MarekR22 2013-03-28 17:02
Nie ma to jak zadanie z potyczek, które na finale zrobiło tylko dwóch z dwudziestu najlepszych w Polsce :D - BFS 2013-03-29 12:20

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0