Witam.
zadanie jest takie
jest sobie Ciąg którego następne wyrazy równają sie a(n+1)=2* a(n)-a(n-3) (z tym że pierwsze 4 wyrazy śą już podane) .... a ja mam obliczyc sumę x wyrazów ;
na szczęśćie intestują mnie tylko 5 ostatnich cyfr tej sumy..
gdyby to byly małe liczby to nie bylo by problemu ale niestety szybko przekraczają zakres long int ... i co dalej.. ?? help
Na szczęście wszystkie te działania są "porządne" względem modulo, tzn. a(n+1) mod 100000 = 2 * (a(n) mod 100000) - (a(n-3) mod 100000).
niestety to co podałes jest błędne bo np.
jeżeli (a(n) mod 100000) = 24
a (a(n-3) mod 100000) = 456
to a(n+1) bedzie równe -408
a jeżeli a(n) bylo równe 200024
a(n-3) było równe 100456
więc wynik powinie byc 299592 czyli (99592)
naszczęście sobie juz z tym poradziem ... ale mam następny problem ... optymalizacja ... a więc
zadanie w pelni wygląda tak :
http://opss.safo.biz/?menu=comp&sub=prob&comp=8&prob=1101
a mój kod to
int tab[51]={0};
int p,k;
int N;
int skruc (int sum){ // skraca ona liczbe sum tak aby bylo 5 cyfr
return (sum %100000);
};
int ciag(){
int suma=0;
int ost=1;
int aktu=1;
int aktut=1;
int aktut2=1;
tab[N+1]=0;
for(int i=1; i<=N;i++) // obliczany kolejny wyraz
tab[N+1]+=tab[i];
N++;
while(1){
if(aktut==52) aktut=1; // jezeli wyjdzie poza tablice to spowrotem
aktut2=aktut-1;
if(aktut2<1) aktut2=51;
if(ost==52) ost=1;
if(aktu>N){ //jezeli wyszedl poza zbiór poczatkowych wyrazów to oblicz następny
tab[aktut]=skruc(200000+2*tab[aktut2]-tab[ost]);//wystarczylo dodać 200000 zeby bylo ok:D
ost++;
}
if (aktu>k) break; //jeżel obliczny wyraz jest już pozad k to koniec
if (aktu>=p) suma+=tab[aktut]; // jeżelia aktu wyraz jest większy od p to dodaj do sumy
suma=skruc(suma); // skracanie do 5 cyfr sumę
aktu++; //i nastepnyy wyraz
aktut++;
}
return suma;
}
nie stety czas jest max 3 s
a przy danych
1
4
2 3 4 5
1 99999999
wynik jest dobry ale czeka sie na niego grubo ponad 3 s (ok 15 sekund)... help
To co podalem nie jest bledne. (-408 == 99592) mod 100000
Do 123 elmo123:
tak się składa, że ja zrobiłem zadanie ciąg na opssie i tego twojego kodu NIGDY NIE ZOPTYMALIZUJESZ tak, żeby on przeszedł... żaden taki brutal nie ma najmniejszych szans przejść przez te limity. moje rozwiązanie opiera się na binarnym potęgowaniu odpowiednich macierzy ; p także najpierw trzeba być biegłym w binarnym potęgowaniu, potem w mnożeniu macierzy, a potem jeszcze znaleźć odpowiednią macierz T_T zadanie nie jest więc takie proste, na jakie wygląda
czy to zadanie jest jeszcze zadaniem konkursowym?
Nie, można je tylko wysyłać w zawodach stałych, czyli o pietruszkę ;]