Pagini recente » Cod sursa (job #2793284) | Cod sursa (job #3212796) | Cod sursa (job #1320453) | Cod sursa (job #3223665) | Cod sursa (job #2507041)
#include <iostream>
#include <fstream>
#define N 101
using namespace std;
ifstream fin ("bete.in");
ofstream fout ("bete.out");
int n, suma, a[N];
int s[10001]; /// s[i]=0 daca nu se poate face suma i
/// s[i]=1 daca se poate face suma i
int s2[10001];
int last_added[10001]; ///last_added[i]=ultimul nr adaugat la suma i
int ct=0;
void Read()
{
fin >> n >> suma;
for(int i=1; i<=n; i++)
fin >> a[i];
}
void Afisare(int sum)
{
if(last_added[sum]==0)
fout<<ct<<"\n";
if(last_added[sum]!=0)
{
ct++;
Afisare(sum - a[last_added[sum]]);
fout << last_added[sum] << " ";
}
}
void Solve()
{
int i, j;
s[a[1]]=1;
last_added[a[1]]=1;
for(i=2; i<=n; i++)
{
s2[a[i]]=1;
last_added[a[i]]=i;
for(j=1; j<=10000; j++)
if(s[j]==1)
{
s2[a[i]+j]=1;
last_added[a[i]+j]=i;
}
///adaug noile sume si in s
for(j=1; j<=10000; j++)
if(s2[j]==1)
{
s[j]=1;
s2[j]=0; ///resetez s2
}
}
if(s[suma]==1)
{
fout << "DA" <<"\n";
Afisare(suma);
}
else fout << "NU";
}
int main()
{
Read();
Solve();
//Afisare();
return 0;
}