SPOJ Czy umiesz potegowac - nie przekraczam czasu i bledna odpowiedz

Question

Nowy na forum. Dopiero zacząłem pisać w C++. Zadanie znane, ale tutaj link do treści na wszelki wypadek: SPOJ. Rozumiem zadanie i wiem, że nie mogę potęgować wprost. Znalazłem zależności i je przetestowałem, a jednak sędzia pisze o błędzie. Domyślam się, że nie spełniam jakiegoś warunku brzegowego.. Tylko którego? Proszę o pomoc.

    int D, a, b, wynik;
    cin >> D;
    if (D < 11 && D >0)
    {
        while (D > 0)
        {
            D--;
            cin >> a >> b;
            wynik = a % 10;
            b = b % 4 + (4 * (b % 4 == 0));
            if ((wynik > 1 && wynik < 5) || wynik > 6) for (int i = 2; i <=b; i++)   wynik = (wynik * a) % 10;
            cout << wynik << endl;
        }
    }

 

Answer 1

W linii 11 (swoją drogą podziliłbym ją - if, for i samo działanie w jednej linii to trochę za dużo) masz operację:

wynik = (wynik * a) % 10;

Zmienna wynik jest jednocyfrowa, nie ma z nią problemu, ale a może przyjąć wartość miliarda, a na 32 bitowych (jakie tam jest środowisko?) liczbach można liczyć tylko do 2-4miliardów (ze znakiem i bez). Pewnie algorytm wariuje gdy a jest skrajnie duże.

 

 

PS. Tak ogólnie musisz się trochę oswoić z takim informatycznym myśleniem - jeśli w traści zadania/założeniach projektowych jest napisane że coś na działać dla danych np. od jeden do stu to na te skrajne wartości zawsze należy soft przetestować. Oczywiście jeszcze trzeba też inna wartości użyć, ale te skrajne są "na bank".

Comments

Dzięki za podpowiedź. Na moim kompie działało nawet przy 999999999 do potęgi 999999999, więc testowałem nawet największe liczby z zadania.

Natomiast na SPOJ nie chodziło. Ale wystarczyła mała zmiana kodu. Nowa formuła:

wynik = (wynik * (a%10)) % 10

i teraz SPOJ przyjął :)

Dziękuję jeszcze raz! :)

---

Może masz system 64 bit (w C wielkość poszczególnych typów nie jest określona, ustalone są tylko miękkie zależności - co jest większe a co mniejsze) a w spoju uruchamiane jest w 32 bit.