1 solutions

  • 0
    @ 2024-12-11 0:16:56

    C++ :

    #include <iostream>
    #include <cstdio>
    using namespace std;
    int n,c;
    int s[7001];
    bool flag[7001]={0}; 
    void in();
    void out();
    int find();
    int main()
    {
    	in();
    	if(find()!=0)
    	{
    		out();
    	}
    	else
    	{
    		cout<<"NoSolution!"<<endl;      
    	}
    	return 0;
    }
    void in()
    {
    	cin>>n>>c;
    	for(int i=0;i<n;i++)
    	{
    		cin>>s[i];
    	}
    }
    int find()
    {
    	int i=0,cc=0;
    	while(i>=0)
    	{
    		if(flag[i]==false)
    		{
    			flag[i]=true;
    			cc+=s[i];
    			if(cc==c)
    			{
    				return 1;        
    			}
    			else if(cc>c)
    			{
    				flag[i]=false;
    				cc-=s[i];
    			}
    			i++;      
    		}
    		if(i>=n)
    		{
    			while(flag[i-1]==true)
    			{
    				i--;
    				flag[i]=false;
    				cc-=s[i];
    				if(i<1)
    				{
    					return 0;
    				}
    			}
    			while(flag[i-1]==false)
    			{
    				i--;
    				if(i<1)
    				{
    					return 0; 
    				}
    			}
    			flag[i-1]=false;
    			cc-=s[i-1];
    		}
    	}
    	return 0;
    }
    void out()
    {
    	for(int i=0;i<n;i++) 
    	{
    		if(flag[i]==true)  
    		{
    			cout<<s[i]<<" ";
    		}
    	}
    	cout<<endl;
    }
    

    Pascal :

    program acm21151;
    var n,c,sum,i:longint;
        v:array[1..7010]of boolean;
        a:array[1..7010] of longint;
    procedure search(now,k:longint);
    var i,j:longint;
    begin
        if (now>c) then exit;
        if (now=c) then
    	  begin
    		for i:=1 to n do
            if v[i] then write(a[i],' ');
            writeln;
            halt;
          end;
        if (k>n) then exit;
        v[k]:=true;
        search(now+a[k],k+1);
        v[k]:=false;
        search(now,k+1);
    end;
    begin
    	readln(n,c);
        for i:=1 to n do
         begin
    	   read(a[i]);
    	   sum:=sum+a[i];
    	 end;
        if(sum<c) then
    	begin writeln('NoSolution!'); halt; end;
        fillchar(v,sizeof(v),false);
        search(0,1);
        writeln('NoSolution!');
    end.
    
    
    • 1

    Information

    ID
    691
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By