#P220. Lucky Number
Lucky Number
Lucky Number
题目描述
致远觉得他有个lucky number,会给他带来幸运,他会给出一个数 a,以及一个长度为 b 的 01 串 S。
简单的说,他的 Lucky Number 是满足以下条件的正整数 n:
n 的位数为 b 且不含前导 0。
若 S 的第 i 位为 1,则 n 的前 i 位组成的数是 a 的倍数,否则 n 的前 i 位组成的数不是 a 的倍数。
对于一个数,前 i 位组成的数是指这个数前 i 个数码依次拼接形成的数。例如 3123111 前 3 位组成的数为 312,前 5 位组成的数为 31231。
现在,请你帮助致远计算一下,他的 Lucky Number 是多少。
由于满足条件的数可能会有多个,你需要输出最小的一个。若不存在,则请输出 -1
输入格式
输入数据由两行构成。
第一行两个整数 a,b,意义见题目描述。
第二行一个长度为 b 的字符串 S。
输出格式
一行,满足条件的最小的数 n。如果不存在满足条件的数,输出 -1。
数据范围
(原站未提供,导入后需人工补齐)
样例
2 2
01
10
10 1
1
-1
6 6
110100
601210
提示
【样例解释】
对于样例一,10是 2 位数,且 10 的前 1 位组成的数 1 不是 2 的倍数,而前 2 位组成的数 10 是 2 的倍数。由于 10 已经是最小的两位数,故不存在比 10 更小的满足条件的数。
对于样例二,我们需要构造一个 1 位数,满足这个 1 位数能被10整除。显然,这样的数不存在。
对于全部数据,保证2≤a≤10,1≤b≤9,S中只包含0和1。