CF852A.Digits
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
John gave Jack a very hard problem. He wrote a very big positive integer _A_0 on a piece of paper. The number is less than 10200000 . In each step, Jack is allowed to put ' + ' signs in between some of the digits (maybe none) of the current number and calculate the sum of the expression. He can perform the same procedure on that sum and so on. The resulting sums can be labeled respectively by _A_1, _A_2 etc. His task is to get to a single digit number.
The problem is that there is not much blank space on the paper. There are only three lines of space, so he can't perform more than three steps. Since he wants to fill up the paper completely, he will perform exactly three steps.
Jack must not add leading zeros to intermediate results, but he can put ' + ' signs in front of digit 0. For example, if the current number is 1000100, 10 + 001 + 00 is a valid step, resulting in number 11.
约翰给杰克出了一道非常难的题目。他在一张纸上写下一个非常大的正整数 A0,该数小于 10200000。在每一步中,杰克可以在当前数字的某些(也可能不加)数字之间插入 + 号,并计算该表达式的和。他可以对得到的和重复执行相同的操作,依此类推。所得的各次和依次记为 A1,A2 等。他的任务是最终得到一个一位数。
问题是纸上的空白空间非常有限——仅有三行空间,因此他最多只能执行三步操作。由于他希望将纸面完全填满,他将恰好执行三步。
杰克不得在中间结果中添加前导零,但他可以在数字 0 前插入 + 号。例如,若当前数字为 1000100,则 10+001+00 是一个合法的操作,其结果为数字 11。
输入格式
First line contains a positive integer N (1 ≤ N ≤ 200000), representing the number of digits of _A_0.
Second line contains a string of length N representing positive integer number _A_0. Each character is digit. There will be no leading zeros.
第一行包含一个正整数 N(1≤N≤200000),表示 A0 的位数。
第二行包含一个长度为 N 的字符串,表示正整数 A0。每个字符均为数字,且不含前导零。
输出格式
Output exactly three lines, the steps Jack needs to perform to solve the problem. You can output any sequence of steps which results in a single digit number (and is logically consistent).
Every step consists of digits and ' + ' signs. Steps should not contain several ' + ' signs in a row, whitespaces, or ' + ' signs as the first or last character. They also need to be arithmetically consistent.
Solution might not be unique. Output any of them in that case.
输出恰好三行,即 Jack 解决该问题所需的步骤。你可以输出任意一个能最终得到一位数字(且逻辑上自洽)的操作序列。
每一步均由数字和 + 号组成。步骤中不得包含连续多个 + 号、空格,也不得在开头或结尾处出现 + 号。此外,每一步还必须满足算术一致性。
解可能不唯一;若如此,请任选其一输出。
输入输出样例
输入#1
1 1
输出#1
1 1 1
输入#2
4 5806
输出#2
5+8+0+6 1+9 1+0
说明/提示
In the first sample, Jack can't put ' + ' signs anywhere, so he just writes 1 in each line and solves the problem. Here, solution is unique.
In the second sample, Jack first puts ' + ' between every two consecutive digits, thus getting the result 5 + 8 + 0 + 6 = 19. He does the same on the second step, getting 1 + 9 = 10. Once more, he gets 1 + 0 = 1, so after three steps, the result is 1 and his solution is correct.
在第一个样例中,Jack 无法在任何位置插入加号(‘ + ’),因此他只能在每一行都只写数字 1 并完成题目。此时解是唯一的。
在第二个样例中,Jack 首先在每两个相邻数字之间插入加号,从而得到结果 5 + 8 + 0 + 6 = 19;第二步中,他同样操作,得到 1 + 9 = 10;再进行一次该操作,得到 1 + 0 = 1。因此,经过三步后结果为 1,他的解法是正确的。
输入解题思路,AI测评打分。不知道怎么写?