Show all threads Hide all threads Show all messages Hide all messages |
WA13 | Mortus | 1570. Eating High | 28 Nov 2023 23:59 | 1 |
WA13 Mortus 28 Nov 2023 23:59 Check how you restore the answer. I had the right price , but it brought out fewer dishes than necessary |
Anyone greedy? | alexradu04 | 1570. Eating High | 9 Aug 2022 23:15 | 2 |
I was wondering if there was a greedy solution to this problem help please. Yes, there is after preliminary DP for min-price-allowed-steps-graph. |
Complexity | Infoshoc | 1570. Eating High | 9 Aug 2022 23:13 | 2 |
Solved with O(n * (m+max("filling value")) * 10^3). Anyone better? Strange thing: seems like in tests 15-16 max("filling value") is good deal smaller than 10.0, because O(n * (m+10) * 10^3) failed. There is 30000*100 solution O(filling X dishes) |
If you got WA on test 3 | Lcyanstars | 1570. Eating High | 20 Jul 2021 11:04 | 1 |
Notice that "Filling value” is THREE decimal places. |
If You have WA 13 | 107th | 1570. Eating High | 16 Apr 2021 13:44 | 3 |
look at overflow!!! in test 13 there are meny than 32 different dishes!!! my bug was: int h = j; ... d[i] |= (1 << h); change it to __int64 h = __int64(j); ... d[i] |= (__int64(1) << h); Edited by author 26.08.2008 17:18 Limit for dishes is 100. Why __int64 (64 bit) should be better than int (32 bit)? In both cases you need an array, don't you? |
why wa on test 13/?? | leehark | 1570. Eating High | 15 Apr 2021 15:33 | 3 |
CAN SOME ONE GIVE ME SOME TEST? MY GMAIL: LIHE21327@GMAIL.COM First, DP needs to be 2D. Values array can be 1D, but backtracking info should be 2D. At least I couldn't make it 1D. And even after making parental state indication 2D I still had bugs in that back-traversal :) about wa 13 i am pretty sure its a problem with backtracking. |
wa15 | Zhang Ye | 1570. Eating High | 6 Mar 2021 11:07 | 3 |
wa15 Zhang Ye 6 Mar 2013 14:07 Can I use CompletePack to solve it? Give me a test about wa15. 5 8 a 11 1.1 b 14 1.4 c 15 1.5 e 15 1.5 f 20 2.0 5 8 a 11 1.1 b 14 1.4 c 15 1.5 e 10 1 f 20 2.0 |
WA4 Test | Gleb | 1570. Eating High | 3 Jul 2018 12:23 | 1 |
|
wa7 | Felich | 1570. Eating High | 12 Oct 2016 18:06 | 2 |
wa7 Felich 20 Aug 2014 18:32 Can you give me a test for wa 7, please? seems like problem with precision |
wa13 | lijian3256 | 1570. Eating High | 10 Mar 2010 13:49 | 1 |
wa13 lijian3256 10 Mar 2010 13:49 13?? why。。。。 #include<iostream> using namespace std; struct Point { char Name[50]; int Price,Value; }P[101]; int N,M; unsigned long long Ans=(unsigned long long)1<<63; long long DP[40010]; int Num[40010]; int Pre[40010]; int Sel[40010]; int Hash[101]; int main() { scanf("%d%d\n",&N,&M); M=M*1000; for(int i=1;i<=N;i++) { double Tmp; scanf("%s %d %lf",&P[i].Name,&P[i].Price,&Tmp); P[i].Value=int(Tmp*1000+0.0001); } DP[0]=1; for(int i=1;i<=N;i++) for(int j=0;j<=M;j++) if(DP[j]) { if(DP[j+P[i].Value]==0) { DP[j+P[i].Value]=DP[j]+P[i].Price; Pre[j+P[i].Value]=j; Sel[j+P[i].Value]=i; if(i==Sel[j]) Num[j+P[i].Value]=Num[j]; else Num[j+P[i].Value]=Num[j]+1; } else if(DP[j+P[i].Value]>DP[j]+P[i].Price) { DP[j+P[i].Value]=DP[j]+P[i].Price; Pre[j+P[i].Value]=j; Sel[j+P[i].Value]=i; if(i==Sel[j]) Num[j+P[i].Value]=Num[j]; else Num[j+P[i].Value]=Num[j]+1; } else if(DP[j+P[i].Value]==DP[j]+P[i].Price) { if(i==Sel[j]) { if(Num[j+P[i].Value]<Num[j]) { Pre[j+P[i].Value]=j; Sel[j+P[i].Value]=i; Num[j+P[i].Value]=Num[j]; } } else if(Num[j+P[i].Value]<=Num[j]+1) { Pre[j+P[i].Value]=j; Sel[j+P[i].Value]=i; Num[j+P[i].Value]=Num[j]+1; } } } int TT; for(int i=M;i<=M+20000;i++) if(DP[i]&&DP[i]<Ans) Ans=DP[i],TT=i; else if(DP[i]&&DP[i]==Ans&&Num[i]>Num[TT]) Ans=DP[i],TT=i; cout<<Ans-1<<endl; while(TT>=1) { Hash[Sel[TT]]++; TT=Pre[TT]; } for(int i=1;i<=N;i++) if(Hash[i]) printf("%s %d\n",P[i].Name,Hash[i]); return 0; } Edited by author 10.03.2010 13:51 |
some question | Mithril | 1570. Eating High | 20 Aug 2008 13:50 | 5 |
1. is it possible that there was no solution at all ? 2. number of various dishes , means total number of dishes or total number of kinds of the dishs? thanks. 1).No because 2).You've got unlimited reserve of dishes. We've got a total number of kinds of dishes. 3). Whats up with Test 13???Last solvings got WA and TL... my reason for not passing Test 13 was using one dimensional table in DP instead of two dimensional. Can some one make up a test that makes one dimensional DP fail? Try this 3 4 a 2 2 b 1 1 c 1 1 |
minor fix | Denis Koshman | 1570. Eating High | 20 Aug 2008 13:32 | 2 |
"reach" should be replaced with "rich" in English problem statement |
Test 9 | svr | 1570. Eating High | 1 Apr 2008 13:51 | 10 |
It seems that in test 9 M>20 All right,mistake Edited by author 10.10.2007 13:39 This is the first problem in timus fo me when DP gives TL(Tle15).In all world such strong tests when DP used are absent as a rule. What parameters we have: 1. productivityness: from 0 to 30000; 2. number of dishes from 1 to 100 3. possible number of each dishes: from 1 to 100 Thus DP needs ~ 300000000 simple integer operations. Why it leads to TLE. Edited by author 11.10.2007 13:59 Edited by author 11.10.2007 14:02 Re: Test 9 KIRILL(ArcSTUpid coder:) 11 Oct 2007 16:20 I use more quick: free(c); c=c1; c1=(int *) malloc(20001*sizeof(int)) But Tle 16 Edited by author 25.03.2008 22:51 Re: Test 9 Fetisov Alex [USTU Frogs] 26 Mar 2008 21:59 Simple DP without any memory optimisations gives AC) I don't belive! For Ac It was required to me a great carefulness in the most internal loop. For example: value k*c[i-1] I was forced to precalculate as cc[k][i-1] and two characteristics c and m where m- number of dishes to unite in one as c*200-m Re: Test 9 Fetisov Alex [USTU Frogs] 31 Mar 2008 00:04 Hm.. For each cost (calory) I had an array of the meals I used.. and no problems with memory My straightforward solution to the problem got AC within 0.234 sec without any optimizations/precalculations/so on. So, timelimit is quite huge and the only problem is in ineffective algos... Re: Test 9 Vladimir Yakovlev (USU) 11 Oct 2007 16:27 There is a solution with O(productivityness * number_of_dishes) time I used this solution and still got TLE on test 12. I couldn't accept it untill I reduced my used memory (use shorts instead of ints where possible, make the DP table as small as possible). Then I got accepted (0.8s on the toughest test) |
Can anyone tell me what's the problem with test 9 | lakeoffire | 1570. Eating High | 6 Nov 2007 15:34 | 2 |
This is my code. I would appreciate if someone will help me. #include <stdio.h> #include <vector> #include <string.h> #include <bitset> #include <math.h> using namespace std; #define INFI 0x3f3f3f3f #define NMAX 150300 #define pb push_back #define ff first #define ss second #define sz size() inline int MAX(int a, int b) { return (a > b) ? (a) : (b); } inline int MIN(int a, int b) { return (a < b) ? (a) : (b); } typedef struct dish { int f, c; char s[50]; }; vector<dish> p; int n, m; int a[NMAX], b[NMAX], c[NMAX]; short viz[NMAX], viz2[NMAX]; inline dish scan() { dish aux; double x; scanf("%s %d %lf\n", aux.s, &aux.c, &x); aux.f = (int)floor(x*1000); return aux; } void read() { scanf("%d %d\n", &n, &m); for(int i = 0; i < n; ++i) p.pb( scan() ); } void knap1() { int i, j, until; viz[0] = 1; for(i = p.sz-1; i >= 0; --i) { for(j = 0; j < NMAX; ++j) if(j - p[i].f >= 0 && viz[ j - p[i].f ]) { if(!viz[ j ]) a[ j ] = a[ j - p[i].f ] + p[i].c, viz[ j ] = 1; else a[ j ] = MIN(a[ j ], a[ j - p[i].f ] + p[i].c); } } } void knap2() { int i, j, until; memset(c, -1, sizeof(c)); viz2[0] = 1; for(i = p.sz-1; i >= 0; --i) for(j = 0; j < NMAX; ++j) if(j - p[i].f >= 0 && viz2[ j - p[i].f ]) { viz2[ j ] = 1; if(b[ j - p[i].f ] + (c[ j - p[i].f ] != i) > b[ j ]) b[ j ] = b[ j - p[i].f ] + (c[ j - p[i].f ] != i), c[ j ] = i; } } int main() { // freopen("1570.in", "r", stdin); // freopen("1570.out", "w", stdout); read(); knap1(); knap2(); int min = INFI, poz = 0; //for(int i = m*1000; i < NMAX; ++i) int i = m*1000; if(viz[i]) if(min > a[i] || (min == a[i] && b[i] > b[poz])) min = a[i], poz = i; printf("%d\n", min); // printf("%d\n", b[poz]); int j = poz, nr, aux; while(j > 0) { nr = 1; aux = c[j]; j -= p[ c[j] ].f; while(c[j] == aux) ++nr, j -= p[ aux ].f; printf("%s %d\n", p[aux].s, nr); } // printf("\n"); // for(j = 0; j < NMAX; ++j) // if(b[j]!= 0) // printf("%d %d %d %d\n", j, a[j], b[j], c[j]); return 0; } |
Why it may be WA15 ? | Laise (Chernenkov Alexey) | 1570. Eating High | 10 Oct 2007 21:51 | 3 |
Why it may be WA15 ? Can anybody tell me? if it can help you to answer? this is my source code: source code temporarily deleted Edited by author 10.10.2007 21:33 this line is wrong if (bcnt[i-b[j].cal][0] >= bcnt[i][0] && bcnt[i-b[j].cal][j] == 0) delete your code Kirill, very very much thanks to you!!!! ))) Now a have AC... There was realy mistake in the statement... very LAMO mistake |