"Czy Umiesz Potęgować" - SPOJ - Jak przyśpieszyć kod?

Question

Witam, rozwiązywałem tytułowe zadanie ze SPOJ'a i udało mi się napisać taki oto kod (wg. mnie prawidłowy).

#include <iostream>

int main()
{
    short D,number,numbers2[4]={2,4,8,6},numbers3[4]={3,9,7,1},numbers4[2]={4,6},numbers7[4]={7,9,3,1},numbers8[4]={8,4,2,6},numbers9[2]={9,1},j=0;
    long long int a,b;
    std::cin>>D;
    for(int i=0;i<D;i++)
    {
        std::cin>>a>>b;
        if (a==0 || a%10==0)
            number=0;
        else if (a==1 || a%10==1 || b==0)
            number=1;
        else if (a==2 || a%10==2)
            for(int i=1;i<=b;i++,j++)
            {
                number=numbers2[j];
                if (i%4==0)
                    j=-1;
            }
        else if (a==3 || a%10==3)
            for(int i=1;i<=b;i++,j++)
            {
                number=numbers3[j];
                if (i%4==0)
                    j=-1;
            }
        else if (a==4 || a%10==4)
            for(int i=1;i<=b;i++,j++)
            {
                number=numbers4[j];
                if (i%2==0)
                    j=-1;
            }
        else if (a==5 || a%10==5)
            number=5;
        else if (a==6 || a%10==6)
            number=6;
        else if (a==7 || a%10==7)
            for(int i=1;i<=b;i++,j++)
            {
                number=numbers7[j];
                if (i%4==0)
                    j=-1;
            }
        else if (a==8 || a%10==8)
            for(int i=1;i<=b;i++,j++)
            {
                number=numbers8[j];
                if (i%4==0)
                    j=-1;
            }
        else if (a==9 || a%10==9)
            for(int i=1;i<=b;i++,j++)
            {
                number=numbers9[j];
                if (i%2==0)
                    j=-1;
            }
        std::cout<<number<<std::endl;
        j=0;
    }
    return 0;
}

Treść zadania: http://pl.spoj.com/problems/PA05_POT/

Mam pytanie, widziałem już pewne, o wiele szybsze rozwiązania tego zadania, jednak ciekawi mnie czy mógłbym przyśpieszyć ten kod jednocześnie nie zmieniając jego konstrukcji diametralnie. Zależy mi właśnie na tym, abym nie zmieniał większości kodu, chciałbym mniej więcej tego typu rozwiązanie wysłać. Mógłby mi ktoś coś doradzić, abym mógł wystarczająco przyśpieszyć ten kod, żeby SPOJ mógł go zaliczyć?

Comments

O matko boska, tyle ifow to ja dawno nie widziałem. Nie tędy droga, bo tak się nie rozwiązuje problemów. Polecam potegowanie modularne, albo rozpisać sobie potęgi dla wszystkich cyfr i coś zauważyć.

Answer 1

W Twoim kodzie jest dużo redundancji kodu i niepotrzebnych pętli. Ja zrobiłbym to tak:

#include <iostream>

int main()
{
	int tablica[10][4] =
	{
		{ 0, 0, 0, 0 },
		{ 1, 1, 1, 1 },
		{ 6, 2, 4, 8 },
		{ 1, 3, 9, 7 },
		{ 6, 4, 6, 4 },

		{ 5, 5, 5, 5 },
		{ 6, 6, 6, 6 },
		{ 1, 7, 9, 3 },
		{ 6, 8, 4, 2 },
		{ 1, 9, 1, 9 }
	};

	int podstawa, wykladnik;
	int ile;

	std::cin >> ile;
	for (int i = 0; i < ile; i++)
	{
		std::cin >> podstawa;
		std::cin >> wykladnik;

		std::cout << tablica[podstawa % 10][wykladnik % 4] << "\n";
	}
}

Comments

O tej metodzie właśnie pisałem zakładając ten temat, jest seksi i na pewno o wiele lepsza niż moja, ale chciałbym póki co po prostu zmodyfikować mój kod. Mam pewien pomysł, jeżeli wypali (i nie zapomnę) to napisze czy zadziałało.

---

#include <iostream>

int main()
{
    short D,number,numbers2[4]={2,4,8,6},numbers3[4]={3,9,7,1},numbers4[2]={4,6},numbers7[4]={7,9,3,1},numbers8[4]={8,4,2,6},numbers9[2]={9,1};
    int a,b;
    std::cin>>D;
    for(int i=0;i<D;i++)
    {
        std::cin>>a>>b;
        if (a%10==0)
            number=0;
        else if (a%10==1)
            number=1;
        else if (a%10==2)
            for(int i=0;i<=b%4;i++)
            {
                if (b%4==0)
                    number=numbers2[3];
                else
                    number=numbers2[i-1];
            }
        else if (a%10==3)
            for(int i=0;i<=b%4;i++)
            {
                if (b%4==0)
                    number=numbers3[3];
                else
                    number=numbers3[i-1];
            }
        else if (a%10==4)
            for(int i=0;i<=b%2;i++)
            {
                if (b%2==0)
                    number=numbers4[1];
                else
                    number=numbers4[i-1];
            }
        else if (a%10==5)
            number=5;
        else if (a%10==6)
            number=6;
        else if (a%10==7)
            for(int i=0;i<=b%4;i++)
            {
                if (b%4==0)
                    number=numbers7[3];
                else
                    number=numbers7[i-1];
            }
        else if (a%10==8)
            for(int i=0;i<=b%4;i++)
            {
                if (b%4==0)
                    number=numbers8[3];
                else
                    number=numbers8[i-1];
            }
        else if (a%10==9)
            for(int i=0;i<=b%2;i++)
            {
                if (b%2==0)
                    number=numbers9[1];
                else
                    number=numbers9[i-1];
            }
        std::cout<<number<<std::endl;
    }
    return 0;
}

Tak oto zmieniłem mój kod i czas uruchamiania programu wg. SPOJ'a jest perfekcyjny, 0.00 :)

---

O super :) Nie byłem w stanie prześledzić Twojej wersji :) Gratuluję zwycięstwa!

Answer 2

,,Dla danych dwóch liczb naturalnych a i b, wyznaczyć ostatnią cyfrę liczby ab."(b było zmniejszone i umieszczone przy górnej granicy linijki)

Ja bym to zrobił tak:

1. Wykonaj potęgowanie.

2. Wczytaj wynik do stringa.

3. Odczytaj ostatni znak stringa, wyświetl. (jeśli trzeba w typie liczbowym to przekonwertuj jak tam chcesz)

Comments

Nie da się tak zrobić, bo wynik będzie przekraczał każdy zakres zmiennej. Więc nie wykonasz potegowania a^b, a wcale nie chodzi o to w tym zadaniu

---

Każdy zakres zmiennej?

Mógłbyś mi wytłumaczyć o co według ciebie chodzi w tym zadaniu? Ja to zrozumiałem tak: weź A, spotęguj B razy, wyświetl ostatnią cyfrę z wyniku.

---

Spoteguj: 1 000 000 000 do 1 000 000 000, bo taki możesz mieć input

---

Edit. ,, W pierwszej linii wejścia znajduje się jedna liczba całkowia D (1≤D≤10), oznaczjąca liczbę przypadków do rozważenia. Opis każdego przypadku podany jest w jednym wierszu, zawierającym dwie liczby naturalne a i b oddzielone pojedynczym odstępem (spacją), takie, że (1 ≤ a,b ≤ 1 000 000 000). "

Myślałem że A może być od 1 do 10.

---

Dalej nie jesteś wstanie obliczyć w/w potęgi.

---

To tam testują do paru miliardów w A i B?

---

Czytałeś całe zadanie?  Tak, input jest do miliarda. Wynik maksymalny będzie miał koło 9000000000 zer, więc tego raczej w żadnej zmiennej nie pomiescisz.

---

Pamięć RAM wymięka przy tej liczbie. Idę spać.