SPOJ 522 przedszkolanka

Question

Witam, otoz moj problem dotyczy zadania z serwisu SPOJ. Po przeczytaniu tego zadania zauwazylem, ze chodzi w nim o NWW i w kodzie zastosowalem jego wlasna wersje - najpierw obliczylem wielokrotnosci mozliwych liczb dzieci w grupie a nastepnie przyrownalem (petla w petli) obie te wielokrotnosci az do napotkania 2 takich samych najmniejszych. Liczby wprowadzone dzialaja bez zarzutu wszystko sie zgadza, lecz sedzia odrzuca mi ow kod twierdzac iz program podaje "bledna odpowiedz". Nie mam juz pomyslu co moze byc nie tak w moim kodzie ;/

 

#include <iostream>

using namespace std;

int n,a,b,a1[100],b1[100];

int main()
{

    cin>>n;
    for(int i=1; i<=n;i++)
    {
        cin>>a>>b;
        if(a==0)      cout<<b<<endl;
        else if(b==0) cout<<a<<endl;
        else
            {

        for(int j=0; j<100;j++)
        {
            a1[j]=a*(j+1);
            b1[j]=b*(j+1);


        }
        int k=0,cukierki;

        for(int p=0;p<100;p++)
        {

        for(int j=0;j<100;j++)
        {
            if(a1[j]==b1[k])
            {
                cukierki=a1[j];
                break;
            }

        }
        if(cukierki==b1[k]) break;
        else k++;
        }
        cout<<cukierki<<endl;
            }
    }

    return 0;
}

 

Answer 1

Okej, pierwsza rzecz jaka rzuca się w oczy to ten if.

W założeniach zadania masz podane, że liczba cukierków i dzieci w grupie nie jest zerem. Więc w razie podania zera powinieneś po prostu rzucić błąd i zamknąć program albo prosić o ponowne wprowadzenie liczby większej od zero.

Nie wiem jak dokładnie SPOJ sprawdza poprawność rozwiązania ale zamiast wyświetlać cukierki spróbuj tą wartość zwrócić. Możesz wydzielić całe liczenie NWW do osobnej funkcji, wywołać ją w mainie po tym jak jesteś juz pewny, że wpisano poprawną ilość dzieci w grupie i niech funkcja zwraca ilość cukierków. A na koniec return 0.

Jeśli to nie zadziała to sprawdź czy Twoja implementacja NWW działa zawsze, a nie tylko dla pewnych początkowych par liczb.

Comments

Powinna działać zawsze, cout również działa do wyjścia i powinno przyjąć taka odpowiedź. Nie mam pojęcia co może być błędem w tym kodzie :/ napisałem również drugi kod z użyciem algorytmu euklidesa i wzoru na obliczenie NWW, który jest bardziej profesjonalny i działa, lecz ten pierwotny   kod napisany na "chłopski rozum" nie daje mi spokoju i ciągle się zastanawiam czemu sędzia nie chce go przyjąć :/

Answer 2

Ten kod nie działa poprawnie dla niektórych liczb, np. wpisz 187 i 8 i zobacz co wyjdzie. Myślę, że dla odpowiednio dobranych liczb, te tablice 100 elementowe nie wystarczają.

Answer 3

Jeżeli już rozwiązałeś to zadanie to polecam od razu zrobić bardzo podobne z wyższym stopniem trudności NWW - NWW2.

Comments

Dzięki za odpowiedź. Spojrzałem na zadanie i jest bardzo ciekawe. Juz mam pewien pomysł jak je rozwiązać zaraz zabieram się do pracy ^^