# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1128099 | azik | Bootfall (IZhO17_bootfall) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define pb push_back
#define int short int
#define all(v) v.begin() , v.end()
using namespace std;
int n , m ;
const int N = 101;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n ;
int sum =0 ;
vector<int>a;
short int h;
for(int i= 1 ; i <= n; i++){
cin>>h;
sum+=h;
a.pb(h);
}
if(n<= 1 ){
cout << 0 ;
return 0 ;
}
//sum*=5;
vector<int>ans;
for(int x = 0 ; x <= sum ; x++) {
a.pb(x);
int ok =0 ;
for(int pos = 0 ; pos < n ;pos++) {
if( x == 0 )pos = n ;
int sum2 = sum + x - a[pos];
//cout << a[pos] << ' ' << x << ' ' << sum2 << '\n';
if (sum2 % 2 != 0) {
ok = 1;
break;
}
sum2 /= 2;
bitset < N * 100 > dp;
dp[0] = 1;
for(int i = 0; i < a.size(); i++){
if(i == pos) continue;
dp |= (dp << a[i]);
}
if (!dp[sum2]) {
ok = 1;
break;
}
}
if(x == 0 && ok){
cout << 0 ;
return 0 ;
}
if(!ok && x > 0 ){
ans.pb(x);
}
a.pop_back();
}
cout<< ans.size() << '\n';
for(auto it:ans){
cout << it << ' ';
}
}