Show all threads Hide all threads Show all messages Hide all messages |
To those who got WA#6 | hbmhalley | 1029. Ministry | 22 Jun 2022 17:18 | 3 |
Maybe you have to make a larger array to put the answer. thank you very much,, I've been stuck in this problem for weeks because of this. |
AC program test cases | lakerka | 1029. Ministry | 14 May 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. |
AC | linjek | 1029. Ministry | 19 Feb 2022 12:11 | 3 |
AC linjek 7 Aug 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 |
if you have WA#5 try to use long arithmetics | KALO | 1029. Ministry | 24 Oct 2021 22:31 | 4 |
There is no reason to use long arithmetic.. Read the hint. Though may be you store something amazing to solve the task in more effecient way... In any case, the problem is solvable without long arithmetic WTF REALLY IT HELPS ME!!! THANKS YOU. Я ТУПО СИДЕЛ И НИЧЕГО НЕ ПОНИМАЛ ПОЧЕМУ НЕ РАБОТАЕТ, ЛОНГИ ПОМОГЛИ!! только я не понял почему вообще инт не залетел) |
WA #6?? | Aniruddh Sriram | 1029. Ministry | 29 Dec 2018 04:08 | 1 |
WA #6?? Aniruddh Sriram 29 Dec 2018 04:08 I am using DP, it works for all TC on discussion. what could be wrong? |
WA#1 | Yerlan | 1029. Ministry | 26 Mar 2018 21:49 | 1 |
WA#1 Yerlan 26 Mar 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. Ministry | 3 Nov 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. Ministry | 8 Dec 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. Ministry | 21 Apr 2015 14:08 | 1 |
|
Approach | karan | 1029. Ministry | 9 Apr 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). |
WA15 | Vladislav | 1029. Ministry | 14 Mar 2014 00:37 | 1 |
WA15 Vladislav 14 Mar 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. |
TL#1 | IgorTuphanov | 1029. Ministry | 3 Mar 2014 03:32 | 2 |
TL#1 IgorTuphanov 24 Dec 2005 19:26 Может, я чего и не понимаю, но почему подобный код получает TL#1? #include <stdio.h> #include <stdlib.h> #include <string.h> #define inf 2100000000 int a[2][510],res[2][510]; char fy[110][510]; int n,m,min,i1,i2; void Rec(int i, int j) { if (i > 1) { if (fy[i][j] == j) Rec(i-1,j); else Rec(i,fy[i][j]); }; printf("%d\n",j); }; int main(void) { int i,j; scanf("%d%d",&m,&n);
for (j = 1; j <= n; j++) scanf("%d",&a[1][j]); for (i = 1; i <= n; i++) res[1][i] = a[1][i]; for (i = 2; i <= m; i++) for (j = 1; j <= n; j++) res[i][j] = inf; for (i = 1; i < m; i++) { i1 = i%2; i2 = (i+1)%2; for (j = 1; j <= n; j++) scanf("%d",&a[i2][j]); for (j = 1; j <= n; j++) { res[i2][j] = res[i1][j] + a[i2][j]; fy[i+1][j] = j; }; for (j = 2; j <= n; j++) if (res[i2][j] > res[i2][j-1] + a[i2][j]) { res[i2][j] = res[i2][j-1] + a[i2][j]; fy[i+1][j] = j-1; }; for (j = n-1; j >= 1; j--) if (res[i2][j] > res[i2][j+1] + a[i2][j]) { res[i2][j] = res[i+1][j+1] + a[i2][j]; fy[i+1][j] = j+1; }; }; min = inf; for (i = 1; i <= n; i++) if (res[m%2][i] < min) { min = res[m%2][i]; i1 = i; }; Rec(m,i1); return 0; }; Почему scanf и printf. Ты используешь cin и cout. (Because of scanf and printf. It's better to use cin and cout) |
WA#1 | Slobodianiuk Sergii | 1029. Ministry | 3 Mar 2014 01:17 | 2 |
WA#1 Slobodianiuk Sergii 11 Feb 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. |
Can there be a negative number? | keivan | 1029. Ministry | 2 Nov 2013 18:05 | 5 |
I don't know why I get WA on test 4! Can there be a negative number? This is my code: #include<iostream> #include<cmath> using namespace std; long long dyn[110][510] , a[110][510] , big, sum[110][510] , p[110][510][2] , o , m, n; int main(){ cin>>m>>n; for(int i=0;i<m;i++) for(int j=0;j<n;j++) cin>>a[i][j]; for(int i=0;i<m;i++) { sum[i][0]=a[i][0]; dyn[i][0]=100000000000000000; for(int j=1;j<n;j++) { sum[i][j]=sum[i][j-1]+a[i][j]; dyn[i][j]=100000000000000000; } } if((m==1)&&(n==1)) { cout<<1<<endl; return 0; } dyn[m-1][0]=a[m-1][0]; for(int i=1;i<n;i++) { dyn[m-1][i]=a[m-1][i]; } for(int i=m-2;i>=0;i--) { for(int j=n-1;j>=0;j--) { for(int k=0;k<n;k++) { if(j>k) { if(dyn[i+1][k]+sum[i][j]-sum[i][k-1]<dyn[i][j]) { dyn[i][j]=dyn[i+1][k]+sum[i][j]-sum[i][k-1]; p[i][j][0]=j; p[i][j][1]=k; } } else { if(dyn[i+1][k]+sum[i][k]-sum[i][j-1]<dyn[i][j]) { dyn[i][j]=dyn[i+1][k]+sum[i][k]-sum[i][j-1]; p[i][j][0]=j; p[i][j][1]=k; } } } } } big=dyn[0][0]; o=0; for(int i=1;i<n;i++) { if(dyn[0][i]<big) { big=dyn[0][i]; o=i; } } cout<<o+1; for(int i=1;i<m-1;i++) { if(p[i][o][0]<=p[i][o][1]) { for(int j=p[i][o][0];j<=p[i][o][1];j++) cout<<" "<<j+1; } else { for(int j=p[i][o][0];j>=p[i][o][1];j--) cout<<" "<<j+1; } o=p[i][o][1]; } cout<<" "<<o+1<<endl; return 0; } No there can't be. My ac code. [code deleted] Edited by moderator 19.11.2019 23:27 Seems like your AC code fails at test: 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 I'm sorry. I should be more careful while reading the problem statement. The correct answer here is 2 2 1 1 1 1. Not 2 2 1 1 1 2 3 3 4 5 5 5. |
Just test | 2rf [Perm School #9] | 1029. Ministry | 28 Oct 2013 15:36 | 5 |
Just test 2rf [Perm School #9] 6 Aug 2009 17:19 This test helped me to get AC, though I think it's good only against my solution: 3 4 1 100 1000 0 1 1 1000 0 100 0 1000 100 //answer 1 1 2 2 it helps me a lot! appreciate you in chinese :谢谢你 The fee is a POSITIVE integer. |
What the output means? | phizaz | 1029. Ministry | 25 Aug 2013 14:29 | 2 |
I don't understand what the output means? thanks for help! OUTPUT: 3 3 2 1 1 MOVE 1: 1st floor [3]rd room MOVE 2: 2nd floor [3]rd room MOVE 3: 2nd floor [2]nd room MOVE 4: 2nd floor [1]st room MOVE 5: 3rd floor [1]st room More Detailed: Let out[] be the output array. If out[i] == out[i+1] then it means that you go one floor up, as there is no point in revisiting the same official. Otherwise you go to one of the neighboring rooms. If out[i] + 1 == out[i+1] then you go to the right neighboring room. Else if out[i] - 1 == out[i+1] then you go to the left neighboring room. Hope it helped you. And hope that my C-style like syntax didn't make it hard to understand :) Edited by author 25.08.2013 14:31 |
WA test #6 | idemura | 1029. Ministry | 7 Jul 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. Ministry | 25 May 2013 14:12 | 1 |
WA16 Radostin Chonev 25 May 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. Ministry | 16 May 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. Ministry | 16 Mar 2013 02:05 | 1 |
|