Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
To those who got WA#6 | hbmhalley | 1029. Министерство | 22 июн 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. Министерство | 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. |
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 |
if you have WA#5 try to use long arithmetics | KALO | 1029. Министерство | 24 окт 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. Министерство | 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 |
|
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). |
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. |
TL#1 | IgorTuphanov | 1029. Министерство | 3 мар 2014 03:32 | 2 |
TL#1 IgorTuphanov 24 дек 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. Министерство | 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. |
Can there be a negative number? | keivan | 1029. Министерство | 2 ноя 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. Министерство | 28 окт 2013 15:36 | 5 |
Just test 2rf [Perm School #9] 6 авг 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. Министерство | 25 авг 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. Министерство | 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 |
|