задача

[Ntfser]

ну?

Как обычно после праздников студенты очень быстро устают от процесса обучения. Поэтому когда они заходят в кабинет, то иногда цепляются друг за друга или за парты и падают. Некоторым студентам удаётся подняться и пройти дальше к другой парте. Этот процесс продолжается снова и снова, пока не начнётся пара. Преподаватель по математическому анализу смог вывести закономерность количества студентов упавших под парту. В кабинете стоит N (N <= 200) рядов парт и в каждом ряду по M (M <= 200) парт, образовывая прямоугольник из парт. Препопадатель заметил, что в 0-ом ряду парт падает всегда ровно по одному человеку, зато под 0-ые парты падает по два человека, за исключением парты, которая сама близкая к преподавателю (0; 0) - под неё упало 5 студентов. Затем он вывел общую формулу падения студентов:

P(0, 0) = 5
P(0, k) = 1
P(k, 0) = 2
P(x, y) = (P(x - 1, y - 1) * 3 + P(x - 1, y) + P(x, y - 1)) mod 30000
Нужно помочь учителю определить, сколько упало студентов под парту (x; y) (0 <= x <= N, 0 <= y <= M), т.е. вычислить P(x, y). Ввод/Вывод Пример
x y 3 2
P(x, y) 214

[Ламер_001]

рекурсия... что то типа ханойских башен...
З.Ы. нехило падают то студенты)))

[Ntfser]

я еще школьник это отборачная олимпиада)))) решил все задачи))) кроме этой!!
ps все 40 учасников человек "снято по времени" во всех задачах)))) у всех 0 балов!!! и я прошел)))))))))

просто интересно ее решение)) кто нить знает его?

[Ламер_001]

var n,m:integer;
Function p( x,y :longint): longint;
begin
 if ( (x = 0) and (y = 0) ) then p:=5
 else
 if (x=0) then p:=1
 else
   if (y=0) then p:=2
   else
    p:= (p(x - 1, y - 1) * 3 + p(x - 1, y) + P(x, y - 1)) mod 30000; 
end;

BEGIN
 readln(n,m);
 writeln( p (n,m) );
END.

ну вот вроде. не знаю может при граничных условиях будет многовато но думаю mod не даст выйти. лонгинта должно хватить. а вот что со временем не знаю... вряд ли при границах уложится... еще подумаю как будет время...

[Ntfser]

Function p( x,y :longint): longint;
можно поподробнее что это?

[vvviperrr]

2Ntfser функция называется, потцан)

[Ламер_001]

хм странно куда делся пост. вот в общем решение.

var p:array[-1..200, -1..200] of longint;
    i,j,n,m:longint;

begin
 readln(n,m);
 if n > m then
  for i:=-1 to n do
  begin
   p[i,-1]:= 0;
   p[-1,i]:= 0;
  end

 else
  for i:=-1 to m do
  begin
   p[i,-1]:= 0;
   p[-1,i]:= 0;
  end;
 p[0,0]:=5;

 for i:=1 to n do
  p[i,0]:= 2;
 for i:=1 to m do
  p[0,i]:= 1;

 for i:=1 to n do
  for j:=1 to m do
   p[i,j]:= (3*p[i-1,j-1] + p[i-1,j] + p[i,j-1]) mod 30000;


 writeln(p[n,m]);
 readln
end.

память жрет но работает значительно шустрее рекурсии. если будет вылазить за пределы памяти то хранить надо не всю матрицу а только последние строку и столбец