私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「カードを使って数を作ろう（簡単編）」（CodeIQ）を参照してください。
【概要】
カードが何枚かあります。
カードには、一桁の数字が書いてあります。
カードをn枚選んで並べて数を作ります。
たとえば、「3」「1」「4」「1」「5」が書いてあるカードから 3枚(つまり、n=3)を選んで並べると「341」や「115」を作ることができます( 「334」や「31」は作れません）。
作れる数のうち、ある数 m にもっとも近い数を答えてください。
【入出力】
入力は
4,1234,1/2/2/3/9/9/9
のような感じです。
コンマ区切りで、n(カードの枚数)、m(この値に近い数を作る)、カード列 が並んでいます。
カード列は、カードに書いてある数字をスラッシュ区切りで並べたものです。
出力は、
1232
のような感じです。最も近い数が2つある場合は、小さい順に両方共出力してください。
1233,1235
のような感じです。
末尾の改行はあってもなくても構いません。
作れる数がひとつもない場合には、-を出力してください。
【補足】
「01」のような、「0」で始まる二桁以上の数は作れません。一桁の「0」はOKです。
カードの枚数は8枚以下です。
n は 1以上で、カードの枚数を超えることはありません。
m は 0以上、10の9乗以下です。
6 のカードを逆さにして 9 として使ったりすることはできません。
不正な入力に対処する必要はありません。
Rubyで解答しています。
#!/usr/bin/ruby
def toNum(ptn)
if (ptn.size > 1) && (ptn.last == 0) then return -1 end
ret = 0
ptn.each_with_index{|n, i|
ret += n * (10**i)
}
return ret
end
def solve(n,m,cards)
ret = []
bs = 9999999999
cards.permutation(n){|ptn|
v = toNum(ptn)
if v<0 then next end
s = (m-v).abs
if s < bs then
ret = [v]
bs = s
elsif s == bs then
ret << v
end
}
return ret.uniq.sort
end
def printResult(ptn)
if ptn.empty? then
puts("-")
else
puts(ptn.join(","))
end
end
while line = gets
line.strip!
if line.empty? then next end
sc = line.split(",")
n = sc[0].to_i
m = sc[1].to_i
cards = sc[2].split("/").map{|i| i.to_i}
ret = solve(n,m,cards)
printResult(ret)
end
問題に簡単と書かれている通りそれほど難しくありません。
計算量も8!しかないので総当たりで大丈夫です。単純に全パターン列挙するので入力値mに近いかどうかはmと列挙した値の差の絶対値でチェックすれば大丈夫です。
引数n,m,cardsは入力値をパースして数値にしたものです。
cardsは[1,2,2,3,9,9,9]のようなカードの値の配列です。
Rubyなのでcardsにpermutation()を使ってパターンを列挙します。
そしてtoNum()でパターンを数値に変換します。toNum()はエラー値として-1を返すので-1が帰った時は無視します。
そして帰ってきた値（v）とmの差の絶対値を取り、以前の差の絶対値より小さくなっていたら結果を更新します。以前の差の絶対値と同値なら結果に追加します（20〜26行目）。
結果は同じ値が重複していたり、順番が昇順になっていないのでuniqしてsortしてから返します。
パターンは配列でくるので1つずつを各桁の値として数値に変換します（7〜9行目）。なお、プログラムでは配列の最初の桁が1の位、2つ目が10の位、…、となります。
ただし、1桁の値でない限り戦闘に0はおけないという仕様なので4行目でチェックして先頭（配列の最後の要素）が0ならエラーリターンします。
これを書いている時に気付きましたが、パターンを数値に直すのは配列をcardsを数値に変換せず文字列のまま扱って、joinしてto_iすれば済んでいました。Rubyを始めてから結構Rubyでプログラムを書いたと思いますが、頭の中で考えるコードはC/C++とJavaに近い言語のままのようです。