#P1210. Problem J. 你说的对,但是数据(又)丢了

Problem J. 你说的对,但是数据(又)丢了

Problem J. 你说的对,但是数据(又)丢了

时间限制 : 1000 ms

空间限制 : 256 MB

题目描述

在2023年的迎新生赛中,有这么一道题:

给定一个整数,我们可以将其分成多个部分,如我们可以将 1234567812345678 拆分成3个部分,可以分成 1212 , 343456785678123123 , 4564567878等等。

现在你的目标是:将这个整数拆分成 mm 个部分(可以包含前导0),这 mm 个部分的数加起来是个偶数,请你找出有多少种拆分方法。

在简单版本中,输入格式如下:

第一行两个整数 nnmmnn 代表整数的长度,mm 含义见描述。

在本题中, mm只会等于2或者3

第二行一个长度为 nn 的整数,代表要拆分的数。

例如对于以下输入数据:

8 2
12345678

有三种拆分方法:

12+345678=34569012 + 345678 = 345690

1234+5678=69121234 + 5678 = 6912

123456+78=123534123456 + 78 = 123534

众所周知 ,小季在去年把某道题目的输入数据弄丢了,于是最后只能让大家帮忙造输入数据。今年,小季在准备困难版本的题目时,想将简单版本的数据拿过来直接修改,结果发现输入数据又丢了。所以,只能让大家再感受一下出数据的快乐了。

输入格式

输入一个整数,代表拆分方法个数 AA (1A10101 \le A \le 10^{10})。

输出格式

如果存在一个长度小于等于 10510 ^5 的整数拆成 22 部分或者 33 部分的方案个数为 AA,则输出两行:

第一行包括两个整数 nn, mm(1n1051 \le n \le 10^5, m=2m=233),分别代表整数的长度和拆成的部分数;

第二行为满足条件的长度为 nn 的数字串,注意不能有前导0

如果有多种满足条件的答案,只需要输出其中一种即可。

否则,如果找不到方案数为 AA 的整数,则输出 1-1

样例输入1

3

样例输出1

8 2
12345678

样例输入2

16

样例输出2

10 3
1921022500