Discussion of Problem 1525. PathShow all threads Hide all threads Show all messages Hide all messages | WA # 7 help me,plz! | Arthur | 1525. Path | 6 May 2022 01:08 | 14 | anybody, who knows where can be error! help! I'm also getting WA#7... and don't know why :'( if you will find you mistake, please, write it here! ok? and if i'll find my, i'll write it here too. size of ansver is greatest longint. Use int64. 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 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 :) Can anyone pls explain to me the sample output on test 3 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 In test #7 the second line (instructions' string) is empty! the problem could be reading the line with 10^5 characters. How can we read a line of 10^5 chars in python and not get a runtime error? use sys.stdin instead of input() | WA 8. | Felix_Mate | 1525. Path | 5 Jan 2016 20:41 | 6 | WA 8. Felix_Mate 4 Jan 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)всё перемножаем. Re: WA 8. Jane Soboleva (SumNU) 4 Jan 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 Изменил прогу,всё равно 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(ровно одна из них может проходить),т.к. значения возрастают и потому пути снова совпадут. Re: WA 8. Jane Soboleva (SumNU) 5 Jan 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 Спасибо за идею! Правда я не совсем понял корректность,но решил по-своему: как и ты(или Вы?) нашёл максимальное смещение влево и вправо,а потом осознал,что нас интересуют такие i,что 1-minlr<=i<=N-maxlr(это получается из системы i+maxlr<=N-кол-во i,не выходящих за правую границу и i-minlr>=1-за левую;все пути остальных i совпадут в конечной точке,а если же таких i нет=> все они выходят по крайней мере за одну границу и ответ 1). Кстати,из таблицы рейтинга решений видно,что ученик превзошёл учителя))) Edited by author 05.01.2016 13:38 Re: WA 8. Jane Soboleva (SumNU) 5 Jan 2016 20:41 Можно на ты :) Поздравляю!~ Да, в этот раз решение уже более похожее на моё. Насчёт памяти — у меня даже на задачу A+B не получается тратить меньше 140кб сейчас, хотя у некоторых, я вижу, выходит около 80 и меньше. Возможно, надо просто отключать или менять какие-то директивы компилятора, но я с этим не заморачивалась. | Admins!!! Java Crash | qwerty | 1525. Path | 12 Jul 2011 13:25 | 3 | I solved this problem both at java and c++ and got ac only at c++, java version get CRASH 7. Why ? And I found the solution. Just look for an empty command sequence. | Can you explain the sample output | Index Tree | 1525. Path | 10 May 2009 01:53 | 4 | I can't understand why the sample output on test3 is 13*12*10 i think it should be 13*13*10 Edited by author 18.02.2007 23:39 Edited by author 18.02.2007 23:39 What's the difference? 13*12*10=12*13*10=1560 There is a mistake =) Look at prev post What's the difference? 13*12*10=12*13*10=1560 What's the difference? 13*12*10=12*13*10=1560 There is a mistake =) Look at prev post "I can't understand why the sample output on test3 is 13*12*10 i think it should be 13*13*10" | broken test data? | Dan George Filimon | 1525. Path | 5 Jan 2008 22:50 | 2 | i am fairly sure my solution should work and definitely sure it should pass the first test. however it constantly gets wrong answer at test #1. is there anything special in test case 1? | WA8 | Kollekcioner[Vologda, VML1] | 1525. Path | 2 Oct 2007 03:37 | 2 | WA8 Kollekcioner[Vologda, VML1] 7 Aug 2007 22:05 Anybody, help!!! I have WA8, but do not understand why??? Plz, can you give me some test? I m also getting WA8 kindly help .. | Why I WA test4?? | lijian | 1525. Path | 14 May 2007 01:43 | 3 | Why I WA test4?? why?????????????? if you know,please tell me!! thank you!! May be you have to use int64 ? | Why example?? | lijian | 1525. Path | 21 Feb 2007 20:59 | 6 | why example 1: 1 1 1 uuuur I think it should be 0!! See problem statment: "If the instruction tells the robot to go outside the room, the robot ignores this instruction." er.... I don't understand what question want to ask!! please give me a example!! Edited by author 21.02.2007 19:00 Let's start from the point (1, 1, 1). After first move we will be at the same point (because we can't go outside the room at point (1, 2, 1)). And so on... After all we will be in the position (1, 1, 1). That is the only possible final position. So answer is 1. Can you please explain why sample input 3 is 13*12*10 or it will solve the task ? You can simply write program to check all possible starting points, so you will see that true answer is :) | Meaning of "position" | Anton [SUrSU] | 1525. Path | 21 Feb 2007 17:43 | 1 | What does it mean? And why the sample result #1 is 1? | Please, give me some hints | Duzhy Igor | 1525. Path | 20 Feb 2007 23:42 | 5 | Who can explain me how to solve this problem? Firstly try to solve similiar problem in one dimension. Then you will find 3D-answer easily. Good luck! I know how to generalize solution of 1-dimensional problem to case 3d, but i can't solve 1-dimensional problem :) I think it's a "not hard combinatorial task" but I cannot get the sample output on test 3, it think it should be 13*13*10 In one dimension is enough to find final positions of left and right ends of segment only. All coordinats between these positions are achievable. | Explain please input test #3 | Bot | 1525. Path | 18 Feb 2007 17:08 | 1 | I cannot understand the task of this problem. Please help me. |
|
|