SPOJ Ostatnia niezerowa cyfra silnii

pytanie zadane 5 listopada 2017 w SPOJ przez michal12334 Obywatel (1,510 p.)
edycja 6 listopada 2017 przez michal12334

Zrobiłem zadanie z serwisu SPOJ ostatnia niezerowa funkcja silni. Wyskakuje mi przekroczono limit czasu i nie mam pomysłu jak zoptymalizować algorytm. Link do zadania: http://pl.spoj.com/problems/OSTSIL/

#include <iostream>

using namespace std;

//funckja obliczajaca wartosc silni
unsigned long long obliczSilnia(int a) {
    if (a==1) return 1;
    else return a*obliczSilnia(a-1);
}

int main() {
    //zmienne oznaczajace liczbe testow oraz liczbe w danym tescie
    int t, liczba;

    //wczytanie wartosci liczby testow
    cin >> t;

    //petla ktora wykona wszystkie testy
    for (int i = 0; i<t; i++) {
        //wczytanie wartosci liczby dla danego testu
        cin >> liczba;

        //zmienna przechowujaca wartosc silni
        unsigned long long silnia = obliczSilnia(liczba);

        //obciecie zer stojacych z tylu liczby
        while (silnia/10*10==silnia) {
            silnia /= 10;
        }

        //wypisanie ostatniej niezerowej cyfry silni
        cout << silnia%10 << endl;
    }

    return 0;
}

2 odpowiedzi

odpowiedź 5 listopada 2017 przez 10kw10 Pasjonat (22,880 p.)

wypisz sobie wartosci silni od 1 do 10 i zauwaz regule.

komentarz 6 listopada 2017 przez michal12334 Obywatel (1,510 p.)

Mógłbyś dać mi jeszcze jedną wskazówkę bo nie widzę żadnej reguły?

komentarz 6 listopada 2017 przez 10kw10 Pasjonat (22,880 p.)

liczba | silnia(liczba)

komentarz 6 listopada 2017 przez 10kw10 Pasjonat (22,880 p.)

zuwaaz co sie dzieje z wartosciami silni gdy liczba jest wieksza lub rowna 10, a reszta to juz ify

komentarz 6 listopada 2017 przez michal12334 Obywatel (1,510 p.)

Chodzi o to, że ostatnia niezerowa cyfra w silni z np. 11 to ostatnia niezerowa cyfra z silni 1*8?

komentarz 6 listopada 2017 przez 10kw10 Pasjonat (22,880 p.)

pomylilem zadania ;d

komentarz 7 listopada 2017 przez michal12334 Obywatel (1,510 p.)

Ale pomogło mi to dojść do rozwiązania, choć teraz w kodzie mam błąd którego nie mogę znaleźć.

#include <iostream>

using namespace std;

//funckja obliczajaca wartosc silni
int obliczSilnia(int a, int k[]) {
    if (a==10) return k[8];
    else if (a<10) return k[a-1];
    else {
        for (int i = 0; i<9; i++) {
            k[i] = (k[i]*k[8])%10;
        }
        return obliczSilnia(a-10, k);
    }
}

int main() {
    //zmienne oznaczajace liczbe testow oraz liczbe w danym tescie
    int t, liczba;

    //wczytanie wartosci liczby testow
    cin >> t;

    //petla ktora wykona wszystkie testy
    for (int i = 0; i<t; i++) {
        //tablica przechowujaca koncowki silni od 1 do 9
        int koncowki[9] = {1, 2, 6, 4, 2, 2, 4, 2, 8};

        //wczytanie wartosci liczby dla danego testu
        cin >> liczba;

        //wypisanie ostatniej niezerowej cyfry silni
        cout << obliczSilnia(liczba, koncowki) << endl;
    }

    return 0;
}