009 - パスワードをお忘れですか?
時間制限 1 秒 / メモリ制限 64 MB / 得点 12 / x 0 /
問題
二郎君は数式を用いたセキュリティシステムを開発した。システムにはa、b、c、dを変数とする数式が設定されており、それぞれに0から9までの整数を入力すると計算が行われる。その計算結果が正の整数N と一致したとき、ロックが解除される。ロックを解除できる4つの整数をa,b,c,dの順に並べた4桁の数字の列がパスワードになる。
二郎君はこのシステムで彼が使っているパスワードを忘れてしまった。幸い、二郎君はシステムに設定されている数式と、$N$ の値は覚えていたので、それを使ってパスワードを特定しようと考えた。
システムに設定されている数式と正の整数Nが与えられたとき、パスワードの候補の数を求めるプログラムを作成せよ。
入力
入力は以下の形式で標準入力から与えられる。
$S$ $N$
1行目にシステムに設定されている数式を表す文字列$S$が与えられる。2行目に、整数$N(1 \leq N \leq$ 10,000,000,000,000,000,000 = 1016
$S$は算術式を表す文字列であり、以下の要素から構成される。
- 加減乗算(それぞれ +, -, *)
- カッコ「(」または「)」
- 0から10,000までの整数
- 変数a,b,c,d
- 変数の連結
変数が連続して与えられた場合は変数の連結を表し、それらの変数の値を並べてできる一つの数とみなす。たとえば、a=0、b=1、c=2なら、abcは一つの整数12を表す。
また、$S$は以下の条件を満たす。
- 符号を反転する記号として演算子-が使われることはない。
- 乗算を表すときに演算子*が省略されることはない。
- Sの長さは200以下である。
- 乗算演算子*は2回までしか現れない。
- 変数が連続するのは4つまでである(たとえば、abcda, aaabb, aaaaaaのようなものは与えられない)。
- 空白文字は含まれない。
- 変数の連結を除いて、通常の数式である。
出力
パスワードの候補の数を1行目に出力する。パスワードがひとつに特定できる場合は、それを2行目に出力する。
入出力例
入力例1
a+b+c+d 36
出力例1
1 9999
入力例2
a+b+c+d 5
出力例2
56
式a+b+c+dが5になるのはa=b=c=0,d=5のときだが、他にもa=b=c=1,d=2などでも5になるので、合計で56通りの候補が存在する。
入力例3
b+c+d 27
出力例3
10
式b+c+dが27になるのはb=c=d=9のときだが、aの選び方は任意なので10通りの候補が存在する。
入力例4
abcd+abcd 1024
出力例4
1 0512
式abcd+abcdが1024になるのはa=0,b=5,c=1,d=2のときだけなので、候補は1つだけであり、0512が唯一のパスワードである。