← 返回题目列表

Codeforces · 625/D

D. 算术期末考试

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

Vitya 正在三年级学习。在最后一节数学课上,所有学生都写了算术测验。 Vitya 是一个聪明的男孩,所以他很快就完成了所有任务,Oksana Fillipovna 给了他一个新任务,这要困难得多。

让我们将整数的翻转操作表示如下:数字以十进制表示法考虑,然后恢复。如果之后有任何前导零,它们将被丢弃。例如,如果我们翻转 123,结果是整数 321,但是翻转 130,我们得到 31,翻转 31,我们得到 13。

Oksana Fillipovna 选择了一些不带前导零的数字 a,并将其翻转以获得数字 ar。然后她对 a 和 ar 求和,并告诉 Vitya 结果值 n。他的目标是找到任何有效的a。

由于 Oksana Fillipovna 选择了一些小整数作为 a 和 ar,Vitya 很快就找到了答案,并对寻找一些通用算法来处理这个问题产生了兴趣。现在,他希望你编写一个程序,对于给定的 n 找到任何不带前导零的 a,这样 a + ar = n 或确定这样的 a 不存在。

输入

输入的第一行包含单个整数 n (1 ≤ n ≤ 10100 000)。

输出

如果不存在不带前导零的正整数 a 使得 a + ar = n 则打印 0。否则,打印任何有效的 a。如果有很多可能的答案,您可以选择任何一个。

示例

输入 #1

4

输出 #1

2

输入 #2

11

输出 #2

10

输入 #3

5

输出 #3

0

输入#4

33

输出#4

21

注意

在第一个样本 4 = 2 + 2 中,a = 2 是唯一的可能性。

在第二个示例 11 = 10 + 1 中,a = 10 — 唯一有效的解决方案。请注意,a = 01 是不正确的,因为 a 不能有前导零。

很容易检查出第三个样本中没有合适的a。

在第四个样本中 33 = 30 + 3 = 12 + 21,因此 a 有三种可能:a = 30、a = 12、a = 21。其中任何一个都被认为是正确答案。