会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい数字が大好きだ。そんなゆう君は最近、表に0から9までのいずれかの数字の書かかれたプレートをn枚購入してn桁の数を作る遊びに熱中している。 今月もゆう君は貰ったお小遣いでn枚のプレートを買いに行こうと考えていた。
プレートは表に書かれている数字によって値段が異なる。 それらを使って作れるn桁の数をできる限り小さくしたい。 ゆう君の所持金額と各プレートの値段、購入するプレートの枚数が与えられるので、そこから作ることのできる数の最小値を求めよ。
購入するプレートの値段の総和が所持金額を超えなければ自由にプレートを購入できる。 同じ数字の書かれたプレートを複数枚購入しても良い。
プレートは必ずn枚購入しなければならない。n枚購入できない場合は "NA" と出力すること。
購入後はn枚のプレートを任意の順番で一直線上に並べる。 そうしてできる数字の列を10進数の数とし、その値が最小になるようにしたい。 先頭に1つ以上の0が連続していても良い。 ( 例えば 0019 なら 19 となり, 0000 なら 0 として考える )
図1は0、1、9のプレートを購入した場合についての説明である。
図1 : 0,1,9のプレートを購入した場合 |
この問題を解くに当たって、以下のことを参考にしても良い。 整数値を文字列に変換する方法を示す。 value を文字列として str に代入する。
#include<stdio.h> int main(){ int value = 123; // この値を文字列に変換する char str[6]; // この変数に value を文字列にしたものが入る sprintf(str,"%d",value); return 0; }
#include<sstream> using namespace std; int main(){ int value = 123; // この値を文字列に変換する string str; // この変数に value を文字列にしたものが入る stringstream ss; ss << value; ss >> str; return 0; }
class Main { public static void main(String args[]){ int value = 123; // この値を文字列に変換する String str = new Integer(value).toString(); // この変数に value を文字列にしたものが入る } }
n m c0 c1 c2 ... c9
1行目に2つの整数 n ,m が空白区切りで与えられる。n は購入するプレートの枚数, m はゆう君の所持金額を表す。
2行目には10個の整数が空白区切りで与えられる。 ci ( i は0以上9以下 ) は表に i が書かれたプレートの値段を表す。
入力は以下の条件を満たす。
n枚のプレートを購入し、それらを任意の順番で並べることでできる数の値の最小値を出力せよ。
先頭にいくつかの0を含む場合はそのまま出力すること。 ( 例えば答えが 0019 の場合は先頭の0を取り除いて 19 とするのではなく、そのまま 0019 と出力すること ) 所持金額では n 枚プレートを購入できない場合は "NA" と出力すること。
1 10 1 2 3 4 5 6 7 8 9 10
0
3 10 8 4 5 3 5 6 9 10 11 2
119
5 30 25 51 32 9 2 1 10 2 5 10
04555
5 100 101 101 101 101 101 101 101 101 101 101
NA