Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Страница 4 |
WA #6?? | Aniruddh Sriram | 1029. Министерство | 29 дек 2018 04:08 | 1 |
WA #6?? Aniruddh Sriram 29 дек 2018 04:08 I am using DP, it works for all TC on discussion. what could be wrong? |
WA#1 | Yerlan | 1029. Министерство | 26 мар 2018 21:49 | 1 |
WA#1 Yerlan 26 мар 2018 21:49 My code fails with WA#1 although it passes every test cases that I've found in comments. Any hints? |
What is the wa3 and wa6 like? | Wei Zhang | 1029. Министерство | 3 ноя 2017 01:04 | 1 |
Need help. Stuck for serval weeks! What is wa3 like? What is wa6 like? |
all who got wa on 5 | azizulhakim.f | 1029. Министерство | 8 дек 2015 11:52 | 1 |
i also got wa on 5 and then found out i considered room and floor both can be at most 100. but problem says floor is 100 and room can be at most 500. |
please help | PAUL MICKEY TOPPO | 1029. Министерство | 21 апр 2015 14:08 | 1 |
|
AC | linjek | 1029. Министерство | 19 фев 2022 12:11 | 3 |
AC linjek 7 авг 2014 22:39 I solved this problem with algo of Dijkstra. Edge : (i,j)->(i+1,j), (i-1, j), (i, j+1) with weight of a[i]j]; Edited by author 19.02.2022 12:12 Why I get WA?! Edited by author 19.02.2022 12:12 Edited by author 19.02.2022 12:13 |
AC program test cases | lakerka | 1029. Министерство | 14 май 2022 14:37 | 3 |
3 4 1 100 1000 0 1 1 1000 0 100 0 1000 100 //answer 1 1 2 2 1 1 1000000000 //answer 1 5 6 525 0 171 0 872 673 0 843 0 0 0 0 0 277 0 202 0 0 0 0 733 957 65 96 637 566 0 0 0 441 //answer: 4 4 5 5 5 5 10 1 10 10 10 1 1 10 10 10 1 10 1 1 1 1 1 1 10 1 10 10 10 10 1 //answer: 2 2 1 1 1 1 1 10 100 90 80 70 60 50 40 30 20 10 //answer: 10 5 6 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 //answer: 2 2 3 3 3 2 2 3 2 3 1 1 1 1 3 //answer: 2 2 1 1 3 1 1 1 1 //answer: 1 1 1 You 3rd and 6th test cases are wrong. The fee should be positive. |
WA15 | Vladislav | 1029. Министерство | 14 мар 2014 00:37 | 1 |
WA15 Vladislav 14 мар 2014 00:37 If you have WA15 use for dp and for fees long long, because not optimal answer for official, which can be before program find optimal answer, may be more then 10^9. |
WA#1 | Slobodianiuk Sergii | 1029. Министерство | 3 мар 2014 01:17 | 2 |
WA#1 Slobodianiuk Sergii 11 фев 2014 06:26 I don't know why my program has WA#1. My computer gives correct answer. Please help me, maybe you had the same problem. If you have written your solution in C++ and you use scanf and printf, it would be better to use cin and cout. |
Approach | karan | 1029. Министерство | 9 апр 2014 12:24 | 4 |
I used dijkstra to do in O(mnlog(mn))? Whats your approach? I used dynamic programming to solve the question. dp[floor][room][lastStep] indicates the best way to reach top when we are on floor, room and the last step is know. Each state of dp is solved in constant time as we have to do only 2 computations at each step. But my approach runs very very slow. Two dimensions are enough DP can solve this problem in O(MN). |
WA test #6 | idemura | 1029. Министерство | 7 июл 2013 06:25 | 1 |
My code: What's wrong??? #include <algorithm> #include <vector> #include <utility> #include <stdio.h> #define ARRAY_SIZEOF(a) (sizeof(a) / sizeof(a[0])) #define INF 0x7fffffff using namespace std; typedef long long int lli; int M, N; int C[100][500]; int T[101][500]; int m1[500]; int m2[500]; int path[500*500]; int main() { #ifndef ONLINE_JUDGE freopen("in", "r", stdin); #endif int i, j, k; scanf("%d%d", &M, &N); for (i = 0; i < M; i++) { for (j = 0; j < N; j++) { scanf("%d", &C[i][j]); C[i][j]++; T[i+1][j] = INF; } } for (i = 1; i <= M; i++) { m1[0] = T[i-1][0] + C[i-1][0]; for (j = 1; j < N; j++) { m1[j] = min(m1[j-1], T[i-1][j]) + C[i-1][j]; } m2[N-1] = T[i-1][N-1] + C[i-1][N-1]; for (j = N-1; j-- > 0; ) { m2[j] = min(m2[j+1], T[i-1][j]) + C[i-1][j]; } for (j = 0; j < N; j++) { T[i][j] = min(m1[j], m2[j]); } } int jmin = 0; for (j = 1; j < N; j++) { if (T[M][j] < T[M][jmin]) { jmin = j; } } i = M; j = jmin; k = 0; do { path[k++] = j + 1; int m = T[i-1][j]; jmin = j; if (j-1 >= 0 && T[i][j-1] < m) { jmin = j-1; m = T[i][jmin]; } if (j+1 < N && T[i][j+1] < m) { jmin = j+1; m = T[i][jmin]; } if (m == T[i-1][j]) i--; else j = jmin; } while (i); for (i = 0; i < k; i++) { printf("%d ", path[k-1-i]); } printf("\n"); return 0; } |
WA16 | Radostin Chonev | 1029. Министерство | 25 май 2013 14:12 | 1 |
WA16 Radostin Chonev 25 май 2013 14:12 Can anyone help me ? I have WA16 and i don't know what is wrong with my code . UPD : Test 16 is a big test . I replaced in one place int with long long and i got AC. Good Luck :) ! Edited by author 25.05.2013 14:23 |
maybe a cornor case to help. | hliu20 | 1029. Министерство | 16 май 2013 14:18 | 1 |
Think about this case If you use DP 2 2 1 1 0 0 when considering the elem 0 at [1, 0] , you can find the way from [0, 1] -> [1, 0] and [0, 1] -> [1, 1] -> [1, 0] have the same sum(both are 1), how to handle this situation ? I handle this by giving the way from `ABOVE` higher priority, or else when printing the path to the answer, you wil get [1, 0] <- [1, 1] <- [1, 0] <- [1, 1] ....... which is WA. and another thing to notice is you may need long long to hold. hope it helps :) |
Why WA#4????? | Top Secret | 1029. Министерство | 16 мар 2013 02:05 | 1 |
|
How to print the solution.. | Top Secret | 1029. Министерство | 10 мар 2013 00:46 | 1 |
I am able to find the minimum cost but not being able to print the room numbers. |
How to avoid to use int64 | Vlad | 1029. Министерство | 27 янв 2013 23:58 | 1 |
The result isn't greater than 1 000 000 000. So everytime you make "element = something" you should do "element = min(something, 1 000 000 000)" , min(a, b) returns a if a < b of b if a > b. |
WA15 | Capitan | 1029. Министерство | 7 дек 2012 02:24 | 1 |
WA15 Capitan 7 дек 2012 02:24 Hint is wrong. I had WA#15, but after changing in Java code "int" to "long" task was accepted. |
To Judge new test | TheDreamCatcher | 1029. Министерство | 23 ноя 2011 17:00 | 3 |
I got AC. But I know test that crush my solution; we need gen Fibonachi F(0)=0 F(1)=1 from 0 to 33 F(n)=F(n-1)+F(n-2)+1 from 34 to 499 F(n)=F(n-1) then fill the table 100 500 F(499) F(498) ... F(0) F(499) F(498) ... F(0) ...................... F(499) F(498) ... F(0) also test 100 500 F(0) F(1) ... F(499) F(0) F(1) ... F(499) ...................... F(0) F(1) ... F(499) Good Luck! Does the correct answer fits in the 10^9 limit? Read site news. Thank you for tests. |
Страница 3 |
special cases | luckysundog | 1029. Министерство | 15 окт 2011 17:13 | 1 |
test #2: M==1 => read N numbers from and output index of minimal test #3: N==1 => output '1' M times |
I got crash(access violation) in test14,please help me!!! | guojinyu | 1029. Министерство | 30 июл 2011 20:42 | 1 |
I got crash in test14,please help me!!! this is my program: #include <iostream> #include <cstdio> using namespace std; int n,m,xia=0; int fare[110][510]; int dp[110][510],jilu[70000]; char pre[110][510]; void init() { int i,j; scanf("%d %d",&n,&m); for(i=0;i<=n+1;i++) for(j=0;j<=m+1;j++) { fare[i][j]=2000000000; dp[i][j]=2000000000; } for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&fare[i][j]); for(i=1;i<=m;i++) dp[1][i]=fare[1][i]; } void print(int i,int j) { int k,ti,tj; while(1) { ++xia; jilu[xia]=j; ti=i; tj=j; if(pre[i][j]=='B') ti-=1; if(pre[i][j]=='L') tj-=1; if(pre[i][j]=='R') tj+=1; if(i==1) break; i=ti; j=tj; } for(k=xia;k>=1;k--) printf("%d\n",jilu[k]); } void solve() { int i,j,end,temp=2000000000; for(i=2;i<=n;i++) { for(j=1;j<=m;j++) { if(dp[i-1][j]<=dp[i][j-1]) if(dp[i-1][j]+fare[i][j]<dp[i][j]) { dp[i][j]=dp[i-1][j]+fare[i][j]; pre[i][j]='B'; } if(dp[i-1][j]>dp[i][j-1]) if(dp[i][j-1]+fare[i][j]<dp[i][j]) { dp[i][j]=dp[i][j-1]+fare[i][j]; pre[i][j]='L'; } if(dp[i][j]>dp[i][j+1]+fare[i][j]) { dp[i][j]=dp[i][j+1]+fare[i][j]; pre[i][j]='R'; } } for(j=m;j>=1;j--) { if(dp[i-1][j]<=dp[i][j-1]) if(dp[i-1][j]+fare[i][j]<dp[i][j]) { dp[i][j]=dp[i-1][j]+fare[i][j]; pre[i][j]='B'; } if(dp[i-1][j]>dp[i][j-1]) if(dp[i][j-1]+fare[i][j]<dp[i][j]) { dp[i][j]=dp[i][j-1]+fare[i][j]; pre[i][j]='L'; } if(dp[i][j]>dp[i][j+1]+fare[i][j]) { dp[i][j]=dp[i][j+1]+fare[i][j]; pre[i][j]='R'; } } } for(i=1;i<=m;i++) if(dp[n][i]<temp) { temp=dp[n][i]; end=i; } print(n,end); } int main() { init(); solve(); return(0); } |