Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "At Boss's Expense"
https://onlinejudge.u-aizu.ac.jp/problems/0202
・上司のおごり
僕が作成、提出したコードは、以下のとおりです。
・Aizu Online Judge in C++ #Volume2 - 0202 : At Boss's Expense
/* Aizu Online Judge in C++ #Volume2 - 0202 : At Boss's Expense https://onlinejudge.u-aizu.ac.jp/problems/0202 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll i,j,n,x,v[35],a[10000010],b[10000010]; int main(void){ for(i=2;i<10000000;i++){ if(a[i]==0){ a[i]=1; if(i*2<=1000000){ for(j=i*2;j<1000000;j+=i){ a[j]=2; } } } } while(cin>>n>>x,n){ for(i=0;i<=x;i++){ b[i]=0; } b[0]=1; for(i=0;i<n;i++){ cin>>v[i]; } for(i=0;i<n;i++){ for(j=0;j<=x;j++){ if(b[j]==1 && j+v[i]<1000000){ b[j+v[i]]=1; } } } for(i=x;i>1;i--){ if(b[i]==1 && a[i]==1){ break; } } if(i==1){ cout<<"NA\n"; }else{ cout<<i<<"\n"; } } return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/