|
|
Hi, 1. If any product is mentioned in the list then the minimum weight of that product should be at least 1. So, if you have input like this 3 a 1 1000 b 0 c 0 Then the minimum total weight of this scenario is 1002 because b and c got to have at least 1. The maximum is 3000. The final answer is NO. 2. Multiple products can have same weights so for the above case the max total weight is 3000 with a = b = c = 1000. The problem can be solved by finding the minimum possible weight and maximum possible weight and checking if 10000 is in between them. For example: 3 a 0 b 0 c 1 5 The minimum possible weight is 15 (a = b = c = 5) and the maximum possible weight is 20005 (a = b = 10000 and c = 5). And so 15 <= 10000 <= 20005 and hence the answer is true. Well the real answer is a = 4998, b = 4997 and c = 5. You just need to run two loops, one for finding minimum weight and the another one for finding maximum weight. And here some test cases from other places on this forum: Test Case 1 4 Water 0 Cocoa-butter 0 Cocoa-powder 1 4000 Lecithin 0 Minimum Sum is 12001 and maximum sum is 28000 so the answer is NO. Test Case 2 5 a1 1 2001 a2 0 a3 0 a4 0 a5 1 1999 Minimum sum is 9997 and the maximum sum is 10003 and so the answer is YES. Test Case 3 4 w 1 10 a 0 b 1 1 c 0 Minimum sum is 13 and the maximum sum is 22 so the answer is NO. Test Case 4 3 a 1 3 b 0 c 0 Minimum sum is 5 and the maximum sum is 9 so the answer is NO. Test Case 5 3 a 1 10000 b 0 c 0 Minimum sum is 10002 and the maximum sum is 30000 so the answer is NO. Test Case 6 3 a 0 b 0 c 0 Minimum sum is 3 and the maximum sum is 30000 so the answer is YES Test Case 7 5 a1 1 9997 a2 0 a3 0 a4 0 a5 0 Minimum sum is 10001 and the maximum sum is 49985 so the answer is NO. Varun Edited by author 24.12.2010 08:51 Why I have worng anserw in test #2?? My code: #include <cstdio> #include <iostream> #include <string> using namespace std; int main() { int n; cin >> n; string nazwa[5000]; int wartosc[1000], wartosc2[1000], x, koniec = n-1, pocz = 0, min = 1, max = 10000, summin = 0, summax = 0; for (int i=0; i<n; i++) { cin >> nazwa[i]; cin >> x; if (x == 1) cin >> wartosc[i]; if (x == 0) wartosc[i] = 0; wartosc2[i] = wartosc[i]; }
for (int i = koniec; i>=0; i--) { if (wartosc[i] == 0) wartosc[i] = min; else min = wartosc[i]; summin += wartosc[i]; }
for (int i = pocz; i < n; i++) { if (wartosc2[i] == 0) wartosc2[i] = max; else max = wartosc2[i]; summax += wartosc2[i]; }
if ( summin < 10000 && 10000 < summax) cout << "YES"; else cout << "NO"; getchar(); getchar(); return 0; system("PAUSE"); } Edited by author 24.01.2011 01:13 Hi, I keep getting wrong answer for test 7. Any hint as to what is test 7 ? Thanks This test helped me. 4 Water 1 10 Cocoa-butter 0 Cocoa-powder 1 1 Lecithin 0 answer is "NO". My mistake was in disregarding too low maximum value. Thank your hint! This test helped me. 4 Water 1 10 Cocoa-butter 0 Cocoa-powder 1 1 Lecithin 0 answer is "NO". My mistake was in disregarding too low maximum value. For the above shown test the minimum possible weight is 13(10 + 1 + 1 + 1) and the maximum possible weight is 22 (10 + 10 + 1 + 1). Since 10000 does not lie in their range, the answer is NO. 3 q 0 r 0 e 1 5 right ans:Yes Thank you! I got AC (0.125sec) This test helped me. 4 Water 1 10 Cocoa-butter 0 Cocoa-powder 1 1 Lecithin 0 Answer is NO. Because there is a maximum of 40 parts of 10000 Could anybody give me some tests?? i can't find mistake in my solution.. :-( Try this test: 3 a 1 3 b 0 c 0 correct answer is NO. Why the answer is NO ? No, because your can't find such value for last 2 components, that totalSum not < than 10000 Why the answer is NO ? didn't understand.what'd be if b = 9990 and c = 7? According to the statement B and C must be not greater than A. So B<=3 and C<=3. If you failed on test 12,try this test. 3 a 10000 b 0 c 0 You should output NO because the amount of "b" and "c" can't be less than 1. If you failed on test 12,try this test. 3 a 10000 b 0 c 0 You should output NO because the amount of "b" and "c" can't be less than 1. May be 3 a 1 10000 b 0 c 0 :) program Ural1190; var h:array[1..5000]of longint; a,can,n,l,m:longint; w:char; begin readln(n); fillchar(h,sizeof(h),0); l:=maxlongint; for a:=1 to n do begin w:='a'; while w<>' ' do read(w); read(m); if m=1 then readln(h[a]) else h[a]:=-1; end; l:=1; can:=0; for a:=1 to n do begin if h[a]=-1 then inc(l); if h[a]<>-1 then begin can:=can+h[a]*l; l:=1; end; end; if can>10000 then begin writeln('NO'); halt; end; can:=0; l:=1; for a:=n downto 1 do begin if h[a]=-1 then inc(l); if h[a]<>-1 then begin can:=can+h[a]*l; l:=1; end; end; if l>1 then can:=can+10000; if can<10000 then begin writeln('NO'); halt; end; writeln('YES'); end. Edited by author 07.02.2009 08:15 Edited by author 07.02.2009 08:15 I know AC solution that answers YES for test 2 Cocoa-butter 1 10000 Cocoa-powder 0 I think that answer for this test should be NO because if it is true, then fraction of Cocoa-powder is 0, and it should not be mentioned in the list at all. One more problematic test is 3 Cocoa-butter 1 9999 Cocoa-powder 0 Lecithin 0 It is not clear whether fraction may be less than one handredth of percent. If it may then the answer is YES, if it cannot then the answer is NO. I suggest to clarify this in statement. Edited by author 04.02.2009 23:25 Test 3 contains duplicate names of components. If one component may be mentioned several times, then for the following test 2 Water 1 6000 Water 0 answer should be 'NO' because according to component list bar consists entirely of water, and percent of water should be 100 (10000 in input). All known to me AC solutions ignore names of components so I suggest to rename duplicate names in test 3 and add into statement notice that all names in the list are different. WA Test 9. Can anyone test my program? Anyone know what is the test #9? I thing, that my program solve this task! But wrong Test#4. What I hadn't read? Sum of all thing must be 100 00? I don't know... [или я просто не фтыкаю информатику ;)] ==== SOURSE ==== Var cur,last:longint; i,n:longint; s:string; f:boolean; Begin readln(n); readln(s); last:=GetProc(s); sum:=0; f:=false; for i:=2 to n do Begin readln(s); cur:=GetProc(s); if (last>=cur) then cur:=last else Begin f:=true; cur:=last; End; End; if f then writeln('NO') else writeln('YES'); End. *** GetProc - returne procent of thing. The following situation doesn't checked in tests or the problem statement is incorrect. --------------- 2 Cocoa-butter 1 1000 Cocoa-powder 1 9000 --------------- Here we have weights written in increasing order (problem says: they should be in non-increasing order!). My solution checks this and gets WA. But the solution from forum says YES and gets AC. ;) You are right. N = 5000 in test 3. The problem statement is fixed. I have Crash#1. And I know, that first string in input is not number, because I catch exception, than I convert this String to Integer. Read FAQ, it's not allowed to use exceptions here, so try..except, or try..catch will lead to Crash (when exception occurs) Problem statement: 0 < N < 5000. Test 3: N = 5000. One more bug: test 3 contains duplicate names of components. Like in this test: 2 a 1 6000 a 0 I think this kind of tests was not intended, because I know AC program that does not use name information at all. |
|
|