Обсуждение @ 1525. Path @ Timus Online Judge

Arthur WA # 7 help me,plz! [13] // Задача 1525. Path 18 фев 2007 18:11

Arthur Re: WA # 7 help me,plz! [2] // Задача 1525. Path 18 фев 2007 19:47

anybody, who knows where can be error! help!

Fokysnik[LNU] Re: WA # 7 help me,plz! [1] // Задача 1525. Path 18 фев 2007 20:13

I'm also getting WA#7... and don't know why :'(

Arthur Re: WA # 7 help me,plz! // Задача 1525. Path 18 фев 2007 21:05

if you will find you mistake, please, write it here! ok?
and if i'll find my, i'll write it here too.

Соболева Оля Re: WA # 7 help me,plz! [5] // Задача 1525. Path 18 фев 2007 23:40

size of ansver is greatest longint.
Use int64.

Fokysnik[LNU] Re: WA # 7 help me,plz! [4] // Задача 1525. Path 19 фев 2007 00:46

Thanks! After your post I managed to solve it.
But, actually I was using int64, but...

I've found out that if you write like this:

ans:=x*y*z; where ans is int64 and x,y,z are integer

you get WA

After I wrote:

ans:=x;
ans:=ans*y;
ans:=ans*z;

I got Accepted.

I think it happens because of calculation x*y*z is performed in integer and then converted to int64.
Interesting... :-|
Should have written in C. I guess I wouldn't have faced this if written in C.

Edited by author 19.02.2007 00:56

Arthur Re: WA # 7 help me,plz! // Задача 1525. Path 19 фев 2007 13:51

Thank you very much!

Kit Re: WA # 7 help me,plz! [2] // Задача 1525. Path 19 фев 2007 16:36

Fokysnik[LNU] писал(a) 19 февраля 2007 00:46

Should have written in C. I guess I wouldn't have faced this if written in C.

It's common feature of all compilers I know. I guess, C would not help you also :)

Index Tree Re: WA # 7 help me,plz! [1] // Задача 1525. Path 19 фев 2007 21:12

Can anyone pls explain to me the sample output on test 3

Olly Re: WA # 7 help me,plz! // Задача 1525. Path 23 фев 2007 19:18

I had wa7 too. be carefull

printf("%lld\n",ans) IS WRONG!
printf("%I64d\n",ans) is OK

for MSVS2005 it's no matter, but not for Timus compiler

Petr Huggy (Pskov) Re: WA # 7 help me,plz! [1] // Задача 1525. Path 20 май 2010 17:44

In test #7 the second line (instructions' string) is empty!

gautamvs Re: WA # 7 help me,plz! // Задача 1525. Path 16 июл 2013 22:54

the problem could be reading the line with 10^5 characters.

huysgori Re: WA # 7 help me,plz! [1] // Задача 1525. Path 5 май 2022 14:47

How can we read a line of 10^5 chars in python and not get a runtime error?

Vladislave Re: WA # 7 help me,plz! // Задача 1525. Path 6 май 2022 01:08

use sys.stdin instead of input()

Felix_Mate WA 8. [5] // Задача 1525. Path 4 янв 2016 17:48

const Nmax=111111;
var
path:array[1..Nmax] of char;
N,M,K,pic,d,dmax,i,L,now:longint;
ch:char;
ans1,ans2,ans3:int64;

begin
readln(N,M,K);
L:=0;
read(ch);
while(ch='u')or(ch='d')or(ch='r')or(ch='l')or(ch='f')or(ch='b') do begin
inc(L);
path[L]:=ch;
read(ch);
end;

pic:=1;
d:=1;
dmax:=1;
now:=1;
for i:=1 to L do begin
if(path[i]='l') then begin
   if(now=1) then begin
    inc(d);
    if(dmax<d) then dmax:=d;
   end
   else begin
    dec(now);
    if(now=1) then begin
     d:=1;
     if(dmax<d) then dmax:=d;
    end;
   end;
end;
if(path[i]='r') then begin
   if(now=N) then pic:=N
   else begin
    inc(now);
    d:=0;
    if(now>pic) then pic:=now;
   end;
end;
end;

ans1:=1;
i:=2;
while(i<=N)and(pic<N) do begin
if(i-1>=dmax) then inc(pic);
if(i-1>=dmax)and(pic<=N) then inc(ans1);
inc(i);
end;

pic:=1;
d:=1;
dmax:=1;
now:=1;
for i:=1 to L do begin
if(path[i]='d') then begin
   if(now=1) then begin
    inc(d);
    if(dmax<d) then dmax:=d;
   end
   else begin
    dec(now);
    if(now=1) then begin
     d:=1;
     if(dmax<d) then dmax:=d;
    end;
   end;
end;
if(path[i]='u') then begin
   if(now=M) then pic:=M
   else begin
    d:=0;
    inc(now);
    if(now>pic) then pic:=now;
   end;
end;
end;

ans2:=1;
i:=2;
while(i<=M)and(pic<M) do begin
if(i-1>=dmax) then inc(pic);
if(i-1>=dmax)and(pic<=M) then inc(ans2);
inc(i);
end;

pic:=1;
d:=1;
dmax:=1;
now:=1;
for i:=1 to L do begin
if(path[i]='b') then begin
   if(now=1) then begin
    inc(d);
    if(dmax<d) then dmax:=d;
   end
   else begin
    dec(now);
    if(now=1) then begin
     d:=1;
     if(dmax<d) then dmax:=d;
    end;
   end;
end;
if(path[i]='f') then begin
   if(now=K) then pic:=K
   else begin
    d:=0;
    inc(now);
    if(now>pic) then pic:=now;
   end;
end;
end;

ans3:=1;
i:=2;
while(i<=K)and(pic<K) do begin
if(i-1>=dmax) then inc(pic);
if(i-1>=dmax)and(pic<=K) then inc(ans3);
inc(i);
end;

write(ans1*ans2*ans3);
end.

Рассуждения такие:
1)как только достигнуто значение верхней границы,то все последующие шаги бессмысленны,т.к. пути совпадут;
2)пока первые i точек попадают в минимум у 1-ой точки (т.е. можно построить график зависимости номера шага от его значения,причем за пределы значений нельзя выходить и потому строим график в этом случае параллельным оси шага),их всех(кроме 1-ой точки) не засчитываем,все оставшиеся(если есть) и дают ответ;
3)всё перемножаем.

Jane Soboleva (SumNU) Re: WA 8. [4] // Задача 1525. Path 4 янв 2016 19:12

Сложновато как-то... моя var-секция выглядит так:
var x, y, z: int64;
    curlr, minlr, maxlr: longint;
    curdu, mindu, maxdu: longint;
    curbf, minbf, maxbf: longint;
    c: char;
begin
...

UPD: да, и ещё, рекомендую всё-таки
    while not eoln do begin
        read(ch); ...
вместо
    read(ch);
    while(ch='u')or(ch='d')or(ch='r')or(ch='l')or(ch='f')or(ch='b') ...
Потому что этот второй цикл означает, что в какой-то момент будет произведена попытка считать ещё один символ, когда всё уже считано. У меня этот код при тестировании на файле иногда работает, а иногда выдаёт рантайм 201. Но если в конце второй строки делать Enter, переход на новую, то конечно проблем не возникнет, но ведь в тестах этого не гарантируется.

UPD:
Вот простейший тест, на котором валится. Почему именно неправильно работает, не скажу, слишком сложные вычисления какие-то.
8 1 1
llllrrrr
4 (правильно.)
8 1 1
llllrrrrrrrr
1 (правильно.)
8 1 1
rrrrllllllll
4 (неправильно.)

Edited by author 04.01.2016 20:59

Felix_Mate Re: WA 8. [3] // Задача 1525. Path 4 янв 2016 23:26

Изменил прогу,всё равно WA.
Jane Soboleva (SumNU),я правильно рассуждаю?:я ищу 3 максимума-dmax-максимальное время,когда мы были в 1,maxb-максимальное смещение(вправо от 1) до dmax,maxa-максимальное смещение вправо уже после dmax. Т.е. если строить график пути,то r означает поднятие по оси OY,а l-спуск.Тогда мы как бы начинаем в 1 и с шагом 1 то увеличиваем ординату,то уменьшаем,причем попав в 1 мы не можем идти вниз,а потому движемся вправо,то же и с N.В итоге я ищу максимальную высоту до "ямы" длиной dmax и после. Потом рассматриваю точки i>=dmax+1,т.к. все точки меньшие попадают в яму и потому все пути совпадут.Остальные точки смещены на dmax от графика первой точки и потому они дают новые пути,если не проходят через N(ровно одна из них может проходить),т.к. значения возрастают и потому пути снова совпадут.

Jane Soboleva (SumNU) Re: WA 8. [2] // Задача 1525. Path 5 янв 2016 01:36

Не уверена~
К сожалению, я сейчас не в состоянии сказать, насколько эти рассуждения правильные.

У меня алгоритм был такой: я поместила робота в условную точку (0, 0, 0) бесконечного параллелепипеда, а потом просто двигаю его согласно заданной строке, параллельно отмечая самое дальнее расстояние в каждом из измерений, которое он достигает в процессе.
То есть, к примеру, после rrlllll будет minlr = -3 и maxlr = 2, и расстояние = maxlr - minlr = 5 (2 - -3). И так я считаю для каждого из трёх измерений. После всего этого я получаю три таких расстояния, и вычитаю их из соответствующей им размерности измерения, а потом все эти три числа перемножаю. Вот и всё.
Ну и единственный нюанс — надо проследить, чтобы каждый из трёх множителей не опустился ниже единицы, то есть хотя бы одна позиция должна остаться. Например, у нас по left/right размерность 5, и у нас lrrrrrrrr, получатся minlr -1, maxlr 7, 7 - -1 = 8, 5 - 8 = -3, -3 меньше 1, поэтому вместо -3 мы подставляем 1 при умножении.

Edited by author 05.01.2016 01:39

Felix_Mate Re: WA 8. [1] // Задача 1525. Path 5 янв 2016 13:36

Спасибо за идею! Правда я не совсем понял корректность,но решил по-своему: как и ты(или Вы?) нашёл максимальное смещение влево и вправо,а потом осознал,что нас интересуют такие i,что 1-minlr<=i<=N-maxlr(это получается из системы i+maxlr<=N-кол-во i,не выходящих за правую границу и i-minlr>=1-за левую;все пути остальных i совпадут в конечной точке,а если же таких i нет=> все они выходят по крайней мере за одну границу и ответ 1).

Кстати,из таблицы рейтинга решений видно,что ученик превзошёл учителя)))

Edited by author 05.01.2016 13:38

Jane Soboleva (SumNU) Re: WA 8. // Задача 1525. Path 5 янв 2016 20:41

Можно на ты :)
Поздравляю!~
Да, в этот раз решение уже более похожее на моё.
Насчёт памяти — у меня даже на задачу A+B не получается тратить меньше 140кб сейчас, хотя у некоторых, я вижу, выходит около 80 и меньше. Возможно, надо просто отключать или менять какие-то директивы компилятора, но я с этим не заморачивалась.

qwerty Admins!!! Java Crash [2] // Задача 1525. Path 7 сен 2008 00:47

Index Tree Can you explain the sample output [3] // Задача 1525. Path 18 фев 2007 19:07

Dan George Filimon broken test data? [1] // Задача 1525. Path 5 янв 2008 17:16

Kollekcioner[Vologda, VML1] WA8 [1] // Задача 1525. Path 7 авг 2007 22:05

lijian Why I WA test4?? [2] // Задача 1525. Path 19 фев 2007 10:56

lijian Why example?? [5] // Задача 1525. Path 21 фев 2007 14:55

Anton [SUrSU] Meaning of "position" // Задача 1525. Path 21 фев 2007 17:43

Duzhy Igor Please, give me some hints [4] // Задача 1525. Path 20 фев 2007 14:33

Bot Explain please input test #3 // Задача 1525. Path 18 фев 2007 17:08

Обсуждение задачи 1525. Path