Bit Manipulation is black magic to me really i just cant figure out how sum of all subsets possible is obtained by it, so just decided to dissect the vexorian's editorial code
here is it
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
using namespace std;
#define FOR(i,a) for(long int i = 0;i < a;i++)
#define REP(i,a,b) for(long int i = a;i < b;i++)
static const int MAX = 100000 * 20 + 1;
bool poss[MAX];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int MinNumber(vector<int> S);
vector<int>S;
int temp,n;
cin>>n;
FOR(i,n)
{cin>>temp;
S.push_back(temp);
}
int k=MinNumber(S);
cout<<k<<endl;
return 0;
}
int MinNumber(vector<int> S)
{
fill(poss, poss + MAX, false);
int n = S.size();
// All subsets:
for (int mask = 0; mask < (1<<n); mask++) {
cout<<"mask "<<mask<<endl;
int sum = 0;
for (int i = 0; i < S.size(); i++) {
if (mask & (1<<i)) {
cout<<"S[i] "<<S[i]<<" i "<<i<<endl;
sum += S[i];
}
}
poss[sum] = true;
}
int x = 1;
while (poss[x]) {
x++;
}
return x;
}
here is it
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
using namespace std;
#define FOR(i,a) for(long int i = 0;i < a;i++)
#define REP(i,a,b) for(long int i = a;i < b;i++)
static const int MAX = 100000 * 20 + 1;
bool poss[MAX];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int MinNumber(vector<int> S);
vector<int>S;
int temp,n;
cin>>n;
FOR(i,n)
{cin>>temp;
S.push_back(temp);
}
int k=MinNumber(S);
cout<<k<<endl;
return 0;
}
int MinNumber(vector<int> S)
{
fill(poss, poss + MAX, false);
int n = S.size();
// All subsets:
for (int mask = 0; mask < (1<<n); mask++) {
cout<<"mask "<<mask<<endl;
int sum = 0;
for (int i = 0; i < S.size(); i++) {
if (mask & (1<<i)) {
cout<<"S[i] "<<S[i]<<" i "<<i<<endl;
sum += S[i];
}
}
poss[sum] = true;
}
int x = 1;
while (poss[x]) {
x++;
}
return x;
}
for input like :-
3
1 2 3
output is:-
mask 0 mask 1 S[i] 1 i 0 mask 2 S[i] 2 i 1 mask 3 S[i] 1 i 0 S[i] 2 i 1 mask 4 S[i] 3 i 2 mask 5 S[i] 1 i 0 S[i] 3 i 2 mask 6 S[i] 2 i 1 S[i] 3 i 2 mask 7 S[i] 1 i 0 S[i] 2 i 1 S[i] 3 i 2 7
7 is the least possible sum which cannot be generated by all the numbers of the sequence
and i have trouble finding out how this code does it :P and i have an end semester due on monday RATS!!!!
No comments:
Post a Comment