93 / 237
Sep 2016

Aktualnie walczę z innym problemem. Przekraczam limit czasowy. Czytałem post i zauważyłem zależności miedzy potęgami. Wydaje mi się że nie jest to jedyny sposób na rozwiązanie tego zadania. http://ideone.com/n3B6uO35 oto mój kod. Jak masz jakieś pomysły jak go przyspieszyć by się mieścił w limicie czasowym to słucham :slight_smile:

[edit by narbej] ... Post jest skierowany do osób chcących udzielić odpowiedzi/podpowiedzi, ...

Pomogłem już dziesiątkom osób, tobie też dałem odpowiedź, najlepszą z możliwych :slight_smile:
to, że jej nie rozumiesz, to twój problem

Nikt inny raczej tego nawet nie czyta, a tym bardziej jeżeli nie chciałby pomóc.

PS
Beznadziejny przypadek - chodziło o to, że twojego sposobu nie da się przyśpieszyć, nawet jak poczytasz o szybkim potęgowaniu, to twój kod wymaga zbyt dużo poprawek - a chyba chodzi tu też o odrobinę samodzielności, czyż nie?

A szkoda, bo każdy szukający tu pomocy, powinien zawsze najpierw poczytać wątek/[a nawet wątki] poświęcone problemowemu zadaniu. Np: http://discuss.spoj.com/search?q=czy%20umiesz%20pot%C4%99gowa%C4%87 + [plus] http://213.192.104.217/phpBB3-spoj-pl-backup/viewtopic.php?f=1&t=222&hilit=czy+umiesz+pot%C4%99gowa%C4%87&sid=689abcabeb3c4142e274150b75303a4313 a dopiero potem, jeżeli nie znajdzie odpowiedzi, zadawać tu swoje pytanie/a...

Ja Ci podpowiem. Rzeczywiście masz sporo błędów, co nie oznacza, że jesteś głupi, ale przydałoby Ci się trochę lepiej poznać język C++. Może jakaś książka, żeby ugruntować sobie wiedzę? Albo po prostu więcej uwagi, jeśli wiedzę masz. Pierwsze co mi się rzuciło, to w treści zadania masz napisane, że wszystkie dane wejściowe są liczbami całkowitymi. Potem operacje, które na nich wykonujesz dotyczą liczb całkowitych(modulo, dodawanie, mnożenie itp). Wyjścia też są liczbami całkowitymi(cyfra jedności wyniku a^b, gdzie a i b są liczbami całkowitymi dodatnimi). W związku z tym nie należy się spodziewać, by w programie przydały się liczby zmiennoprzecinkowe. Twoje zmienne a i b zadeklarowałeś jako typu double, czyli zmiennoprzecinkowe o podwójnej precyzji, a nie poszerzony zakres int(a przypuszczam, że o to Ci mogło chodzić). Jeśli chodzi o sposób na obliczenie cyfry jedności zauważ, że dla np b=1000000000, instrukcje z pętli będą wykonywały się miliard razy, a limit czasowy wynosi 0.529 sekundy. Nie znam się za bardzo na przełożeniu złożoności obliczeniowej na czas wykonywania, ale już nawet na pierwszy rzut oka taki przypadek śmierdzi baaaardzo długim czasem wykonywania, powyżej 0.529s. Sama idea funkcji nie jest zła. Jeśli chodzi o samo skrócenie czasu wykonywania- gdzieś w temacie wcześniej było poruszone, ale powtórzę podpowiedź: Rozpisz sobie pierwszych 6 potęg liczby 2, zaczynając od 2^1, a kończąc na 2^6 i postaraj się zauważyć powtarzającą się prawidłowość w wyniku w rzędzie jedności. Jeśli nie będziesz w stanie rozwiązać tego zadania po staraniach, prześledź temat, wgryź się w cudze kody i zobaczysz w czym rzecz. Powodzenia:)

Z doublem to był mój błąd który został naprawiony :slight_smile: Zauważyłem zależność miedzy potęgami ( powtarza się co 4). Z tego co napisałeś wynika ze rozwiązać to zadanie można tylko korzystając z tej zależności. Tak czy inaczej dzięki.

Tak, z tym, że wyniki rzędu jedności potęg nie wszystkich cyfr powtarzają się co 4, ale więcej nie napiszę, żeby Ci nie zabierać frajdy i satysfakcji z samodzielnego dochodzenia do rozwiązania. Co do tego jedynego sposobu na rozwiązanie, ten jest jedynym działającym, z którym się spotkałem(pisząc i potem patrząc w parę kodów tutaj), ale może są jakieś inne. Jeśli chodzi o to "czytanie książki", to się powtórzę, ale polecam, z autopsji. Obecnie czytam symfonię c++ i choć na pierwszy rzut oka wszystkie poruszane tematy są oczywiste, co chwila się czegoś dowiaduję czytając to. Trochę się pomądrowałem, ale może znajdziesz w tej wypowiedzi przydatne dla siebie rzeczy. Pozdro:)

Może mi ktoś powiedzieć, czy moje rozwiązanie jest dobre... Tzn testy przechodzą, ale nie wiem czemu dopiero przy zmodulowaniu wykładnika przez 20 testy przechodzą... Czy okres liczby jedności w wszystkich potęgach jest 20 lub jego dzielnikiem?

Summary

include

using namespace std;

long long int pot(int a,int b)
{
if(b==1)return a%10;
else return (a*pot(a,b-1))%10;
}

int main()
{
int x,y,z;
cin>>x;
for(int i=0;i<x;i++)
{
cin>>y>>z;
y=y%10;
z=z%20;
if(z!=0)cout<<pot(y,z)<<endl;
else cout<<"1"<<endl;
}
return 0;
}

Co jest złego z tym kodem? (Jeśli zamierzasz odpowiedzieć poczytaj u góry to oszczędź klawiatury i nie odpisuj ;] )

include

include

using namespace std;
unsigned long long a,b,temp,wynik,ile;
int main()
{
cin>>ile;
for(unsigned int i=1; i<=ile; i++)
{
cin>>a>>b;
temp=pow(a,b);
if(b==1)
{
wynik=a;
}
if (b==0)
{
wynik=1;
}
else{
wynik=temp%10;
}
cout<<wynik;
}
return 0;
}
`

nic nie jest złego - tyle, że poprawnie rozwiązuje tylko niewielki podzbiór możliwych zestawów danych

oczywiście informacja, dlaczego tak się dzieje jest gdzieś powyżej w tym wątku.

z twojego komentarza rozumiem, że nie masz czasu, aby przeczytać cały wątek (lub nie rozumiesz co czytasz)

ja natomiast nie mam czasu po raz n-ty tłumaczyć podstawowych rzeczy

pozdrawiam, i życzę powodzenia

16 days later

Na ideone nie testowałem, tylko na kompie. I na kompie wszystko jest okej. Te przykłady, których użyłeś działają u mnie poprawnie, a na ideone już nie. O co chodzi? :confused:

25 days later

Witam,

poczytałem wszystkie wątki i już mam pomysł na inne rozwiązanie z case'ami :wink: jednak zapisałem to inaczej link14 i zastanawiam się dlaczego mi nie przechodzi.
Wykonałem wszystkie testy jakie tu podajecie i zawsze miałem prawidłową odpowiedź a mimo to dostaję od sędziego błędną odpowiedź :confused:

Byłbym wdzięczny za wskazówkę co zrobiłem nie tak.

wszystkich zamieszczonych tu testów to nie zrobiłeś - sprawdź dla danych zamieszczonych w poście nr. 52

Możesz jaśniej? Bo nie rozumiem.
W 52 jest o if a==0 <- co z założenia jest niepotrzebne, bo liczby są z zakresu 1 <= a <= 1000000000 :wink: a w sytuacji a==1 to moje rozwiązanie też powinno zadziałać; niemniej jednak dodałem if'a dla a==1, ale sędzie i tak nie przepuszcza.

Nie rozumiem, z czym sędzia ma w tej sytuacji problem.

Proszę o wyjaśnienie, nie rozwiązanie, bo chcę zrozumieć co jest złego w moim kodzie. Koduję dopiero tydzień, więc proszę o wzięcie tego pod uwagę przy pisaniu :slight_smile:

Z góry dziękuję za pomoc.

być może źle liczyłem posty :), może to jest 53 - w każdym razie autorem jest j4rooo, podany jest tam test dla około 40 par liczb, dla części z nich masz złe wyniki