ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1171. Lost in Space

Could anyone tell me why do I get WA? Here's my program.
Posted by shitty.Mishka 23 Dec 2001 00:08
[deleted by moderator]

Edited by moderator 11.04.2004 01:38
What should I output as food ratio if he never gets out?
Posted by shitty.Mishka 23 Dec 2001 00:09
some test data for you (+)
Posted by abc 23 Dec 2001 11:10
2
1 20 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
20 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 4

The output of my program for the above input is:
7.3333
5
WWWDS
Thank you very much, but (+)
Posted by shitty.Mishka 23 Dec 2001 15:58
Your test data was very useful. It turned out that I just had to
change read(x,y) to read(y,x), and my program is working properly.
But now I got Time limit exceeded.
Could you tell me how can I improve my solution? My algorythm is as
follows.
For each floor, from n downto 1, i fill an array
a:array[0..Max*16,1..4,1..4],
and after I filled it for current flor, a[d,x,y] is the maximum
number of food he could bring to the current floor to room (x,y)
after d days from start. Having this information for floor number k,
I, using recursive search, fill such an array for floor number k-1,
and, when this array is filled for floor number 0(which is under
floor 1, and we can go down to it from every room of floor 1), I do
such a cycle:
max:=0;
for i:=1 to 4
 for j:=1 to 4
  for k:=1 to n*16 do
   if a[k,i,j]/k>max then
    max:=a[k,i,j],
so after all this we have he maximum food ratio in variable max. Of
course, there's some more stuff to do to find his way, but this is
not really important - the main thing is how should I change my
algorythm of finding max to make it quick?
I think ...
Posted by I have answers to all your questions :) 23 Dec 2001 16:22
For i:=1 To 4 Do
 For j:=1 To 4 Do Begin
  c[j,i]:=1;
  For k:=0 To Max*16 Do
   If a[k,j,i]>=0 Then
    TryIt(i,j,k,a[k,j,i],c,s[k,j,i]); <= a very big waste of time
  c[j,i]:=0;
  End;

u have to do the recursive search for each (i,j) only :)
Thank you. I will try to change my algorythm
Posted by shitty.Mishka 23 Dec 2001 19:21
Thank you for read(y,x)!
Posted by Nemets Ilya 26 Dec 2001 18:47