All forum tests passed, but wa:( Million thanks to someone who will help! upd: I have AC with this test: 0 2 1 1 Instead of searching for answer for m, search for sum - m 5 4 1 3 6 1 answer:3 Edited by author 29.05.2011 11:06 thanks for your test, it helped me thanks ! Edited by author 18.04.2014 19:54 You must sort the missing cards' number in increasing order. This test helped me on WA14: 10 4 1 1 2 10 Answer: 1 2 3 Я написал на чистом Си и не мог ну никак пробиться через WA#4 Затем я переписал на Си++14 и получил AС Видимо сложность Си и отсутствие привычных функций STD меня отвлекают от сути задачи в какой-то мере Ну а алгоритм -- это задача о рюкзаке Вместимость рюкзака равна рвзности между суммарным весом всех карт и весом неполной колоды. /* ye mera template hai apna khud likho bc :P */ /* Author : Sarvagya Agarwal */ #include<bits/stdc++.h> using namespace std; //defines #define openin freopen("input.txt","r",stdin) #define openout freopen("output.txt","w",stdout) #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define ll long long #define int long long #define mod 1000000007 #define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--) #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++) #define all(c) (c).begin(),(c).end() #define ff first #define ss second #define pb push_back #define mp make_pair /* Print pair */ template <typename T,typename S> ostream & operator << (ostream &os , const pair<T,S> &v) { os << "(" ; os << v.first << "," << v.second << ")" ; return os ; } /* Print vector */ template <typename T> ostream & operator << (ostream &os , const vector<T> &v) { os << "[" ; int sz = v.size() ; for(int i = 0 ; i < sz ; ++i) { os << v[i] ; if(i!=sz-1)os << "," ; } os << "]\n" ; return os ; } /* Print set */ template <typename T> ostream & operator << (ostream &os , const set<T> &v) { T last = *v.rbegin() ; os << "[" ; for(auto it : v) { os << it ; if(it != last) os << "," ; } os << "]\n" ; return os ; } /* Print Map */ template <typename T,typename S> ostream & operator << (ostream &os , const map<T,S> &v) { for(auto it : v) { os << it.first << " : " << it.second << "\n" ; } return os ; } int power(int a , int b) { int res = 1 ; while(b) { if(b%2) { res = (res * a) % mod ; } b/=2 ; a = (a*a) % mod ; } return res ; } //debug #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif int sum , n , arr[105] ; int dp[105][1005] ; int ans[105] ; int solve(int index,int weight) { if(weight == 0) { // found a configuration return 1 ; } if(index > n) { return 0 ; } int &res = dp[index][weight] ; if(res != -1) return res ; res = 0 ; res += solve(index + 1 , weight) ; if(arr[index] <= weight)res += solve(index + 1 , weight - arr[index] ) ; return res ; } void go(int index, int weight) { if(index > n || weight == 0) return ; // can you take this ? if(arr[index] <= weight && solve(index + 1 , weight - arr[index]) == 1) { ans[index] = 1 ; go(index + 1 , weight - arr[index] ) ; return ; } go(index + 1 , weight) ; return ; } int32_t main() { fast; cin >> sum >> n ; rep(i,1,n) { cin >> arr[i] ; } memset(dp,-1,sizeof(dp)) ; int res = solve(1,sum) ; if(res == 0) { cout << res ; return 0 ; } if(res > 1) { cout << -1 ; return 0 ; } go(1,sum) ; for(int i = 1 ; i <= n ; ++i) { if(ans[i] == 0) { cout << i << " " ; } } return 0; } 4950 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 4951 ans = 100 Edited by author 11.05.2017 11:05 Simple test for programs with verdict WA #14: Sample input: 0 2 1 1 Sample output 1 2 Your program outputs "-1"? Find your simple stupid mistake!!! Edited by author 05.11.2005 18:58 Thank you!I got AC!!!Before testing your testcase,my program outputed "2" :) It helps a lot. Thank you! BTW. It's not a valid test case. Here's a valid one. input: 3 3 3 1 1 output: 2 3 1) 3 2 1 2 2) 614 13 627 861 527 911 751 658 568 846 998 188 923 426 685 3) 1560 19 580 594 644 62 963 718 291 532 293 77 356 984 384 182 986 915 18 671 920 4) 555 27 816 170 523 595 471 313 970 877 465 50 819 517 721 143 394 872 905 462 346 639 193 902 945 927 133 401 410 5) 800 15 10 20 30 40 50 60 70 80 90 100 110 120 130 200 350 6) 1458 17 802 204 451 575 158 168 247 15 50 100 1000 257 354 125 358 125 268 Thanks. Edited by author 22.06.2006 19:08 Edited by author 23.06.2006 12:20 My answer: 1. -1 2. 1 2 3 4 5 6 7 8 9 11 13 3. 2 3 4 5 6 8 9 10 11 12 13 14 15 16 19 4. 0 At me now wrong answer 12. Give me tests. I used DP, but I have found a mistake{an error} at a conclusion-1. Can give me what that ideas! Help!!! Thanks 1)0 2)1 2 3 4 5 6 7 8 9 11 13 3)-1 4)0 5)-1 6)-1 Your test#1 doesn't match the description that "It's guaranteed that the total weight of all cards in the complete pack is strictly greater than the weight of the incomplete pack." Please help me....... Thanks in advance It's similar to knapchak problem Even knapsack passes the tests. ALL tests from the discussion passed and still WA7. Any suggestions? try this test too : ) 7 4 4 4 3 2 corrent : -1 my WA was : 0 the judje calcute the memory wrong. my Ac code have this line:
char dp[100+5][100000+5]; as a global array in C++. it has about 10000Kb, but the judge calcute memory about 5000Kb. sorry for my poor english. Edited by author 29.11.2010 23:28 I solve this task with DP, but wa#12... Please give me some useful tests. Thanks. to Admins!!! 2 2 1 1 result empty line or zero? Also have WA #12 (now). The test above is incorrect (weight of not full set is strongly less than weight of full set of cards by condition) I lost this fragment: if(f[i][1-page]==-1) f[i][page]=-1; or if(f[i][j-1]==-1) f[i][j]=-1; Please give me (show me) test#12. Thanks Edited by author 04.07.2009 01:20 let me know the algorithm please I got Time limit exceeded in test 17. Can you tell me the reason ??? i had just tried all given test ?but it WA in #1 . Const finp =''; Fout =''; Maxn =101; Limit =200000; var fi,fo :Text; n,s :Longint; A :array[0..Maxn] of Integer; d,f :array[0..Limit] of Integer; Procedure OpenFile; Begin Assign(fi,finp); Reset(fi); Assign(fo,fout); Rewrite(fo); End; Procedure CloseFile; Begin Close(fi); Close(fo); End; Procedure Readinp; Var i:Integer; sum:Longint; Begin Readln(fi,s); readln(fi,n); For i:=1 to n do Read(fi,a[i]); end; Procedure Solve; Var i,st,Maxtong,Max:Longint; Begin Fillchar(d,sizeof(d),0); Fillchar(f,sizeof(f),0); f[0]:=1; maxtong:=0; For i:=1 to n do Begin Max:=Maxtong; For st:=Maxtong downto 0 do if f[st] <>0 then Begin if f[st+a[i]]=0 then Begin f[st+a[i]]:=i; d[st+a[i]]:=1; end else d[st+a[i]]:=d[st]+d[st+a[i]]; if max<st+a[i] then Max:=st+a[i]; ENd; Maxtong:=max; End; End; Procedure Trace; Var i,dem:Integer; Begin if d[s]=0 then Writeln(fo,0) else if d[s] >1 then Writeln(fo,-1) else Begin dem:=0; While s>0 do Begin Inc(dem); d[dem]:=f[s]; s:=s-a[f[s]]; if s=0 then Break; End; For i:=dem downto 1 do Write(fo,d[i],' '); End; End; begin OpenFile; Readinp; Solve; Trace; CloseFile; End. Edited by author 29.11.2008 18:30 For each mass store amount of possibilities you can get it. If this number exceeds to than you can lower it downto 2. NumGet: array[0..MaxCardMass * MaxCards] of byte; For each mass store atleast one (if possible) card wich can create that mass. WhatGet: array[1..MaxCardMass * MaxCards] of byte; You need 1000*100 * 2 arrays of bytes. Start DP with 0 cards; NumGet[0] := 1; for CurrentCard <- 1 to CardCount do for i <-SumOfAllCards - CardWeight[CurrentCard] DOWNTO (!!!) 0 do if NumGet[i] <> 0 then Inc(NumGet[i + CardWeight[CurrentCard]], NumGet[i]); if NumGet[i + CardWeight[CurrentCard]] > 2 the NumGet[i + CardWeight[CurrentCard]] := 2 if WhatGet[i + CardWeight[CurrentCard]] = 0 then WhatGet[i + CardWeight[CurrentCard]] := CurrentCard; Downto needed to avoid next trap: consider we can get mass 100 know we check card with mass 10 when i = 100 we mark that we can get 110 when i = 110 and it is (already marked) we mark 120 when i = 120 ... ... Hope this will be helpfull...
I have the same idea as you.but i got WA.Please help me. I think we should check if there is no solution(output 0) first,and then check if there is more than one solution(output -1). am I right? Here is my program: [code deleted] Edited by moderator 27.03.2007 09:45 Knapsack at all, guys, as well :) It's so helpfull... Thank you. :) What output? 150 4 50 50 50 50 and this 200 4 50 50 50 50 My AC program outputs -1 in both cases Why output -1 for the second test??? My output for the first one is -1 and for the second one is an empty line. second test is not valid. it's given that some cards are missing... which means there is atleast one card missing 270 5 50 50 100 110 170 and the answer is -1 |
|