804. Gra Euklidesa [EUCGAME]

[code_messiah]

Cześć,

Otóż taki komunikat pokazuje mi się przy kompilacji na stronie: "threshold: 5".

Z innych tematów wyczytałem, że nie spełniłem wymaganej liczby punktów najprawdopodobniej.
Pytanie co poszło nie tak, jeżeli oba testy w okienku konsoli kod przechodzi prawidłowo.
Czy ktoś coś widzi? : ) Dziękuję za odpowiedzi!

  Tu był kod.

[sig]

Tą część

     while (a>b)
    {
        a = a-b;
    }
    while (b>a)
    {
        b = b-a;
    }

Trzeba by powtarzać póki a jest różne od b, swoją drogą weźmy taki test
1
2 1000000000
Naprawdę trzeba tyle razy dwójkę odejmować? Czy też można szybciej policzyć ile zostanie?

[narbej]

Testując z klawiatury [w okienku konsoli], nie widać pewnych niuansów [może widać, ale trezba umieć zauważyć].
Dlatego najlepiej testować przekierowywując z pliku, jak nie wiesz jak, możesz łatwo na ideone.com: zobacz http://ideone.com/cDDVGd

Druga sprawa, to twój algorytm jest nie tylko mniej efektywny od najlepszego to dodatkowo błędny. Wystarczyłoby "ubrać" go w pętle dopóki a!=b. Po obu poprawkach jest AC 15 pkt.

PS
nwd (1122, 867) = 51 <-- https://pl.wikipedia.org/wiki/Algorytm_Euklidesa

PS 2

Otóż taki komunikat pokazuje mi się przy kompilacji na stronie: "threshold: 5".

To nie jest komunukat kompilacji, tylko komunikat sędziego - przy wykonaniu - sprawdzaniu poprawności działania twojego kodu.

PS 3
Kiedyś, "duży" test, mogł powodować TLE i tylko 10 pkt, ale po "przeprowadzce" na szybsze komputery, i pozostawieniu nie zmienionego limitu czasu [1 sek], nawet "wolne" ale poprawne algorytmy uzyskują 15 pkt.

[code_messiah]

Zmieniłem trochę algorytm, i przechodzi wszystkie testy - łącznie z przypadkami takimi jak: a=1122 i b=867 oraz a=1000000 i b=2.
Czas maksymalny wykonania programu narzucony w treści zadania to 1s. Mój algorytrm nie przekracza tego czasu.
Chyba najważniejsze jest to, że algorytm zwraca poprawne wyniki w zadanym czasie, prawda? Nawet jeżeli nie jest to najefektywniejszy sposób. Chyba, że nie ogarniam czegoś w działaniu sędziego...

Z jakiegoś powodu ideone pokazuje "błąd wykonania": http://ideone.com/tubyłlink
Proszę kogoś o wytłumaczenie mi tego, jeśli w pośpiechu przedświątecznym znajdzie czas.

Kod:

Tu był kod.

[krystian01]

Trochę przekombinowałeś. Można to zrobić dużo prościej. Na początku, byś mógł jakoś poukładać swój kod zastanów się jaki jest warunek końcowy programu? Skoro:

Gra kończy się w sytuacji, gdy żaden z graczy nie może wykonać ruchu (w szczególności gra może skończyć się bezpośrednio po "rozdaniu" żetonów, bez jakichkolwiek ruchów).

Oznacza to, że program ma wykonywać dana pętlę dopóki a != b
Czyli:
while (a!=b) {
//jakieś operacje
}
Nie mogę znaleźć testu, dla którego twój algorytm daje niepoprawny wynik, ale poukładaj to jakoś inaczej i czytelniej, żeby każdy mógł wiedzieć co robisz:

Na koniec:
while(a!=b){
if (a < b) {...}
else if (b < a) {...}
}

[code_messiah]

Zastosowałem się do życzliwych propozycji, i co? "0 threshold 5".

... Po czym rozgoryczony dodałem " <<endl;" na końcu. Zaliczone.

-,- i hate the judge.

[krystian01]

Faktycznie brakowało "endl" . Poprzedni kod też by ci zaliczyło jakbyś dodał "endl" Bywa i tak Gratuluję zaliczenia.

PS. Tak z ciekawości... jaki miałeś czas?

[code_messiah]

Oj jak porównuję z najlepszymi czasami w tym zadaniu to bardzo kiepski: 0.22.

Kod którym zaliczyłem różnił się jednak trochę od tego który wrzuciłem na forum, wprowadziłem a !=b, o którym pisałeś ty i kolega wyżej.

Wszystkiego dobrego na święta każdemu kto zaglądnął do tego tematu!

[narbej]

Testując z klawiatury [w okienku konsoli], nie widać pewnych niuansów [może widać, ale trezba umieć zauważyć].Dlatego najlepiej testować przekierowywując z pliku, jak nie wiesz jak, możesz łatwo na ideone.com: zobacz http://ideone.com/cDDVGd

Właśnie tym drobnym niuansem w twoim kodzie był między innymi brak endl. Podpowiedzi także trzeba umieć czytać i z nich korzystać

Przepraszam. Wszyscy [większość] znających się na programowaniu i na "obsłudze" SPOJ'a, mogących Ci pomóc, będzie do jutra, do godziny 20:00, bardzo zajęta na ostatniej już w tym roku rundzie AlgoLigi -> http://algoliga.pl. Ale nie czekaj, sam/a też możesz tam zajrzeć i spróbować swoich sił, zapraszamy Cię bardzo serdecznie!

[kazik98x]

#include <iostream>

using namespace std;

int main()
{
int t;
cin>>t;

for(int i=0;i<t;i++)
{
    int a,b;
    cin>>a>>b;
    int x=0;

do
{
    if(a>b)
    {
        a=a-b;
        x=a+b;
    }
    else if(a<b)
    {
        b=b-a;
        x=a+b;
    }
    else
    {
        x=a+b;
    }

    cout<<x<<endl;

}
while(a!=b);

}


return 0;

}

Dlaczego w tym kodzie pojawia się komunikat 0 (threshold: 5) ?

[sig]

Dostałeś zero punktów, a potrzebujesz 5 do zaliczenia. Część błędów (np 0 w tym) jest "kikalna" i można przeczytać powód (akurat u ciebie na 3 zestawy testów jest 1 nieprawidłowa odpowiedź i 2 przekroczone limity czasu)

[krystian01]

laczego w tym kodzie pojawia się komunikat 0 (threshold: 5) ?

[->] Pamiętaj, że pętla:

do{
     
} while(...);

Wykonuje się przynajmniej raz i zamiast 3 out'ów w twoim programie są 4. Gra może się zakończyć od razu przy wartościach: [1, 1]; [2, 2]; [3, 3]; itd.
Tutaj masz pierwszą czynność do wykonania.

[->] Gdy poprawisz na taki kod :

po częsci poprawiony twój kod, ale nadal bez AC[CLICK]

To nadal nie będzie AC. Po co Ci dodatkowa zmienna 'x' ? Nie lepiej od razu dodawać do 'a', odejmować od 'a' itd.?
a+= jakieś_wyrażenie;
lub
a-= jakieś_wyrażenie;

Po co na wyjście wypisujesz:

cout << x << endl;

?
Można od razu wypisać:

cout << a + b << endl;

Tylko musisz umieścić umieścić to cout ... po pętli while(a!=b){} , a nie w środku tej pętli. Podejrzewam, że po tych poprawkach będziesz mieć AC z wynikiem 10.
Max jest 15, ale to już sam musisz się domyśleć co zrobić, by mieć taki rezultat

PS. Usuń zmienną x i jej nie używaj, bo jest niepotrzebna.
PS 2. Ostatni warunek else ... też jest niepotrzebny.

[odziownik]

Witam,
rowniez mam problem z tym zadankiem, pojawia sie ten sam blad: "0: Treshold 5" - nie mam pojecia co on oznacza, po kliknieciu nie pojawiaja sie zadne zrozumiale dla mnie informacje, natomiast przy probie kompilacji na ideone pojawia sie znow "blad wykonania" - czy to oznacza jakis gruby blad w kodzie?

tu jest link do mojego programu:
//TU BYL KOD
podejrzewam ze glownym problemem jest wydajnosc skryptu bo przy podaniu danych wejsciowych w stylu 1 000 000 000 i 1 czas wykonania programu wynosi kilkanascie sekund. czy moglbym liczyc na jakies podpowiedzi, jak to obejsc?

[krystian01]

Banalna poprawka i będzie AC. Umieść linijkę
int A[t], B[t], wynik[t];
za:
cin >> t;

I dostaniesz AC z wynikiem 15. Widzę, że jesteś początkujący zatem kilka uwag.
Deklarowanie zmiennych w ten sposób:
cin >> t;
int A[t], B[t], wynik[t];

możliwe jest tylko w niektórych kompilatorach lub występuje jako rozszerzenie do niego. Należy unikać tego rodzaju deklaracji. Brzydki, ale przenośny kod wyglądałby tak:
cin >> t;
int *a, *b, *wynik;
a = new int[t];
b= new int[t];
wynik = new int[t];

Kod którego powinieneś użyć:
cin >> t;
std::vector a(t), b(t), wynik(t);

Odsyłam tutaj

[odziownik]

rzeczywiscie, wszystko jak powiedziales : )

fakt ze jestem poczatkujacy, dopiero czytam o podstawach, niestety brakuje mi dobrych kursow z przykladami praktycznymi, a w moim przypadku inny rodzaj nauki nie przynosi rezultatow, dlatego tez duzo eksperymentuje, jednak dzieki ludziom Twojego pokroju nawet na blednych eksperymentach mozna sie sporo nauczyc, dzieki wielkie za pomoc!!!

[flying_high01]

Mam dokładnie ten sam problem co poprzednicy.

Sędzia nie akceptuje mojego kodu (komunikat 0 (threshold: 5)), pomimo uzyskania poprawnych wyników na wyjściu.

Dopiero zaczynam kodować i sądzę, że popełniłem drobny błąd, który nie zauważam, a jest za pewne oczywisty:

Ideone.com

Będę wdzięczny za pomoc

[mariusz193]

Mam dokładnie ten sam problem co poprzednicy.

zgadza się, ten problem już wystąpił, więc odpowiedź znajdziesz gdzieś powyżej

[skupcioo]

Halko sorki ,że odświeżam ale czy ktoś ogarnie czemu to nie chce działać ? #include

using namespace std;
int Lb_testow,zetonyA,zetonyB;

int main()
{
cout << “Podaj liczbe testow” << endl;
cin>>Lb_testow;
for (int i=1;i<=Lb_testow;i++)
{
cin>>zetonyA>>zetonyB;

    {
        while(zetonyA!=zetonyB)
        {
          if(zetonyA>zetonyB)
          {

                zetonyA = zetonyA-zetonyB;

          }

          if(zetonyA<zetonyB)
          {
                zetonyB = zetonyB-zetonyA;

          }


        }

    }
    cout<<zetonyA+zetonyB;

}
return 0;

}

[reny]

System nie może tego sprawdzić
W SPOJU po prostu przyjmuje się dane bez

cout << “Podaj liczbe testow” << endl;

I dane wyjściowe powinny być oddzielone od siebie, a nie tworzyć ciąg znaków

cout<<zetonyA+zetonyB << endl;

Masz też drobny błąd w warunkach (są dobre, ale brakuje jednego słowa)

[ancoqlaus]

Hej, sam zrobiłem kod, przeczytałem później cały temat i dalej nie wiem w czym leży błąd.
Obecnie 2 z testów są zaliczone poprawnie
Pierwsze testy trwają 0.01 s, niestety pokazuje mi iż ostatni test trwa 1.01s podczas gdy limit to 1.00s

int main()
{
    int ile, a, b;
    cin >> ile;
    for (int i = 0 ; i < ile ; i++)
    {
        cin >> a >> b;
        while (a!=b)
        {
            if (b > a)
            {
                b -= a;
                continue;
            }
            else if (a > b)
            {
                a -= b;
                continue;
            }
        }
        cout << a + b << endl;
    }
    return 0;
}