| ENG RUS | Timus Online Judge |
Обсуждение задачи 1254. Крепкий орешек👑TIMOFEY👑 WA7 // Задача 1254. Крепкий орешек 26 июн 2023 19:02 you don't know how to write bfs, try watching videos for beginners 👑TIMOFEY👑 WA6 // Задача 1254. Крепкий орешек 26 июн 2023 18:40 precision Abid29 wa 9 // Задача 1254. Крепкий орешек 24 апр 2021 00:07 use sqrt(2.00) instead of 1.41421356 kerpoo can anyone give a counterexample if BFS is wrong? [1] // Задача 1254. Крепкий орешек 11 сен 2016 17:49 I used BFS and getting WA#4 but I don't know why my BFS doesen't get AC! This is my code: #include<bits/stdc++.h> using namespace std; #define X saf[0].first+dir[d][0] #define Y saf[0].second+dir[d][1] #define F first #define S second #define mp make_pair const int M=1002; int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; deque<pair<int,int> >saf; pair<int,int> mark[M][M],ans,l[M]; char land[M][M]; int n,m,k; double v; int inland(int x,int y) { if(x<1 || x>n || y<1 || y>m) return false; return true; } void bfs(int h) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mark[i][j].F=mark[i][j].S=0; saf.clear(); saf.push_back(mp(l[h].F,l[h].S)); mark[l[h].F][l[h].S]=mp(1,0); while(saf.size()) { for(int d=0;d<8;d++) if(inland(X,Y)) if(!mark[X][Y].F && !mark[X][Y].S && land[X][Y]=='.') { mark[X][Y]=mark[saf[0].F][saf[0].S]; if(d>3) mark[X][Y].S++; else mark[X][Y].F++; saf.push_back(mp(X,Y)); } saf.pop_front(); } } int main() { cin>>m>>n>>k>>v; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>land[i][j];//scanf("%c",&land[i][j]); for(int i=0;i<=k;i++) scanf("%d%d",&l[i].second,&l[i].first); for(int i=0;i<k;i++) { bfs(i); if(!mark[l[i+1].F][l[i+1].S].F && !mark[l[i+1].F][l[i+1].S].S) { l[i+1]=l[i]; continue; } ans.F+=mark[l[i+1].F][l[i+1].S].F-1; ans.S+=mark[l[i+1].F][l[i+1].S].S; } double x=(double)ans.F+(double)ans.S*sqrt(2.0); printf("%.21f",x/v); return 0; } Edited by author 11.09.2016 17:51 Jade Re: can anyone give a counterexample if BFS is wrong? // Задача 1254. Крепкий орешек 11 сен 2016 21:01 BFS is okay, i use BFS in my solution. The thing is, it's not that simple as it usually is, in fact~ Here's an example for you: 5 8 1 1.00 ..... ..... .#... .##.. .###. .##.. .#... ..... 1 1 3 8 If we move down, we do 6 vertical + 1 diagonal + 1 horizontal = 8 jumps with distance 8.41. But, if we move diagonally, we do 4 diagonal jumps right, 2 diagonal jumps left and 1 vertical = 7 jumps, but greater distance (your program says 9.48). So take into account that less "jumps" is not always less distance. If you redo your BFS properly, it should work out. Good luck! csctcycle why my modified BFS is wrong // Задача 1254. Крепкий орешек 15 дек 2015 17:39 I define the distance between diagonal block as sqrt(2) and others as 1. Then I use bfs to solve this problem but wa in #4 I don't know the reason.please help Michael Plusnin (USU) Planar graph // Задача 1254. Крепкий орешек 1 дек 2012 17:42 This task can be soved using a linear Frederickson shortest path algo. hello It's a good problem ! [3] // Задача 1254. Крепкий орешек 25 июн 2004 19:03 svr Re: It's a good problem ! [2] // Задача 1254. Крепкий орешек 4 фев 2007 11:27 One of solvable by Dijksta with heap. But interesting how to speed up. Idea: use struct (int,int*sqrt(2)) instead of double for distances with compair: (h1,h2*sqrt(2))<(q1,q2*sqrt(2))~ (h1-q1)^2<2*(h2-q2)^2 in int type. Alias (Alexander Prudaev) Re: It's a good problem ! // Задача 1254. Крепкий орешек 24 мар 2007 21:02 i have used other method, and i have best AC 0.265 sec 220 kb IgorKoval(from Pskov) Re: It's a good problem ! // Задача 1254. Крепкий орешек 22 дек 2011 03:53 svr писал(a) 4 февраля 2007 11:27 One of solvable by Dijksta with heap. But interesting how to speed up. Idea: use struct (int,int*sqrt(2)) instead of double for distances with compair: (h1,h2*sqrt(2))<(q1,q2*sqrt(2))~ (h1-q1)^2<2*(h2-q2)^2 in int type. I have read you massage and after wrote as you said. I got TLE. I changed <<<struct harT{long k1, k2;};>>> on <<<double>>> and get AC. Conclusion: It's not good idea or I don't undestand you. =) Edited by author 22.12.2011 03:53 Edited by author 22.12.2011 03:54 M@STeR.SoBG Strange WA #2 [6] // Задача 1254. Крепкий орешек 25 июл 2007 05:43 What can be in this test? What answer for this test? 5 1 1 0.02 .#... 1 1 5 1 Is answer "0.00"??? Rafail Ahmadisheff "0.00" is correct (+) [5] // Задача 1254. Крепкий орешек 9 авг 2007 01:15 M@STeR.SoBG писал(a) 25 июля 2007 05:43 Is answer "0.00"??? Yes. It is "0.00".If he can't reach some bomb he moves to the next one. What if none of the bombs can be reached? If this is the case, you may assume, that agent's mission is complete - he can do nothing, so he does nothing and it takes him no time to do it!TlaughE I got WA in #2 too [4] // Задача 1254. Крепкий орешек 19 ноя 2007 09:45 Is that #2? KALO Re: I got WA in #2 too [3] // Задача 1254. Крепкий орешек 28 окт 2010 00:14 I can't get through test#2 please help. Ibragim Atadjanov (Tashkent U of IT) Re: I got WA in #2 too [2] // Задача 1254. Крепкий орешек 12 ноя 2010 08:15 I also had that problem(wa2). But when I made a test I understood my mistake and got ac. I've used dijkstra and in main method I did like this for(int i = 0; i< k - 1; i ++){ dijkstra(i); ...... } and this was wrong example imagine I cannot reach to th 3rd boomb.So my walk will be like this 0 ->1 ->2 ->3(unreachable) 3->4 ..... instead, it must be like this 0 ->1 ->2 ->3(unreachable) 2->4 ..... I dont know your problem but mine was like above [stupid(:] test 5 5 5 1 ..... .###. .#.#. .###. ..... 1 1 5 1 3 3 5 5 1 5 1 3 ans 14 If it wont help, you can post me ur code(to email) Edited by author 12.11.2010 08:20 KALO Re: I got WA in #2 too // Задача 1254. Крепкий орешек 15 ноя 2010 00:06 Thank you! Edric Mao Re: I got WA in #2 too // Задача 1254. Крепкий орешек 22 окт 2011 16:55 Thanks rohit WA7 [2] // Задача 1254. Крепкий орешек 12 апр 2011 03:18 What's special in test 7 ? I tried all the tests given here and I get right answer. My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same. Anything wrong with my method ? Erop [USU] Re: WA7 [1] // Задача 1254. Крепкий орешек 2 май 2011 22:47 may be some problems with precision? Velea Alex Re: WA7 // Задача 1254. Крепкий орешек 26 авг 2011 01:41 I got the same problem .. i have WA7 .. I used BFs .. O(n*m*k) with 2 quest .. one for the blocks whose were reached by vertical or orizontal moves ( last move ) and another for those who were reached with diagonal moves (last move counts only again .. ) with this i do not need to use Heap :( but i got a problem .. i triend almoast every test .. and they worked .. but still WA7 .. :( my prog. it's not written so well ... so i will not post it .. if you think that it will help you .. ask for it : ) i will keep in touch with this thread :-S Leonid (SLenik) Andrievskiy A little hint for those, who have TLE and who use Dijkstra's algorithm // Задача 1254. Крепкий орешек 3 июл 2011 03:53 My program was written on C# I had written simple Dijkstra -> TLE #6 [ID = 2902593] I had written Dijkstra over Heap (a.k.a. PriorityQueue) -> TLE #6 [ID = 2902684] I had written Dijkstra over RMQ -> AC (3.296 s) [ID = 3643861] Use RMQ for Dijkstra! AterLux To Admins: please add test // Задача 1254. Крепкий орешек 3 май 2011 21:21 7 5 3 1 ....... .#####. .#...#. .#####. ....... 1 1 3 3 5 3 7 1 one of my AC versions fails with test hoan for C++ coder : <set> is very bad!!! [1] // Задача 1254. Крепкий орешек 29 ноя 2010 21:47 dont use <set> for dijekstra, use heap. first i use <set> ansd i had TL#7 but when i changed it to heap i Ac in 1.234 s. sorry for my poor english. GOOD LUCK!!! SEG Re: for C++ coder : <set> is very bad!!! // Задача 1254. Крепкий орешек 2 май 2011 22:44 my dijksta over <set> gets AC in 3.89 vetas Time Limit Test for You [5] // Задача 1254. Крепкий орешек 29 май 2008 15:52 75 75 1000 1.23 .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.. 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 [LG]_#\#@P$T[101]R Re: Time Limit Test for You [2] // Задача 1254. Крепкий орешек 13 июл 2008 16:06 ans is 2219446.46 ? vetas Re: Time Limit Test for You [1] // Задача 1254. Крепкий орешек 11 ноя 2008 21:02 Yes Leonid (SLenik) Andrievskiy Re: Time Limit Test for You // Задача 1254. Крепкий орешек 24 янв 2010 14:38 My program works for about 58 seconds on this test (I'm using Deikstra over Heap) hoan Re: Time Limit Test for You // Задача 1254. Крепкий орешек 29 ноя 2010 21:44 tank you very much !!! hoan Re: Time Limit Test for You // Задача 1254. Крепкий орешек 29 ноя 2010 21:44 thank you very much !!! Fyodor Menshikov Lower TL please [2] // Задача 1254. Крепкий орешек 19 фев 2009 00:37 solution ID 1557946: 3 Mar 2007 time 4.75 solution ID 2456185: 19 Feb 2009 time 1.875 source code is identical. It seems that TL for this problem has not been changed since the server upgrade this autumn. I suggest to lower TL from 5s to 2s or rejudge all TLE solutions submitted before server upgrade. OpenGL +1 [1] // Задача 1254. Крепкий орешек 19 июн 2009 17:25 Al.Cash +1, but // Задача 1254. Крепкий орешек 19 июн 2009 19:07 This problem is far from alone in such situation. The best of all would be to update timelimits for all old problems, but it looks impossible. vgu why "WA7"? [2] // Задача 1254. Крепкий орешек 5 фев 2008 17:50 {$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O-,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1} program Project5; {$APPTYPE CONSOLE} uses SysUtils; const cn: array [0..1] of extended=(1,1.414213562373095); dx: array [1..8] of integer=(-1,0,1,1,1,0,-1,-1); dy: array [1..8] of integer=(-1,-1,-1,0,1,1,1,0); var a: array [0..76,0..76] of byte; i,j,n,m,k,x,y,x1,y1: integer; v,s,res: extended; ch: char; flag: boolean; procedure wave(x,y,x1,y1,n,m: integer; var res: extended; var flag: boolean); var fl: array [0..76,0..76] of byte; r: array [0..76,0..76] of extended; och: array [1..6000,1..2] of integer; i,j,b,e,xz,yz: integer; begin flag:=false; For i:=1 to n do For j:=1 to m do begin fl[i,j]:=0; r[i,j]:=0; end; b:=1; e:=1; och[b,1]:=x; och[b,2]:=y; fl[y,x]:=1; while b<=e do begin If (och[b,1]=x1) and (och[b,2]=y1) then begin flag:=true; break; end; For i:=1 to 8 do begin xz:=och[b,1]+dx[i]; yz:=och[b,2]+dy[i]; If (a[yz,xz]=0) and (xz>0) and (xz<=m) and (yz>0) and (yz<=n) then begin If fl[yz,xz]=0 then begin inc(e); och[e,1]:=xz; och[e,2]:=yz; r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2]; fl[yz,xz]:=1; end else If r[yz,xz]>r[och[b,2],och[b,1]]+cn[i mod 2] then r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2]; end; end; inc(b); end; If flag then res:=r[y1,x1] else res:=0; end; begin readln(m,n,k,v); For i:=1 to n do begin For j:=1 to m do begin read(ch); If ch='#' then a[i,j]:=1 else a[i,j]:=0; end; readln; end; s:=0; readln(x,y); For i:=1 to k do begin readln(x1,y1); wave(x,y,x1,y1,n,m,res,flag); If flag then begin x:=x1; y:=y1; s:=s+res; end; end; write((s/v):0:2); end. vgu Re: why "WA7"? [1] // Задача 1254. Крепкий орешек 6 фев 2008 15:43 AC now sdf Re: why "WA7"? // Задача 1254. Крепкий орешек 1 май 2009 14:44 I have wa7 too. I used dijkstra. Give me hint, I can't find mistake :((( Programmer Why wrong answer7? What is this test? // Задача 1254. Крепкий орешек 28 фев 2009 02:49 Lebedev_Nicolay[Ivanovo SPU] Need Help!!! WA4 [6] // Задача 1254. Крепкий орешек 20 янв 2009 00:05 I use simple BFS, but I have wa4; Can anybody help me??? Vedernikoff Sergey (HSE: EconomicsForever!) Re: Need Help!!! WA4 [5] // Задача 1254. Крепкий орешек 20 янв 2009 00:29 BFS doesn't work here, since you have edges of different lengths, that's why WA. Think of other algorithm OpenGL Re: Need Help!!! WA4 [4] // Задача 1254. Крепкий орешек 20 янв 2009 18:23 I used BFS and got very fast AC Lebedev_Nicolay[Ivanovo SPU] Re: Need Help!!! WA4 [2] // Задача 1254. Крепкий орешек 22 янв 2009 22:35 OpenGL, can you check my solution, if yes - give me your mail. OpenGL void438@mail.ru // Задача 1254. Крепкий орешек 22 янв 2009 23:58 OpenGL void438@mail.ru // Задача 1254. Крепкий орешек 22 янв 2009 23:59 Vedernikoff Sergey (HSE: EconomicsForever!) Re: Need Help!!! WA4 // Задача 1254. Крепкий орешек 22 янв 2009 23:54 2 OpenGL: if you use BFS with dequeue - then yes, it's OK. But usual BFS with queue - it's WA 198808xc A USEFUL HINT for those TLE authors!!! // Задача 1254. Крепкий орешек 1 сен 2008 12:31 Many people got TLE on this problem. However, there are ways to avoid TLE. I viewed some topics before, and they told me to use vectors instead of float numbers. I tried, but it doesn't work for my bad programming. After that, I tried to think another way... Many people got TLE, but they only use 7 or 8 sec. Here is a method to make the time derive to half: First, find all avaliable task, and assume the staring point is No.0 then, instead of calculating all the shortest paths, we can calculate this: Shortest from No.1 to No.0 and No.2, (add them up) Shortest from No.3 to No.2 and No.4, (add them up) ...... thus we can easily save half of the time, and My program got AC in 2.8 sec (previously TLE) Sorry for my bad English. Good luck for EVERYONE~ uuuuuuu Could you explain the sample to me please ? [1] // Задача 1254. Крепкий орешек 5 апр 2003 20:29 I understand the problem like that : J - john's position B - bomb The first way is : J 1 0 0 # # 2 0 B 3 0 0 So the time needed is 3 * 1.23 = 3.69 The second : 0 0 0 B # # 2 0 J 1 0 0 Here the time 2 * 1.23 = 2.64 Total = 2.46 + 3.69 = 6.29 The third : 0 0 0 J # # 0 1 0 0 0 B time = 1.23 total = >>>> 7.52 <<<<< ????!!!!! the answer in the sample isn't even a multiple of v ??!!! WOuld You be so kind and explain it to me ?? vetas Re: Could you explain the sample to me please ? // Задача 1254. Крепкий орешек 4 июн 2008 13:53 >>So the time needed is >>3 * 1.23 = 3.69 if move diagonal distance is sqrt(2) (2+2*(sqrt(2)))/1.23=3.9255 Inside Why i got "WA"? help plz // Задача 1254. Крепкий орешек 27 июл 2007 23:33 #include <iostream> #include <vector> #include <queue> #include <cstdio> using namespace std; char A[75][75]; int B[5625][9]; int color[5625]; double d[5625]; int n,m; queue<short> q; const double dva = 1.4142135623730950488016887242097; void BFS(int s) { int i,u; for(i=0;i<n*m;i++) { color[i]=0; d[i]=-1.0; } color[s]=1; d[s]=0.0; q.push(s); while (!q.empty()) { u=q.front(); for(i=0;i<8;i++) { if(B[u][i]==-1) break; if(color[B[u][i]]==0) { color[B[u][i]]=1; if(B[u][i]==(u-1) || B[u][i]==(u+1) || B[u][i]==(u-n) || B[u][i]==(u+n)) d[B[u][i]]=d[u]+1.0; else d[B[u][i]]=d[u]+dva; q.push(B[u][i]); } } q.pop(); color[u]=2; } } int main() { int k,i,j,x,y,s,f,u,z,c; double dist=0.0,v; cin>>n>>m>>k>>v; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>A[i][j]; for(i=0;i<n*m;i++) { j=0;u=i; if((u+n)<(n*m) && A[(u+n)/n][(u+n)%n]!='#') {B[i][j]=(u+n);j++;} if((u-n)>-1 && A[(u-n)/n][(u-n)%n]!='#') {B[i][j]=(u-n);j++;} if((u+1)%n!=0 && A[(u+1)/n][(u+1)%n]!='#') {B[i][j]=(u+1);j++;} if(u%n!=0 && A[(u-1)/n][(u-1)%n]!='#') {B[i][j]=(u-1);j++;} if((u-n-1)>-1 && (u-n)%n!=0 && A[(u-n-1)/n][(u-n-1)%n]!='#'){B[i][j]=(u-n-1);j++;} if((u-n+1)>-1 && (u-n+1)%n!=0 && A[(u-n+1)/n][(u-n+1)%n]!='#'){B[i][j]=(u-n+1);j++;} if((u+n-1)<(n*m) && (u+n)%n!=0 && A[(u+n-1)/n][(u+n-1)%n]!='#'){B[i][j]=(u+n-1);j++;} if((u+n+1)<(n*m) && (u+n+1)%n!=0 && A[(u+n+1)/n][(u+n+1)%n]!='#'){B[i][j]=(u+n+1);j++;} B[i][j]=-1; } cin>>y>>x; s=(x-1)*n+y-1; for(i=0;i<k;i++) { BFS(s); cin>>y>>x; f=(x-1)*n+y-1; if(d[f]==-1) continue; dist+=d[f]; s=f; } printf("%.2lf\n",dist/v); return 0; }
|