Dの方が簡単だった。
https://yukicoder.me/problems/no/689
問題
整数Kが与えられる。
N要素の整数列A[i]のうち、i<jについてA[i]+A[j]が奇数になるものがK通りになるようなものを構築せよ。
解法
サンプルにヒントがある。
3,4,5,6からなる数列を作ると、3+4と5+6のみ素数となる。
よってAを3,4,5,6から構築することを考えよう。
C[i]をAにおける登場回数とすると、K=C[3]*C[4]+C[5]*C[6]であればよいので、C[3],C[4],C[5]を総当たりし、条件を満たすC[6]を探そう。
int K; void solve() { int i,j,k,l,r,x,y; string s; cin>>K; for(int a3=0;a3<=200;a3++) { for(int a4=0;a4<=200;a4++) { if(a3+a4>250) continue; int left=K-a3*a4; if(left<0 || left>200) continue; if(left==0) { if(a3+a4<=250) { cout<<a3+a4<<endl; FOR(i,a3) cout<<3<<" "; FOR(i,a4) cout<<4<<" "; return; } continue; } for(int a5=1;a5<=250-a3-a4;a5++) if(left%a5==0) { int a6=left/a5; if(a3+a4+a5+a6<=250) { cout<<a3+a4+a5+a6<<endl; FOR(i,a3) cout<<3<<" "; FOR(i,a4) cout<<4<<" "; FOR(i,a5) cout<<5<<" "; FOR(i,a6) cout<<6<<" "; return; } } } } }
まとめ
シンプルで良い問題。