Cod sursa(job #33831)

Utilizator johnyJohny Deep johny Data 19 martie 2007 20:48:00
Problema 1-sir Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.67 kb
{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.