Instead of searching for answer for m, search for sum - m

All forum tests passed, but wa:( Million thanks to someone who will help!

Я написал на чистом Си и не мог ну никак пробиться через 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;
}

You must sort the missing cards' number in increasing order.

ALL tests from the discussion passed and still WA7. Any suggestions?

5
4
1 3 6 1

answer:3



Edited by author 29.05.2011 11:06

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

let me know the algorithm please

Please help me....... Thanks in advance

I solve this task with DP, but wa#12... Please give me some useful tests. Thanks.

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

270
5
50
50
100
110
170
and the answer is
-1

Thank you to the ones who provide some tests.

[code deleted]

Edited by author 01.04.2008 21:52

Sorry for the trouble,I have error in the algorithm.
By the way can we use brute force here?

Edited by author 30.01.2007 22:04

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