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?
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
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 ...
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?
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?
@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-old146
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.com35 i podaj tylko link do swojego kodu. od razu ktoś będzie mógł przeprowadzić testy.
@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.
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..
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?
@bunker96
modulo10 (1000000000002 ** 2) = ?
modulo10 (100000000002 ** 2) = ?
modulo10 (10000000002 ** 2) = ?
modulo10 (1000000002 ** 2) = ?
itd
Czy potrzebujesz całej "a" czy wystarczy jej mały kawałek a może jeszcze mniej a, może wystarczy tylko ociupinka a?