【1】 問題
解答長さnの数列Aと整数Mに対して、Aの要素の中のいくつかの要素を足しあわせてMが作れるかどうかを判定するプログラムを作成せよ。
Aの各要素は1度だけ使うことができる。
数列Aが与えられたうえで、質問としてq個のMが与えれるので、それぞれについて"yes"または"no"と出力せよ。
プログラムはC, C++, JAVA, C++11, C#, Dいずれかの言語で作成すること。
入力
1行目にn、2行目にAを表すn個の整数、3行目にq、4行目にq個の整数Miが与えられる。
出力
各質問についてAの要素を足しあわせてMiを作ることができればyesと、できなければnoと出力せよ。
制約
n ≤ 20
q ≤ 200
1 ≤ Aの要素 ≤ 2000
1 ≤ Mi ≤ 2000
import std.stdio;
import std.conv;
import std.string;
void main(){
int n = to!int(stdin.readln().strip());
int[] A = new int[n];
string[] inputA = stdin.readln().split();
for(int i = 0; i < n; i++){
A[i] = to!int(inputA[i]);
}
int q = to!int(stdin.readln().strip());
int[] Mi = new int[q];
string[] inputMi = stdin.readln().split();
for(int i = 0; i < q; i++){
Mi[i] = to!int(inputMi[i]);
}
foreach(int x; Mi){
writeln(A.findSum(x) ? "yes" : "no" );
}
}
bool findSum(const(int)[] elements, int x){
if(elements == null || elements.length == 0)return false;
if(elements[0] == x)return true;
return findSum(elements[1..$],x - elements[0]) || findSum(elements[1..$],x);
}
"Don't repeat yourself."(コードの重複は避けよ)に従うと…
import std.stdio;
import std.conv;
import std.string;
template InputArrayCode(alias LengthName, alias ArrayName){
static immutable string InputArrayCode = r"int " ~ LengthName ~ r" = to!int(stdin.readln().strip());
int[] " ~ ArrayName ~ " = new int[" ~ LengthName ~ r"];
string[] input" ~ ArrayName ~ r" = stdin.readln().split();
for(int i = 0; i < " ~ LengthName ~ r"; i++){
" ~ ArrayName ~ "[i] = to!int(input" ~ ArrayName ~ r"[i]);
}";
}
void main(){
mixin(InputArrayCode!("n","A"));
mixin(InputArrayCode!("q","Mi"));
foreach(int x; Mi){
writeln(A.findSum(x) ? "yes" : "no" );
}
}
bool findSum(const(int)[] elements, int x){
if(elements == null || elements.length == 0)return false;
if(elements[0] == x)return true;
return findSum(elements[1..$],x - elements[0]) || findSum(elements[1..$],x);
}