Pagini recente » Monitorul de evaluare | Cod sursa (job #2274734) | Cod sursa (job #855969) | Cod sursa (job #227640) | Cod sursa (job #33831)
Cod sursa(job #33831)
{1-sir
(problema usoara, clasele 11-12)
Prima observatie este aceea ca valoarea maxima
pe care o poate lua S este N * (N-1) / 2,
sirul s fiind egal cu (0, 1, 2... N-1), iar
valoarea minima -N * (N-1) / 2, caz in care
sirul este egal cu (0, -1, -2... -(N-1)).
Daca notam cu D[N][S] numarul de 1-siruri cu
N termeni care au suma elementelor S, atunci se observa ca
D[N][S] = D[N-1][S-(N-1)] + D[N-1][S+(N-1)],
deoarece avem doua posibilitati de alegere pentru al
doilea element (1 sau -1), si fiecare alegere poate fi
interpreta ca o translatie pentru fiecare din elementele
urmatoare cu 1 sau -1 ( deci in total o translatie in
functie de suma de N-1, cu plus sau cu minus ). Pentru
a evita folosirea indicilor negativi pentru suma este
suficient sa observam ca D[N][S] = D[N][-S],
pentru orice S > 0, relatie evidenta din faptul ca se
poate forma o bijectie intre 1-sirurile cu suma S si
cele cu suma -S printr-o simpla inmultire cu -1. Pentru
ca algoritmul sa se incadreze in limita de memorie este
suficient sa retinem doar ultimele doua linii din
tabloul D. Un astfel de algoritm are complexitate O(N^3)
si obtine punctajul maxim.
}
program sir1;
const max=256;
r=194767;
var A,B: array[0..max*(max-1)div 2] of longint;
N,S: longint;
i,j: longint;
rez: longint;
begin
assign(input,'1-sir.in');
reset(input);
readln(N,S);
close(input);
A[0]:=1;
if S>n*(n-1)div 2 then rez:=0
else
begin
for i:=2 to N do
begin
for j:=1 to i*(i-1)div 2 do
B[j]:=(A[abs(j-(i-1))]+A[j+(i-1)])mod r;
A:=B;
end;
rez:=B[s];
end;
assign(output,'1-sir.out');
rewrite(output);
writeln(rez);
close(output);
end.