1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<cmath> #include<vector> #include<map> #include<queue> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int mod=1e9+7; inline int mo(ll a,int p){ return a>=p?a%p:a; } inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } inline ll gcd(ll x, ll y){ return y==0?x:gcd(y,x%y); } inline ll speed(ll a,ll b){ ll cur=a,anss=1; while(b){ if(b&1) anss=anss*cur; cur=cur*cur; b>>=1; } return anss; } const int MAXN=1e5; bool ipr[MAXN+20]; int cnt,pri[MAXN/5]; void prime(){ int N=sqrt(MAXN)+0.5,mul; memset(ipr,true,sizeof(ipr)); ipr[1]=false; for(int i=2;i<=N;i++){ if(ipr[i]==true){ i==2?mul=1:mul=2; for(int j=i*i;j<=MAXN;j+=i*mul){ ipr[j]=false; } } } for(int i=2;i<=MAXN;i++){ if(ipr[i]==true){ pri[++cnt]=i; } } } int n,m; int a[50]; int ans[50],ct=0,al=0,mid; bool fg=false; map<int,int>mp; int sss=15; void dfs(int cur,int sum,int cou){ if(fg) return; if(sum==m){ fg=true; ct=cou; return; } if(cur==n+1) return; ans[cou+1]=a[cur]; if(sum+a[cur]<=m&&al-sum-a[cur]>=m-sum-a[cur]) dfs(cur+1,sum+a[cur],cou+1);
if(al-sum>=m-sum) dfs(cur+1,sum,cou);
} void dfs1(int cur,int sum){ mp[sum]=1; if(cur==n+1) return; dfs1(cur+1,sum+a[cur]); dfs1(cur+1,sum); } void dfs2(int cur,int sum,int cou){ if(fg) return; if(mp[m-sum]){ fg=true; mid=sum; ct=cou; return; } if(cur==sss+1) return; ans[cou+1]=a[cur]; if(sum+a[cur]<=m&&al-sum-a[cur]>=m-sum-a[cur]) dfs2(cur+1,sum+a[cur],cou+1);
if(al-sum>=m-sum) dfs2(cur+1,sum,cou);
} bool fg2=false; void dfs3(int cur,int sum,int cou){ if(fg2) return; if(sum==m){ fg2=true; ct=cou; return; } if(cur==n+1) return; ans[cou+1]=a[cur]; if(sum+a[cur]<=m&&al-sum-a[cur]>=m-sum-a[cur]) dfs3(cur+1,sum+a[cur],cou+1); if(al-sum>=m-sum) dfs3(cur+1,sum,cou);
} int main(){
scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); al+=a[i]; } if(al<m){ printf("No Solution\n"); return 0; } sort(a+1,a+1+n); if(n<=sss){ dfs(1,0,0); } else{ dfs1(sss+1,0); dfs2(1,0,0); if(fg) dfs3(sss+1,mid,ct); }
if(fg){ for(int i=1;i<=ct;i++){ printf("%d ",ans[i]); } printf("\n"); } else{ printf("No Solution\n"); } return 0; }
|