#abc024d. [abc024_d]動的計画法
[abc024_d]動的計画法
翻译
(21:52)发现在用于判断的样例测试用例中有一个与问题描述不同。给您带来不便,深感抱歉。但请注意,测试用例本身是正确的,因此不会重新判断等。请谅解。
问题描述
高桥君决定使用一张有高度和宽度各个格子的方格纸来解决以下问题。
"从最左下角的格子开始,每次向右或向上移动一格,求到达每个格子的路径数量除以后的余数。"
由于高桥君喜欢动态规划,他马上意识到这个问题可以用动态规划来解决。
具体地,
- 对于属于最左列或最下行的所有格子,将其设为1。
- 对于还没有写入整数的格子,如果其左边格子和下面格子都有整数,则将这两个格子的和除以后的余数写入该格子。
- 重复步骤2,直到没有空白格子为止。
通过上述算法,高桥君将"到达每个格子的路径数量除以后的余数"写入了所有格子。
完成后的方格纸的左下部分如下图所示。
然而,在完成写入后,高桥君为了达成感而兴奋地跳起来,结果不小心撕破了方格纸的一部分。
高桥君手上有一个碎片,上面写着某个格子以及其上方和右侧格子的信息。
高桥君希望将这个碎片放回原位,但是方格纸太大了,他不知道应该放在哪里。
请根据碎片的信息,求出这个碎片最初位于方格纸中从左边数的第几个格子和从下面数的第几个格子的位置。
换句话说,设从左边数第个格子,从下面数第个格子表示为,给定、、三个格子中的整数,请求出和。
请注意,最左下角的格子是。
输入
输入以以下格式从标准输入中给出。
- 第1行给出了整数,代表的格子中的整数。
- 第2行给出了整数,代表的格子中的整数。
- 第3行给出了整数,代表的格子中的整数。
- 给定的满足,对应位置存在符合条件的答案。
输出
以空格分隔的两个整数和表示碎片最初位于方格纸中的位置。如果有多个可能的答案,则输出最小的答案。如果仍然无法确定答案,则输出最小且最小的答案。输出最后要换行。
输入例1
15
35
21
输出例1
4 2
高桥君手上的碎片如下图所示。
原来的位置如下图所示。
输入例2
126
252
210
输出例2
5 4
输入例3
144949225
545897619
393065978
输出例3
314159 365358