Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Страница 3 |
runtime error | yakung | 1119. Метро | 9 мар 2021 09:44 | 1 |
I'm getting runtime error(access violation) on test case three. I don't know where I went wrong. Can anyone please help me? Here is my code using namespace std; #include <iostream> #include <cmath> #include<bits/stdc++.h> long long int n,m; bool vi[1005][1005], di[1005][1005]; float dp[1005][1005]; #define inf 1e7 float shortest_path(int x, int y){//returns shortest path //base case if(x==n && y==m) return 0.0; if(x>n || y>m) return inf; //memorization if(vi[x][y]) return dp[x][y]; //recursive relation float a,b,c = 20000.0; if(di[x][y]==1){ a = sqrt(c) + shortest_path(x+1,y+1);//diagonal b = inf; }
else { a = 100.0 + shortest_path(x+1,y);//left b = 100.0 + shortest_path(x,y+1);//up }
float ans = min(a,b); dp[x][y] = ans; vi[x][y] = 1; return dp[x][y]; } int main(){ cin>>n>>m; int k; for (int i = 0; i < n*m; ++i) { for (int j = 0; j < n*m; ++j) { di[i][j] = 0; vi[i][j]=0; dp[i][j]=0; } } cin>>k; for (int i = 0; i < k; ++i) { int a,b; cin>>a>>b; di[a-1][b-1] = 1; } cout<<round(shortest_path(0,0))<<endl;
} |
Is given problem test case is right??? | codefresher | 1119. Метро | 29 июн 2022 20:47 | 2 |
The problem test case is: 3 2 3 1 1 3 2 1 2 but is it right?? My observation finds: 3 2 3 1 1 3 2 2 1 plz help me??? |
Is possible to have AC on Python 3.6? | Egor_Shchetinin | 1119. Метро | 4 фев 2022 21:28 | 3 |
I tried to solve this task by dp and bfs, but always have a TL on test 3. the same for python3 Edited by author 03.07.2021 00:47 I just got an AC with pypy |
A better solution | ComebackSeason | 1119. Метро | 9 янв 2019 20:32 | 4 |
I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales. Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j]) where Diag[i][j] is either 100 * sqrt(2) or Infinity. I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently? But when Diag[i][j] get infinity sir I think the main cause of memory consumption is the matrix of DOUBLES. Even a simple array of doubles consumes a lot of memory. Even for the solution involving graph and shortest paths would use 'huge' amount of memory, since you would also need a 2 dimensional array of doubles (I suppose). I managed to solve it using 9360KB. Edited by author 14.06.2018 17:45 a better solution is to use dynamic programming to find the longest increasing sequence of diagonals, which there are 100 at most. then ``` min = (n + m - maxDiagonals * 2) * distance + maxDiagonals * diagonalDistance ``` |
TLE with bfs | sukhad | 1119. Метро | 18 фев 2017 03:53 | 1 |
I am using bfs to solve the problem but still getting TLE. Can anyone suugest the cause? |
There exists O(K^2) solution!!! | c_pp | 1119. Метро | 7 янв 2017 21:27 | 1 |
|
WA10 test | German | 1119. Метро | 22 июл 2017 16:34 | 4 |
10 6 8 2 1 2 2 4 5 5 2 5 4 6 5 9 4 10 5 Ansver: 1366 Парень, я не знаю, где ты это взял, но тебе ОГРОМНОЕ спасибо! С помощью твоих данных нашел ошибку и сдал программу. Спасибо. My program do this test case is correct, but i get WA on 10 test. Pls, anybody write this test! my program pass this too, but I came up with the test which leads to error: 8 8 8 2 7 3 3 4 4 5 4 6 3 6 1 7 2 8 3 answer must be 1424. |
getting Runtime error in test case 3 of metro. Please help | Sushant Bhat | 1119. Метро | 4 сен 2016 19:34 | 2 |
#include<iostream> #include <cmath> #include <climits> #include <deque> using namespace std; int v[1001][1001]; float table[1002][1002]; int metro(int n,int m,int k){ deque<int> qi,qj; qi.push_back(1); qj.push_back(1); table[1][1] = 0; while(!qi.empty()){ int i = qi.front(),j = qj.front(); qi.pop_front(); qj.pop_front(); if(i <= n && table[i+1][j] > table[i][j]+100){ qi.push_back(i+1); qj.push_back(j); table[i+1][j] = table[i][j]+100; } if(j <= m && table[i][j+1] > table[i][j]+100){ qi.push_back(i); qj.push_back(j+1); table[i][j+1] = table[i][j]+100; } if(v[i][j] == 1){ if(i <= n && j <= m && table[i+1][j+1] > table[i][j] + 141.4){ qi.push_back(i+1); qj.push_back(j+1); table[i+1][j+1] = table[i][j]+(141.4); } } } return ceil(table[n+1][m+1]); } int main(){ int n = 0,m = 0,k = 0; cin>>n>>m; for(int i = 0;i <= n+1;++i){ for(int j = 0;j <= m+1;++j){ v[i][j] = 0; table[i][j] = INT_MAX; } } cin>>k; for(int i = 0;i < k;++i){ int x = 0,y = 0; cin>>x>>y; v[x][y] = 1; } cout<<metro(n,m,k)<<endl; return 0; } Edited by author 29.08.2016 16:40 Edited by author 29.08.2016 16:40 It is a biggest test for check boundaries. And you are have a problems with it. For example: for(int i = 0;i <= n+1;++i){ for(int j = 0;j <= m+1;++j){ v[i][j] = 0; where v is: int v[1001][1001]; With n = 1000 this code will crash. It's about 3 test case. Ans I see another mistakes... |
Need Help TEAST CASE5 | Dewesh Deo Singh | 1119. Метро | 22 янв 2018 12:24 | 2 |
I am getting WA 5 Can anyone provide me the test case 5.. or hint to test case 5.. same with u LOL i WA test 5 :"( |
To admins | Mescheryakov_Kirill [SESC17] | 1119. Метро | 21 июн 2023 04:11 | 3 |
To admins Mescheryakov_Kirill [SESC17] 23 фев 2016 11:20 In a task it is told that a way of departure (1; 1) though, actually, the way of departure has to be (0; 0) Nop, he is starting out from the south-west corner of the 1;1 quarter Isn't that the same as 0;0? |
java AC code | esbybb | 1119. Метро | 14 июн 2015 17:28 | 3 |
Messages should not contain correct solutions. i use matrix of costs, each step set value of the cell as minimal of the previous vertical cost + 100, previous horizontal cost + 100, previous diagonal cost + 100*sqrt(2) the answer is Math.round(cost[M][N]) p.s. cycle is organized from 1 to n, 1 to m inclusively Edited by author 14.06.2015 17:09 by default diagonal cost is set to MAX_VALUE, it is updated in case of a[i][j]=true, where a is a matrix of allowed to be crossed through diagonally cells also column with index 0 is populated incrementally (cost[0][0]=0, cost[1][0]=100, cost[2][0]=200..) as well as row with index 0 before the main nested loop starts |
WA 13 Help, pls | Minayev {SESC USU} | 1119. Метро | 2 ноя 2014 17:16 | 1 |
this is my bad code #include <vector> #include <iostream> #include <cmath> #include <algorithm> #include <stdio.h> using namespace std; struct poi { int x,y; }; vector<poi> g; int n; int ma=0; vector<int> w; bool compare(poi m,poi mm) { if (m.x>mm.x) { return false; } else { return true; } } void dp(int t,int coun) { if (coun>ma) { ma=coun; } for (int x=t+1; x<n; x++) { if ((g[x].x>g[t].x) and (g[x].y>g[t].y) and (coun+1)>w[x]) { w[x]=coun+1; dp(x,coun+1);
} } } int main() { int a,b; poi t; scanf("%d%d%d",&a,&b,&n); w.resize(n); for (int x=0; x<n; x++) { scanf("%d%d",&t.x,&t.y); g.push_back(t); w[x]=0; } sort(g.begin(),g.end(),compare); for (int x=0; x<n; x++) { if (w[x]==0) { w[x]=1; dp(x,1); } } double ras=(a+b-2*ma)*100; ras+=ma*sqrt(20000); printf("%d", int(ras+0.5)); }
what is the test №13 |
Comp error | nexerd | 1119. Метро | 19 мар 2018 16:47 | 2 |
while (n>0) { b=a; b=b/pow(10,n-1) - rezult/pow(10,n-1); for (int i=1;i<10;i++) if ((b-i>=0)&(b-i-1<0)) rezult += (i)*pow(10,n-1); n--; } /* if delete : b=b/pow(10,n-1) - rezult/pow(10,n-1); for (int i=1;i<10;i++) if ((b-i>=0)&(b-i-1<0)) rezult += (i)*pow(10,n-1); - work! */ 1. Which programming language do you use? 2. Did you name the variable for result "rezult" (if there is need to pre-declare variables in yout PL)? |
how is output 383 and not 241 for sample cases | Mayank Punetha | 1119. Метро | 26 сен 2014 00:05 | 3 |
first the person goes to (2,2) from (1,1) +141 then (3,2) +100 so why not 241? (0, 0) -> (1, 1) = sqrt(2) * 100 (1, 1) -> (2, 1) = 100 (2, 1) -> (3, 2) = sqrt(2) * 100 Total: 382.842712475 ~ 383 Edited by author 26.07.2014 17:17 Then shouldnt the problem wording be stated as rounding the solution to the nearest integer? If I just round 382.84 to its integer value, it would be 382. |
No subject | Justxu | 1119. Метро | 17 янв 2014 18:57 | 1 |
|
WA test5! Help, please! | Kate | 1119. Метро | 27 сен 2023 14:02 | 5 |
Попробуй большую точность, там где большое поле, например: Input: 1000 1000 5 100 100 200 200 300 300 400 400 500 500 Output: 199707 Thanks it was rounding error |
wrong answer 3 | wuqingxin | 1119. Метро | 10 дек 2014 00:37 | 2 |
Could I get the data of the test 3 something like this 1000 1000 0 |
Wrong Answer 10 | it170994 | 1119. Метро | 12 окт 2013 19:06 | 1 |
who know this error please explain for me please. Give me test 10. Thank you!!! |
Страница 2 |
To admins - weak tests | master_j | 1119. Метро | 21 сен 2013 14:52 | 2 |
Consider two test cases: 3 3 3 1 2 2 3 3 1 and 3 3 3 1 3 2 1 3 2 Although they are symmetric and the answers must be equal, my AC programs (5180921 or 5180891) output different answers for them. Your tests were added. Thank you. |
Can someone help me with test 8? | DKarev | 1119. Метро | 26 июн 2013 22:30 | 1 |
I have WA on test 8. Can someone help. I tried every given test in the site but I can't find any mistakes. This is my code: // #include<iostream> #include<cmath> #include<algorithm> #include<iomanip> using namespace std; bool b[2005][2005]; long double a[2005][2005]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); long double diag=sqrt(2)*100; int n,m,k,k1,r; cin>>n>>m>>r; for(int i=0;i<r;i++) { cin>>k>>k1; b[k][k1]=1; } n++; m++; for(int i=2;i<=n;i++)a[1][i]=a[1][i-1]+100; for(int i=2;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=a[i-1][j]+100; if(j!=1 && a[i][j]>a[i][j-1]+100)a[i][j]=a[i][j-1]+100; if(b[i-1][j-1] && a[i][j]>a[i-1][j-1]+diag+0.001)a[i][j]=a[i-1][j-1]+diag; } } cout<<fixed<<setprecision(0)<<a[n][m]<<"\n"; return 0; } |