← 返回题目列表

Codeforces · 1301/D

D. 运行时间

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

巴沙尔正在为全国编程大赛练习。由于坐在电脑前太多,没有做任何身体动作,而且吃得很多,巴沙尔变得胖了很多。巴沙尔将在全国比赛后退出节目,他将成为一名演员(就像他的父亲一样),所以他应该减肥。

为了减肥,巴沙尔准备跑步$$$k$$$公里。 Bashar 将在一个看起来像 $$$n$$$ 行和 $$$m$$$ 列的网格的地方运行。在该网格中,每对相邻的单元格之间有两条长度为一公里的单向道路,一条道路从第一个单元格到第二个单元格,另一条道路从第二个单元格到第一个单元格。因此,总共有 $$$(4 n m - 2n - 2m)$$$ 条道路。

例如,$$$n = 3$$$ 和 $$$m = 4$$$。在本例中,有 $$$34$$$ 条道路。这是本案例的图片(箭头表示道路):

巴沙尔希望遵守以下规则:

- 他从网格左上角的单元格开始;
- 巴沙尔一步可以向上(符号“U”)、向下(符号“D”)、向左(符号“L”)或向右(符号“R”)。更正式地说,如果他站在 $$$i$$$ 行和 $$$j$$$ 列的单元格中,即单元格 $$$(i, j)$$$ 中,他将移动到: 在“U”的情况下,移动到单元格 $$$(i-1, j)$$$; 在“D”的情况下,到单元格$$$(i+1, j)$$$; 在“L”的情况下,到单元格$$$(i, j-1)$$$; 在“R”的情况下,到单元格$$$(i, j+1)$$$;
- 他想要精确地跑 $$$k$$$ 公里,因此他想要精确地进行 $$$k$$$ 移动;
- 巴沙尔可以在网格的任何单元格中完成比赛;
- 他无法离开网格,所以在任何时候他都应该在某个单元格上;
- 巴沙尔不想在跑步时感到无聊,所以他不能两次访问同一条路。但他可以多次访问同一个牢房。

巴沙尔询问您是否可以按照这样的规则运行。如果可以的话,你应该告诉他该怎么跑。

你应该给他$$$a$$$ 要做的步骤,并且由于Bashar 记不住太多步骤,所以$$$a$$$ 不应超过$$$3000$$$。在每一步中,你应该给他一个整数 $$$f$$$ 和一个长度最多 $$$4$$$ 的移动字符串 $$$s$$$,这意味着他应该重复字符串 $$$s$$$ 中的移动 $$$f$$$ 次。他将按照您打印的顺序执行这些步骤。

例如,如果步骤是$$$2$$$ RUD、$$$3$$$ UUL,那么他要移动的动作是 RUD $$$+$$$ RUD $$$+$$$ UUL $$$+$$$ UUL $$$+$$$ UUL $$$=$$$ RUDRUDUULUULUUL。

你能帮助他并给他一个正确的移动顺序,使他跑的总距离等于 $$$k$$$ 公里,或者说这是不可能的?

输入

唯一一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 500$$$, $$$1 \leq k \leq 10 ^{9}$$$),分别是网格中的行数和列数以及巴沙尔想要运行的总距离。

输出

如果没有可能跑 $$$k$$$ 公里,则在第一行打印“NO”(不带引号),否则打印“YES”(不带引号)。

如果答案为“是”,则在第二行打印一个整数 $$$a$$$ ($$$1 \leq a \leq 3000$$$) — 步骤数,然后打印 $$$a$$$ 描述步骤的行。

要描述一个步骤,请打印一个整数 $$$f$$$ ($$$1 \leq f \leq 10^{9}$$$) 和长度最多为 $$$4$$$ 的移动字符串 $$$s$$$。 $$$s$$$ 中的每个字符都应该是“U”、“D”、“L”或“R”。

Bashar 将从左上角的单元格开始。确保精确移动 $$$k$$$ 步,不要访问同一条道路两次,也不要超出网格范围。他可以在任何牢房完成任务。

我们可以证明,如果可以精确地运行 $$$k$$$ 公里,那么就有可能在这种输出约束下描述路径。

示例

输入 #1

3 3 4

输出 #1

YES
2
2 R
2 L

输入 #2

3 3 1000000000

输出 #2

NO

输入 #3

3 3 8

输出 #3

YES
3
2 R
2 D
1 LLRR

输入#4

4 4 9

输出#4

YES
1
3 RLD

输入 #5

3 4 16

输出 #5

YES
8
3 R
3 L
1 D
3 R
1 D
1 U
3 L
1 D

注意

巴沙尔在第一个例子中要走的棋是:“RRLL”。

在第二个示例中不可能跑 $$$1000000000$$$ 公里,因为道路总长度较小,Bashar 不能在同一条道路上跑两次。

巴沙尔在第三个例子中要走的棋是:“RRDDLLRR”。

巴沙尔在第五个例子中要走的棋是:“RRRLLLDRRRDULLLD”。是他跑步的照片(这条路用红色标出,并按照他跑步的顺序编号):