← 返回题目列表

AtCoder · arc007_4

D. 撕毁的作业

中文机器翻译题面 查看原题

問題文

 高桥先生正在解答他的数学作业,其中回答了算术级数的第一项和公差。
 相邻 2 两个数字之差为常数的一系列数字称为算术级数。第一个数字称为第一项,作为常数的数字之间的差称为公差,最后一个数字称为最后一项。
 然而,高桥粗心地没有将作业中的数字序列用空格或逗号分隔。 由数字 0到 9 组成 1 我把它作为一个字符串复制到我的笔记本中。
 此外,我对笔记本很马虎,所以我把它撕了一部分并把它分开了。
 经确认,只有第一项和最后一项被撕开并分开,并且至少第一项的一部分被保留下来。
 给定这样一个字符串,猜测原始序列并回答它的第一项和公差。

 第一项和容差是 它是大于或等于 1 的整数。如果有多个解,请回答第一项最小的一个。如果有多个解具有相同的第一项,则回答具有最小公差的解。
 另外,003 呀 不必要的,例如 012 复制的编号序列中不包含以 0 开头的号码。

入力

输入将以以下格式从标准输入给出。
c_{0}c_{1}‥‥c_{N-1}
  • 输入是 1 仅作为行中算术级数一部分的长度 给出了字符串 N 。
  • 该字符串是 它由 0-9 组成。

部分点

测试数据包括以下内容: 4 每个数据集中包含的测试数据是如下所示的字符串。 N 范围不同。
如果某个测试数据集中包含的所有测试数据都能输出正确答案,则即使其他测试数据集输出错误答案,也会按如下方式给出部分分数。
  • 级别 1 ( 25 点) : 1≦N≦4
  • 级别2 ( 25 点) : 1≦N≦6
  • 3 级 ( 25 点) : 1≦N≦200
  • 级别4 ( 25 点) : 1≦N≦1,000

出力

对于第一项和最后一项可能被分隔的算术级数,可能的第一项和公差被发送到标准输出,并以空格分隔。 1 按行输出。
如果有多个解,则输出第一项最小的一个。如果有多个解具有相同的第一项,则输出具有最小公差的解。
请在末尾输出换行符。

入力例 1

1

出力例 1

1 1
  • 字符如下 1 可能有两个数字,但最小的第一项是 1 。
  • 容差可以是任何正整数,但最小容差是 1 。

入力例 2

0203

出力例 2

10 10
  • 02 不被识别为数字,因此 2 不是第一个术语。
  • 第一学期 10 的 1 被分开,并且作为最后一项 30 的 0 是分离后的序列,原始序列是 102030。

入力例 3

456789101112131415

出力例 3

4 1
  • 序列的第一项在任何地方都没有丢失 它是 4、公差 1 的算术级数。

入力例 4

579111315171921232

出力例 4

5 2
  • 在最后一节中 这是一个缺少 25 的 5 部分的算术级数。

入力例 5

001131261391521651

出力例 5

100 13
  • 第一学期 100 和最后一个学期 178 的一部分丢失。