ruban's blog

By ruban, 12 years ago, In Russian
Много раз пытался сдать 198B - прыжки по стенам. Вроде бы вполне осмысленное решение  -
  • код ниже — получает RE на 12 тесте. Но это не самое интересное — я поглядел 12 тест и
    обнаружил, что на том же тесте с длиной прыжка 56465 все нормально, а при длине 56466 — уже RE. Но и это не все. Мистика (для меня) состоит в том, что при чистке кода я обнаружил, что при удалении ненужных (нигде не используемых) переменных это самое число 56465 изменяется на несколько сотен. Я, естественно, понимаю, что один дурак может задать столько вопросов, что тысяча мудрецов не ответит, но все же, может кто что подскажет... (Для меня это — третья по счету задача с использованием рекурсии, а может и не в рекурсии дело). Заранее благодарен за подсказку.

program pr1;

{$APPTYPE CONSOLE} var n,k,i,j:longint; t:array[0..1,0..1000000] of int64; flag:boolean; marked: array [0..1,0..1000000] of boolean; sss:array[0..1] of string;

procedure dfs(num,pl,shag:longint); var i,p:longint;

begin if shag<pl then begin marked[num,pl]:=true; inc(shag); t[num,pl]:=shag; if not marked[1-num,pl+k] and (sss[1-num,pl+k]='-')and(pl<=n) then dfs(1-num,pl+k,shag); if not marked[num,pl+1] and (sss[num,pl+1]='-')and(pl<n+k) then dfs(num,pl+1,shag); if not marked[num,pl-1] and (sss[num,pl-1]='-')and(pl>1) then dfs(num,pl-1,shag); end;

end;

begin {assign (input,'input.txt');reset(input); assign (output,'output.txt'); rewrite(output); } readln(n,k); readln(sss[0]);readln(sss[1]); for i:=1 to 100000 do sss[0]:=sss[0]+'-'; for i:=1 to 100000 do sss[1]:=sss[1]+'-'; for i:=0 to n+k do begin t[0,i]:=1000000; t[1,i]:=1000000; end; t[0,1]:=0; dfs(0,1,0); flag:=false; for i:=n+1 to n+k do if (t[1,i]<1000000) or (t[0,i]<1000000) then begin flag:=true; end; if flag then write('YES') else write('NO'); close(output); end.

  • Vote: I like it
  • -8
  • Vote: I do not like it