499. Czy umiesz potęgować [PA05_POT]

[hiraki]

Witam, myśląc nad tym zadaniem stwierdziłem, że rozwiążę je w ten sposób, że po prostu będę potęgował jedynie liczby jedności podanych liczb (przy czym gdy wykładnikiem będzie 10 będzie oddzielny warunek), jednakże sprawdzając sobie te zależności/powtórzenia podczas potęgowania zauważyłem, że te zależności sprawdzają się tylko do pewnego momentu, gdy wykładnik będzie odpowiednio duży to po prostu liczbą jedności będzie zero i tu się pojawia problem, bo gdybym potęgował tylko jedności to tego zera nie uzyskam, co z tym fantem zrobić? Czy ktoś ma jakieś wskazówki bądź rozwiązał to zadanie?

[narbej]

Czy ktoś ... rozwiązał to zadanie?

Tak. To zadanie na razie rozwiązało 4667 osób: http://pl.spoj.com/ranks/PA05_POT/
Napisz sobie taki, lub podobny program i potestuj [powpisuj 2, 12, 22, 32, 42 itd]:

int main(){
	unsigned long long wynik;
	int i, n;
	while(1){
	do {
		cout << "Podaj liczbę z zakresu [2 .. 111]\n[ujemna lub ctrl+c, przerywa program]:\n";
		cin >> n;
		if (n < 0) return 0;
	} while (n > 111 || n < 2);
	wynik = i = 1;
	while(wynik < ULONG_LONG_MAX/n)
	   cout << n << "^" << i++ << "\t= " << (wynik *= n) << endl;
	cout << endl;   
   }
}

Potem zmień pętlę np na: for (int i = 1: i < 20; ++i) ..........
i możesz dodać w pętli warunek: if (wynik> 10) wynik /= 10; Gdy będziesz "bawił się" liczbami mniejszymi od 10, będzie ok, przy większych musiałbyś wymyśleć coś sprytniejszego

[hiraki]

Dobra już widzę swój błąd po prostu kalkulator w którym sprawdzałem te powtórzenia wychodził poza zakres i dlatego wywalał dla pewnych potęg zera na końcu, dzięki/

[hiraki]

include

using namespace std;

int jednosc(unsigned long long, unsigned long long);

int main()
{
int n;
cin >> n;
unsigned long long* pierwsza = new unsigned long long[n];
unsigned long long* druga = new unsigned long long[n];

for(int i=0; i<n; i++)
{
    cin >> pierwsza[i];
    cin >> druga[i];
}

for(int i=0; i<n; i++)
        cout << jednosc(pierwsza[i], druga[i]) << endl;

delete[] pierwsza;
delete[] druga;
return 0;

}

int jednosc(unsigned long long a, unsigned long long b)
{
if(b==0) return 1;
else if(b==1) return (a%10);
a%=10;
int x=a;
if(b>10) b%=10;
for(unsigned int i=1; i {
x*=a;
x%=10;
}
return x;
}

Sknociłem coś takiego, niestety nie przyjmuje(błędna odpowiedź). Jakieś sugestie?

[sig]

Wypisz sobie po 10 pierwszych potęg liczb od 1 do 10, i spójrz na ostatnie cyfry. Swoją drogą po co ci te tablice? Możesz przecież wywoływać funkcję jednosc od razu po wczytaniu liczb. Wejście i wyjście to 2 różne rzeczy, "mieszają się" tylko jak testujesz źle czyli wpisując wejście "z palca"

[hiraki]

Wypisałem sobie te potęgi i się oczywiście powtarzają oczywiście zauważyłem to wcześniej i jest to uwzględnione w programie.
Co do input output test na spoju nie wywali błędu gdy od razu zacznę wypisywać? W poleceniu jest najpierw input wszystkich danych a po tym output

[sig]

Nie. Input jest wczytywany z pliku, a output zapisywany do pliku później porównywanego z "wzorcem". Tak więc żadnych błędów nie będzie, sam nigdy nie buforuję wyników tylko wypisuję od razu gdy je ustalę. Wejście zaś idzie do tablicy tylko jeśli inaczej nie da się zrobić tego zadania.

[narbej]

Bardzo dobrze napisane. "Sknociłem coś takiego"

Wypisałem sobie te potęgi i się oczywiście powtarzają oczywiście zauważyłem to wcześniej i jest to uwzględnione w programie.

Może i zauważyłeś, ale w programie uwzględniłeś, tak jak zacytowałem wyżej
Więc może przyjżyj się jeszcze raz ale dużo dużo [bardzo mocno] uważniej:

In [242]: 2**11
Out[242]: 2048

In [243]: 2**1
Out[243]: 2

In [244]: 2**12
Out[244]: 4096

In [245]: 2**2
Out[245]: 4

[jaromir]

Witam. Czy ktoś ma pomysł jak usprawnić ten kod żeby szybciej działał program? :

include

using namespace std;
int a,b,c,d;
int poteg(int* p, int* w)
{
int iloczyn=1;
for (int i=1; i<=*w;i++)
{
iloczyn =iloczyn* (*p);
}
return iloczyn;
}

int main()
{

cin>>d;
for (int i=1;i<=d;i++)
{cin>>a>>b;
cout<<poteg(&a,&b)%10<<endl;}
return 0;

}

Kompiluje się wszystko dobrze, ale na SPOJu wyskakuje że przekroczono limit czasu ...

[sig]

Poczytaj posty nad twoim, jest tam prawie że wprost napisane jak poprawnie rozwiązać to zadanie.

[hiraki]

Dziękuję za pomoc mimo moich głupich błędów.
Tym razem nie sknociłem, a napisałem taki oto kod

Spoj mi go przyjął.
Co o nim myślicie czy jest to właściwy sposób na rozwiązanie tego zadania?

[narbej]

Raczej nie umieszczaj na forum kodów AC. Wyjątkowo w takim wypadku, ale natychmiast po ocenieniu, lub nawet jeżeli nikt tego nie zrobi, po paru dniach koniecznie usuń. Jedną z wad SPOJ'a jest to, że nie daje odpowiedzi i podpowiedzi na temat czystości kodu, a tylko zalicza albo nie. Swoją drogą polecam książkę właśnie o takim tytule ale także dowolną o programowaniu. Także oglądanie, czytanie i rozumienie kodów napisanych przez innych na pewno przyda się w razie takich wątpliwości i problemów.

Co otwoim kodzie myśli SPOJ już wiesz. Co ja myślę ....

• zastąp wszędzie unsigned long long intem
• usuń if(b==0) return 1;
  usuń else if((a%10)==5) return 5;
  usuń else if((a%10)==6) return 6 na a %= 10;
  mógłbyś teraz zrobić if(a==2 || a ==3 ....) ale po co?
  właściwie usuń wszystko do pętli, a zostaw tylko trzy odpowiednie linijki.
  Czy jeżeli 2 jest liczbą parzystą, to tak samo a nawet dwa razy bardziej parzystą jest też liczba 4?
  Czy taka podobna analogia nie występuje tu: b=(b%4)+4, b=(b%2)+2
  Jeżeli tak, to czy nie możesz tego zrobić bezwarunkowo, wybierając tylko jedną opcję?
  W pętli "powstaną" tak małe potęgi, że możesz zrezygnować z % w środku pętli,
  dopiero zwracając potraktuj %

PS
Częściowo pisałem pewnego rodzaju szyfrem, abyś sam trochę pokombinował, ale teraz chyba domyślasz się co myślę o twoim kodzie?

[forestek1]

Ja zauważyłem że ostatnia cyfra przy potegowaniu powtaża się co 4 potege. Może też byc cały czas taka sama ale na pewno każda cyfra powtaża się co czwartą potęgę. Więc wymyśliłem tak:

#include <iostream>

using namespace std;
int a, b, ile;
int reszta;
int main()
{
    cin >> ile;
    for (int i=1; i<=ile; i++)
    {
        cin >> a >> b;
        reszta=b%4;
        switch(reszta)
        {
        case 0:
        {
            cout << (a*a*a*a)%10 << endl;
        }
        break;
        case 1:
        {
            cout << a%10 << endl;
        }
        break;
        case 2:
        {
            cout << (a*a)%10 << endl;
        }
        break;
        case 3:
        {
            cout << (a*a*a)%10 << endl;
        }
        break;
        }
    }

cout << reszta << endl;

return 0;
}

Na kompilatorze działa, a SPOJ mówi o będnej odpowiedzi. Widzi ktoś błąd w moim rozumowaniu?

[tycjan]

@forestek1
Zauważyłeś dobrze ale nie zauważyłeś że np. milion^4 nie policzy bo wyjdziesz po za obszar nawet unsigned long long inta, którego i tak powinineneś użyć bo w tym zadaniu wartości danych testowych są bardzo duże. Podpowiem tak to da się rozwiązać na warunkach ALE też trzeba coś ZAUWAŻYĆ, najlepiej w tym zadaniu użyć szybkiego potęgowania modularnego (bodajże na khanacademy jest to dobrze wyjaśniona zasada) Jak dobrze poszukasz to znajdziesz nawet gotową implementacje którą sam testowałem i przechodziła, Nie przeraź się ale większość dobrych implementacji potęgowania modularnego, używa przesunięcia bitowego. Piszę trochę podpowiedziami ale nie chcę Ci popsuć satysfakcji z samodzielnie rozwiązanego zadania. Co do twojego kodu to zacząłbym od początku. Ew. możesz poszukać na starym forum wątku z tym zadaniem link do starego forum -> pl.spoj.com/forum-old

EDIT: Taka uwaga na przyszłość jeśli wrzucasz swój kod na forum, to go sformatuj żeby był czytelniejszy (nikomu nie chce się czytać niesformatowanych kodów, jeśli korzystasz z (codeblocksa użyj wtyczki format use AStyle)), umieść z tagach a najlepiej to wrzuć na ideone.com i podaj tylko link do swojego kodu. od razu ktoś będzie mógł przeprowadzić testy.

[narbej]

Ta, poniższa, linia jest "bardzo błędna" i nie na miejscu

cout << reszta << endl;

No i częściowo to co napisał tycjan, [to co dotyczyło a], ale czy potrzebujesz "całego a"? Może wystarczy Ci tylko jego mała ociupinka?

[tycjan]

@narbej @forestek1
To miała być ta podpowiedź, Można rzec że jeśli chodzi o postać bitową danego wyrażenia to komputerowi jest nazwijmy "obojętne" (w przypadku tego zadania) czy liczy milion^2 czy np 100^2.

[narbej]

Jeżeli nawet wcześniejszą podpowiedź zrozumiałem, to tego co napisałeś nie tylko, że nie rozumiem, to nawet nie staram się zrozumieć Co ma piernik do wiatraka. Całe szczęście, że @forestek1 chyba już zaliczył to zadanie bez naszej pomocy, A to co chciałeś powiedzieć, to:
pewnie to, że:
2^10 == 1 << 10
czy
2^30 == 1 << 30
ale bez przesady z tymi milionami i nawet, jeżeli komputerowi jest to zupełnie obojętne, [w tym zadaniu] to programiście już nie powinno.
Powtarzam, że zupełnie nie rozumiem tego co chcesz powiedzieć. Akurat w tym zadaniu reprezentacja bitowa, powiedziałbym, że zupełnie nie ma znaczenia. Tylko takie, że komputer zawsze tak liczy, na bitach Oczywiście, że to zadanie można zrobić, korzystając z szykiego potęgowania modularnego, [sam tak zrobiłem w pierwszej wersji] ale można też tak jak właśnie zrobił to @forestek1 - po poprawieniu drobnych błędów w jego kodzie, więc nie powinieneś radzić mu, aby zaczynał od początku..

[bunker96]

Witam serdecznie,
Napisałem kod, który przy moich testach zwracał właściwe odpowiedzi jednak sędzia go nie uznał. Kod wygląda tak:

Proszę wyjaśnijcie mi gdzie robię błąd

edit poprawilem skrypt, przetestowalem na liczbach od narbeja i rzeczywiscie cos jest nie tak. Tylko nie mam pojecia co.
Jesli chodzi o dlugosc, w tresci jest ze powinno wystarczyc unsigned int.
Mimo tych poprawek kod nadal nie dziala. Moze moje zalozenie jest bledne?

[sig]

Na początek int to za mało, na wejściu mogą się pojawić liczby do miliarda więc potrzebujesz longa. Po drugie algorytm do napisania od nowa, ten tu jest chyba za wolny

[narbej]

No obleci, nie taki on znowu wolny
Ale tak jak napisałeś [@sig] int za mało - long long
scanf("%lld %lld", a, b)//& &

@bunker96
Dodatkowo pomyśl nad np takim testem:
2
1000000000002 2
10000000000000003 2
itd