ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1171. Lost in Space

Could anyone tell me why do I get WA? Here's my program.
Послано shitty.Mishka 23 дек 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?
Послано shitty.Mishka 23 дек 2001 00:09
some test data for you (+)
Послано abc 23 дек 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 (+)
Послано shitty.Mishka 23 дек 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 ...
Послано I have answers to all your questions :) 23 дек 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
Послано shitty.Mishka 23 дек 2001 19:21
Thank you for read(y,x)!
Послано Nemets Ilya 26 дек 2001 18:47