Jak to przyspieszyć ? Zadanie SPOJ "Dwie cyfry silni"

0
#include <iostream>

int silnia(unsigned int &x)
{
	unsigned int wynik = 1;
	for (int i = 1; i <= x; i++) 
	{
		wynik *= i;
	}
	return wynik;
}

int main() {

	short d = 0;
	unsigned int* tab = nullptr;

	do
	{
		std::cin >> d;
	} while (d > 20 && d <= 0);
	
	tab = new unsigned int[d];

	for (int i = 0; i < d; i++)
	{
		std::cin >> tab[i];
	}

	for (int i = 0; i < d; i++)
	{
		std::cout << silnia(tab[i]) / 10 << " " << silnia(tab[i]) - ((silnia(tab[i]) / 10) * 10);
		std::cout << std::endl;
	}

	// end
	delete[] tab;
	return 0;
}

Zrobiłem wszystko co wiedziałem, że mogę zrobić. Jest to zadanie ze strony www.spoj.com - dokładnie [https://pl.spoj.com/problems/FCTRL3/] "Dwie cyfry silni".
Z czego co widze wszystko działa jak ma działać tzn. zadanie wykonane... Tylko czas się nie zgadza. Zamieniłem int'y na short'y aby mniej pamięci zajmowało (intuicyjnie, czyli nie
wiem czy to coś da). Dodam, że dopiero zaczynam w tym c++.

5

Już było na tym forum, zadanie w 5 wierszy z czasem O(1)

3

Zastanów się jak wyglądają te wyniki i dlaczego. Może sobie wypisz pierwszy tysiąc. Są pewne zależności, które da się zauważyć nawet nie będąc ekspertem.

2

https://4programmers.net/Forum/1289117

Chyba moje poczatki na tym forum :D

1

Ja napiszę to co zawsze, jak to zadanie się pojawia.
Weź kartkę i policz ręcznie wyniki zaczynając od 0 a kończąc na 12, a poprawne i szybkie rozwiązanie samo ci się objawi.
Link od stivens jest po prostu rozwiązaniem naiwnym/siłowym zbyt wolnym na SPOJ.

0
MarekR22 napisał(a):

Ja napiszę to co zawsze, jak to zadanie się pojawia.
Weź kartkę i policz ręcznie wyniki zaczynając od 0 a kończąc na 12, a poprawne i szybkie rozwiązanie samo ci się objawi.
Link od stivens jest po prostu rozwiązaniem naiwnym/siłowym zbyt wolnym na SPOJ.

Kolejny co nie potrafi czytac ze zrozumieniem. Ja jak przeczytalem post bogdans to zrobilem to w O(1) ...
Iteracja w tamtym poscie byla jedynie komentarzem do jeszcze bardziej naiwnego rozwiazania rekurencyjnego napisanego przez poczatkujacego programiste. Ale jak sie tylko w listing patrzy bo dwa zdania to za duzo zeby przeczytac to no coz...

1

Można w ten sposób.

#define GSL_THROW_ON_CONTRACT_VIOLATION
#include <iostream>
#include <vector>
#include <gsl_assert>

using namespace std;

template< typename T >
pair<int,int> getLastTwoPositions( T number )
{
    static_assert( std::is_integral<T>::value , "T must be a integral value." );
    Ensures( number>=0 );

    return number>9 ? make_pair(0,0) : (vector<pair<int,int>>{ {0,1}, {0,1}, {0,2}, {0,6}, {2,4}, {2,0}, {2,0}, {4,0}, {2,0}, {8,0} })[number];
}

int main()
{
    for( int i=0 ; i<30 ; i++)
    {
        const auto& [ digit1 , digit2 ] = getLastTwoPositions(i);
        cout << i << " = " << digit1 << ":" << digit2 << "\n";
    }
    return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1