#1201. 「HB 省队互测 2019 Round1 Day2」七星阵

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: huyufeifei

题目描述

北斗是一个精通阵法的女孩子。

你刚得到了一座城池,七星城。由于防卫力量不足,你想请北斗给七星城布置一座护城大阵。


布阵的核心在于一种具有奇异力量的石头,叫做“魂石”。魂石共有 9 种,用数字 1\sim 9 表示。数字越大,则威力也越大。一个阵法由若干个排成一排的阵位组成。每个阵位可以放入一块魂石,或者什么都不放,不放的位置应该用数字 0 表示。

阵法也有威力大小之分。首先,阵位多的阵法威力一定强于阵位少的阵法。其次,越靠左的阵位,对整个阵法的影响就越大。最左边的一个阵位叫做阵眼,阵眼处必须填入一块魂石,否则不能成阵。当两个阵法的阵位个数相同的时候,从左往右依次考虑每一个阵位,如果一个阵法在当前阵位的魂石威力强于另一个阵法,而之前的每一个阵位上的魂石威力都与另一个阵法相同,那么这个阵法就强于另一个阵法。特别地,当一个阵位没放魂石的时候,威力会弱于任一种魂石。

七星城一共有 n 个排成一排的可以放魂石的位置。你拥有足够的魂石,可以在每个位置放入任一种魂石,或者不放。放好之后,你可以截取任意可以成阵的连续一段位置,来构成一个阵法。但是威力太强的阵法你现在还无法控制,威力太弱的阵法又对守城没有帮助。所以你可以认为,威力比一个特定的阵法 r 还大的阵法和威力比另一个特定的阵法 l 还小的阵法都是无用的。

你能够截取出来的有用的阵法(以下简称“可用阵法”)越多,七星城的防卫力量就越强,且防卫力量的强弱跟可用阵法的个数有关,而跟每个可用阵法的威力和顺序无关。所以你需要一种放置魂石的方案,使得七星城的防卫力量最强。注意,如果同一个有用的阵法能够在不同的位置被截取出来,那么它将被计算多次。这些可用阵法之间可以共用魂石。

如果有多种摆放魂石的方案能够使防卫力量最大,你只需要让北斗布置其中最好布置的一种即可,因为布阵也是很累的。最好布置的定义类似于阵位威力的定义,从左往右依次考虑每一个位置,如果一种方案某个位置的魂石威力小于另一个方案这个位置的魂石威力,且之前所有位置的魂石威力都一样,那么就认为这种方案比另一种方案较好布置。

输入格式

输入文件共三行,第一行输入一个字符串,表示阵法 l 。第二行输入一个字符串,表示阵法 r 。第三行输入一个正整数 n

输出格式

输出两行。

第一行一个非负整数,表示最大防卫力量(最多可用阵法数)。

第二行一个长为 n 的字符串,表示在防卫力量最大条件下最好布置的魂石放置方案。

样例

样例 1 输入

1
10
3

样例 1 输出

3
101

样例 2 输入

1
11
3

样例 2 输出

5
111

样例 3 输入

12345
12346
6

样例 3 输出

1
012345

数据范围与提示

a l 的阵位个数, b r 的阵位个数。

测试点编号 n a,b 特殊性质
1\sim 2 \le 4 \le 4
3\sim 6 \le 2000 \le 800 l r 相同
7\sim 10 \le 4
11\sim 20 \le 800

对于全部数据:

保证所有的阵法只包含 0\sim 9 10 个字符。

保证 l r 都是合法的阵法(阵眼处有魂石),且 r 的威力不小于 l

n,a,b\ge 1