COMPRESS

ID: 1320

传统题

1000ms

256MiB

难度: 10

上传者:

标签>

字符串

数论

Rocky Mountain 2003

减少数字的位数。

一位实验物理学家从他进行的实验中生成了大量数据。这些实验产生的数据具有一个特殊属性，他希望利用这个属性来减少存储结果所需的空间。

数据以数字对的形式生成，其中第一个数字总是小于第二个数字。物理学家存储这些数字的方式类似于人们在书中缩写数字范围的方式。例如，当他们提到书中的第11页到第18页时，有时会将其表示为11-8。

定义	示例
一对数字中的第一个数用 $F$ 表示。	在"18482-02"中， $F = 18482$
一对数字中的第二个数（压缩形式）用 $C$ 表示。	在"18482-02"中， $C = 02$
一对数字中的第二个数（解码形式）用 $R$ 表示。	在"18482-02"中， $R = 18502$
$MSD(x,y)$ 指当 $y$ 以十进制表示时， $y$ 的前 $x$ 位最高有效数字。当 $x \leq 0$ 时，为空字符串。	$MSD(3,19283) = 192$ , $MSD(0,12) = ''$
$LSD(x,y)$ 指当 $y$ 以十进制表示时， $y$ 的后 $x$ 位最低有效数字（可能用零填充）。	$LSD(2, 48290) = 90$ , $LSD(2,3) = 03$

规则	示例
数字 $C$ 总是以尽可能少的位数书写。	-
如果数字 $C$ 大于 $F$ ，则 $R$ 与 $C$ 相同。	给定"123-283"，则 $F=123$ ， $C=283$ ， $R$ 为283
如果 $C$ 小于或等于 $F$ ，则应用以下规则：	-
$LSD(length(C), R)$ 始终与 $C$ 相同。	-
如果 $LSD(length(C), F)$ 小于 $C$ ，则 $R$ 等于 $MSD(length(F) - length(C), F)$ ，并在 $C$ 的数字前加上这个值。	给定："4137-223"，则： $F=4137$ ， $C=223$ $LSD(length(C),R) = 223$ $MSD(4 - 3, 4137) = 4$ $R$ 为4223
如果 $LSD(length(C), F)$ 大于或等于 $C$ ，则 $R$ 等于在以下值上加上 $10^{length(C)}$ ： $MSD(length(F) - length(C), F)$ ，并在 $C$ 的数字前加上这个值。	给定："8543-13"，则 $F=8543$ ， $C=13$ $LSD(length(C),R) = 13$ $MSD(4 - 2, 8543) = 85$ $10^{2} = 100$ $R$ 为 $8513 + 100 = 8613$

请注意，数字 $C$ 上的前导零是有意义的。'7'与'07'不同，它们与'007'也不同。例如：

你的任务是根据未压缩的版本计算"压缩"的第二个数字格式。

输入的每一行将由一对用连字符分隔的非负整数组成，其中第二个数字总是大于第一个数字。第二个数字将始终小于 $2^{31}-1$ 。

输入的每一行将产生一行输出。每行输出将由第一个数字，后跟一个连字符，再后跟第二个数字的"压缩"版本组成。

10-18
83294-84137
100-200

10-8
83294-137
100-00

问：问题4指出 $C$ 总是以最少的位数书写。给出的例子 $f=4137$ ， $c=223$ 得到 $r=4223$ 。但是如果输入是4137-4223， $C$ 的最小位数是23。是否有这样的测试用例？

答：确实，4137-223不是范围4137-4223的最小可能表示，但是，给定4137-223，正确的解压缩是4137-4223。

一个生成4137-223的程序将被判定为不正确，因为4137-23是这个范围的最短压缩表示。

#P2319. COMPRESS