#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for(int i=0; i<n; i++){
cin>>a[i];
}
int s;
cin>>s;
int dp[s+1]={0,};
for(int i=0; i<n; i++){
dp[a[i]]=1;
for(int j=a[i]+1; j<=s; j++){
if(dp[j-a[i]]>0 or j==a[i]){
if(dp[j]>dp[j-a[i]]+1 or dp[j]==0)
dp[j]=dp[j-a[i]]+1;
}
}
}
if(dp[s]==0){
cout<<"No solution"<<endl;
return 0;
}
cout<<dp[s]<<endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgbjsKCWNpbj4+bjsKCWludCBhW25dOwoJZm9yKGludCBpPTA7IGk8bjsgaSsrKXsKCQljaW4+PmFbaV07Cgl9CglpbnQgczsKCWNpbj4+czsKCWludCBkcFtzKzFdPXswLH07Cglmb3IoaW50IGk9MDsgaTxuOyBpKyspewoJCWRwW2FbaV1dPTE7CgkJZm9yKGludCBqPWFbaV0rMTsgajw9czsgaisrKXsKCQkJaWYoZHBbai1hW2ldXT4wIG9yIGo9PWFbaV0pewoJCQkJaWYoZHBbal0+ZHBbai1hW2ldXSsxIG9yIGRwW2pdPT0wKQoJCQkJCWRwW2pdPWRwW2otYVtpXV0rMTsKCQkJCQkKCQkJfQoJCX0KCX0KCWlmKGRwW3NdPT0wKXsKCQljb3V0PDwiTm8gc29sdXRpb24iPDxlbmRsOwoJcmV0dXJuIDA7Cgl9Cgljb3V0PDxkcFtzXTw8ZW5kbDsKfQ==
NQoxIDMgNyAxMiAzMgo0MA==
5 1 3 7 12 32 40
language:
C++ (gcc 8.3)
created:
22 days ago
Discover > Sphere Engine API
The brand new service which powers Ideone!
Discover > IDE Widget
Widget for compiling and running the source code in a web browser!
