设 $x$ 的十进制位为 $d_0d_1\ldots d_{n-1}$ （从高位到低位）。总数位和为 $S$ 。
想要 $y<x$ 且数位和等于 $S$ ，一种稳定构造是：在某个位置 $i$ （ $0 \le i \le n-2$ ）把高位 $d_i$ 减去 $1$ （要求 $d_i \ge 1$ ），然后把后缀位置 $i+1\ldots n-1$ 的数位重新分配，使后缀的和增加 $1$ 。这样整体和不变，且由于第 $i$ 位变小，必有 $y<x$ 。
若记原后缀和为 $R=\sum_{j=i+1}^{n-1} d_j$ ，新后缀目标和为 $R+1$ 。只要后缀长度 $L=n-i-1$ 满足
$R+1 \le 9L,$

P3497.第1题-bigbong的数组

1000ms

Difficulty: 5

所属公司 : 饿了么

算法与标签>构造

题目内容

$Bingbong$ 给定 $x$ ，构造一个非负整数 $y(y < x)$ ，使得 $x$ 和 $y$ 的数位和相等。

一个整数 $x(0≦x≤10^{100000})$ ，表示给定的整数。

若存在满足条件的 $Y$ ，输出任意一个，否则输出" $-1$ "。

输入

输出

-1

说明

输入

输出

输入

预期输出（选填）