Znam da zamaram, ali stvarno ne razumem zasto ovo ne radi:
var i,j,n,k:longint;
odg:longint;
a:array[0..160,0..40]of longint;
begin
readln(n,k);
if k=1 then write(1) else
begin
for i:=0 to k do begin a[0,i]:=0; a[1,i]:=1; end;
for i:=2 to n do
begin
a[i,k]:=a[i-1,k]+a[i-1,k-1];
a[i,1]:=a[i-1,1]+a[i-1,2];
for j:=2 to k-1 do a[i,j]:=a[i-1,j]+a[i-1,j-1]+a[i-1,j+1];
end;
odg:=0;
for i:=1 to k do odg:=odg+a[n,i];
writeln(odg);
end;
end.
Ako me pamcenje ne vara, za dafinu mora da se implementira rad sa velikim brojevima jer elementi matrice izlaze iz opsega longinta :)
A mozes da mi objasnis malku za rad sa velikim brijevima?
Fala odnapred i pozdrav
cifrite na brojot gi cuvas vo niza ili neso takvo i sam definiras mnozenje, sobiranje ili sto ti treba.
Kako se resava?
Kako da doznam koliko ima bonova ciji se susedni brojevi razlikuju za najvise jedan?
Ima neka formula ili nesto drugo.
tnx.
Najverovatnije postoji formula, ali nije ti potrebno. Probaj da nadjes rekurentnu vezu sa duzinom serijskog broja i cifrom kojom se zavrsava. Kad to nadjes, sigurno se moze naci i jednacina koja u zavisnosti od n i k daje resenje (odgovor na pitanje da li postoji neka formula), ali za time nema potrebe, dosta ti je da koristis DP i nadjes resenje.
U primeru n=4 i k=3 jel su to serijske oznake tipa
1 1 1
1 1 2
1 2 1
1 2 2
1 2 3
2 1 1
2 1 2
2 2 1
2 2 2
2 2 3
..........
Jer sam ja tako razumeo, a u tom slucaju ih ima 17 a ne 41. Jel moze neko da mi objasni na ovom primeru koji je dat(n=4, k=3)?
1 1 1 1
1 1 1 2
1 1 2 1
1 1 2 2
1 1 2 3
1 2 1 1
1 2 1 2
1 2 2 1
1 2 2 2
1 2 2 3
1 2 3 2
1 2 3 3
2 1 1 1
2 1 1 2
2 1 2 1
2 1 2 2
2 1 2 3
2 2 1 1
2 2 1 2
2 2 2 1
2 2 2 2
2 2 2 3
2 2 3 2
2 2 3 3
2 3 2 1
2 3 2 2
2 3 2 3
2 3 3 2
2 3 3 3
3 2 1 1
3 2 1 2
3 2 2 1
3 2 2 2
3 2 2 3
3 2 3 2
3 2 3 3
3 3 2 1
3 3 2 2
3 3 2 3
3 3 3 2
3 3 3 3
Ju al sam smotan, 10 puta sam procitao zadatak i nisam skapirao da sam potpuno obrnuo neke podatke i pogresno pisao sebi primere. sorry.
Koje resenje ti je za 100 19?
Kakav sam kreten, resenje sam pisao kao niz shortinta a na jednom mestu u svaki element niza dodam 20 cifara sto u jednom momentu prelazi opseg shortinta a posto tek na kraju sredim izraz, od te tacke pa nadalje mi nista ne valja.
Sad sam sredio, hvala.
suma moze u double do 20 i 20 ali posle:(((((
a sta mislite koji su nacunu da se dalje optimizuje kod
npr ocigledno je da za n=3 npr i k=10 dp[3,3]=dp[4,3]=dp[5,3]=dp[6,3]=dp[7,3]=dp[8,3] i tako tu sigurno moze neka otpimizacjia:D
a i predlazem da se uradi sa nekim modulom bolje jer mrzim taj rad sa velikim brojevima:)
Pa kada zakljucis vezu izmedju stanja u dinamici videces da tebi u svakom trenutku trebaju samo dva reda tako da memorijski optimizujes da ti memorija bude 2 * K i naravno moras velike brojeve jer je resenje stvarno ogromno za velike N i K . :)
da vidim da trebaju 2 nego sam mislio vreme da se optimizuje:D
