Polski SPOJ zad 496 Dwie cyfry silni. Wynik (Przekroczono limit czasu )

Question

Ktos wie jak mozna tu zaoszczedzic czasu ? :)

#include <iostream>

using namespace std;

int silnia(int n)
{
    int silnia=1;

    for(int i=2;i<=n;i++)
        silnia=silnia*i;

    return silnia;
}

int main()
{
  int ile,a;

  cin>>ile;

   for(int i=0;i<ile;i++)
   {
    cin>>a;
    cout<<silnia(a)/10<<" "<<silnia(a)%10<<endl;
   }
    return 0;
}

 

Answer 1

Wartości silni rosną bardzo szybko. Przykładowo 20! = 2432902008176640000 (takie liczby już dawno nie mieszczą się w zmiennej typu int). W zadaniu będą podawane przypadki gdy n będzie równe aż 1 000 000 000. Rozpisz sobie na kartce silnie od 1 do np. 12. Od 10! powinieneś zauważyć zależność, że ostatnie cyfry silni zawsze będą zerami więc liczenie ich nie ma sensu :) Zwłaszcza, że to pochłania dużo czasu, a wynik i tak wyjdzie poza zakres zmiennej.

Comments

Jeszcze jedna mała uwaga dla silnia(a) = 120
silnia(a)/10 = 12 - to liczba a chcą cyfrę

Proponuję zrobić (silnia(a)%100)/10 dla cyfry dziesiątek

---

Żeby nie tworzyć znów nowego tematu to pozwolę sobie dopisać tutaj. :P Mianowicie na spoju wyskakuje mi błędna odpowiedź i nie mam zielonego pojęcia dlaczego... Nie chciałby może ktoś mnie nakierować? ;>

 

#include <iostream>

using namespace std;

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

        if(x<10)
        {
        	int s=1;
            for(int i=1; i<=x; i++)
                s=s*i;
                a=(s%100)/10;
            b=s%10;
            cout << a << " " << b;
        }
        else cout << a << " " << b;
    }

    return 0;
}

 

---

Dodałbym nową linię po cout. Gdy pętla działa sobie jakiś czas i wyjdzie np oblicz silnie z 10 to a i b mają już w sobie jakieś wartości. Powinieneś wtedy w elsie je wyzerować przed wypisaniem, albo napisać zera po prostu. Kod poprawny:

#include <iostream>

using namespace std;

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

        if(x<10)
        {
            int s=1;
            for(int i=1; i<=x; i++)
                s=s*i;
                a=(s%100)/10;
            b=s%10;
            cout << a << " " << b<<endl;
        }
        else cout << a << " " << b<<endl;

        a=0; b=0;
    }

    return 0;
}

Albo bez zerowania zmiennych w pętli:

 else cout << 0 << " " << 0 << endl;

---

Zobaczyłem ten problem zaraz po napisaniu posta :P Ale i tak dziękuje, że się zainteresowałeś