← 返回题目列表

Codeforces · 41/D

D. 典当

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

在棋盘最下面一排的某个方格上立着一个棋子。它只有两种移动方式:向上向左或向上向右。棋子可以选择从最低行的哪个方格开始其旅程。每个方格上放有 0 到 9 个豌豆。棋子想要到达最上面一排并收集尽可能多的豌豆。由于它必须将豌豆分配给它自己和它的 k 个兄弟,因此豌豆的数量必须能被 k + 1 整除。找出它能够收集的最大豌豆数量以及它应该采取哪些动作来做到这一点。

棋子不能扔掉豌豆或离开棋盘。当一个棋子出现在棋盘的某个方格(包括该路的第一个和最后一个方格)时,它必然会吃掉所有的豌豆。

输入

第一行包含三个整数 n、m、k (2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10) — 棋盘上的行数和列数,棋子的兄弟数。然后n行包含从0到9的每m个数字,不带空格——棋盘的描述。每个方块都由一个数字来描述——其中豌豆的数量。第一行对应于最上面的行,最后一行对应于最低行。

输出

如果不可能到达收集到可被 k + 1 整除的豌豆数量的最高行,则打印 -1。

否则,第一行必须包含一个数字 - 棋子可以收集的豌豆的最大数量,前提是该数字必须能被 k + 1 整除。第二行必须包含一个数字 - 最低行中方格列的编号,棋子必须从该列开始其旅程。列从左到右编号,整数从 1 开始。第三行必须包含由 n - 1 个符号组成的行 — 棋子移动的描述。如果棋子必须向上和向左移动,则打印 L;如果它必须向上和向右移动,则打印 R。如果该问题有多种解决方案,请打印其中任何一个。

示例

输入 #1

3 3 1
123
456
789

输出 #1

16
2
RL

输入 #2

3 3 0
123
456
789

输出 #2

17
3
LR

输入 #3

2 2 10
98
75

输出 #3

-1