← 返回题目列表

Codeforces · 1120/B

B. 一旦进入赌场

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

一名玩家来到赌场,发现一台老虎机,一切都取决于他如何玩。规则如下。

屏幕上最初出现一个正整数 $$$a$$$。玩家可以将一枚硬币放入机器中,然后将 $$$1$$$ 添加到或减去 $$$1$$$ 的任意两个相邻数字。执行此操作后,所有数字必须保持在 $$$0$$$ 到 $$$9$$$ 之间,并且前导数字不得为零。换句话说,禁止将 $$$1$$$ 添加到 $$$9$$$、从 $$$0$$$ 减去 $$$1$$$ 以及从前导 $$$1$$$ 减去 $$$1$$$。一旦屏幕上的数字等于 $$$b$$$,玩家就赢得了大奖。 $$$a$$$ 和 $$$b$$$ 具有相同的位数。

帮助玩家确定赢得头奖所需花费的最少硬币数量并告诉玩家如何玩。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) 代表数字 $$$a$$$ 和 $$$b$$$ 的长度。

接下来的两行包含数字 $$$a$$$ 和 $$$b$$$,每个数字位于单独的行上 ($$$10^{n-1} \le a, b < 10^n$$$)。

输出

如果不可能赢得大奖,则打印单个整数 $$$-1$$$。

否则,第一行必须包含玩家必须花费的最小可能数量 $$$c$$$ 的硬币。

$$$\min(c, 10^5)$$$ 行,其中 $$$i$$$ 行包含两个整数 $$$d_i$$$ 和 $$$s_i$$$ ($$$1\le d_i\le n - 1$$$, $$$s_i = \pm 1$$$) 表示第 $$$i$$$ 行步骤中,玩家应将 $$$s_i$$$ 添加到左侧的第 $$$d_i$$$ 和第 $$$(d_i + 1)$$$ 位数字(例如 $$$d_i = 1$$$ 表示两个前导数字发生变化,而 $$$d_i = n - 1$$$ 表示有两个尾随数字发生变化)。

请注意,答案可能非常大,如果 $$$c > 10^5$$$,您应该只打印前 $$$10^5$$$ 动作。如果能够以尽可能少的硬币完成打印的动作并赢得大奖,则您的答案被认为是正确的。特别是,如果有多种方法可以执行此操作,则可以输出其中任何一种。

示例

输入 #1

3
223
322

输出 #1

2
1 1
2 -1

输入 #2

2
20
42

输出 #2

2
1 1
1 1

输入 #3

2
35
44

输出 #3

-1

注意

在第一个示例中,我们可以对前两位进行 +1 运算,将数字 $$$\textbf{22}3$$$ 转换为 $$$\textbf{33}3$$$,然后对最后两位进行 -1 运算,将 $$$3\textbf{33}$$$ 转换为 $$$3\textbf{22}$$$。

也可以以相反的顺序执行这些操作,这给出了另一个正确答案。

在最后一个示例中,可以表明不可能将 $$$35$$$ 转换为 $$$44$$$。