← 返回题目列表

AtCoder · abc024_d

D. 动态规划

中文机器翻译题面 查看原题
(21:52) 发现法官使用的样本测试用例之一与问题文本中的不一样。对于给您带来的不便,我们深表歉意。请注意,测试用例本身是正确的,因此不会进行重新判断。注意。

問題文

高桥君纵横 10^8 我决定使用带有正方形的方格纸来解决以下问题。

``重复从左下方格开始向右或向上移动一个方格的操作,并计算到达每个方格的方式数。 除以 1,000,000,007 求余数。 ”

高桥喜欢动态规划,所以他立即意识到这个问题可以用动态规划来解决。

具体来说

  1. 属于最左列或最底行的所有单元格 写入 1 。
  2. 如果对于尚未写入的方格,左侧方格和底部方格都写入了整数,则 2 平方和 将除以1,000,000,007 得到的余数写在该方格中。
  3. 重复步骤 2,直到所有方格上都写有整数。 可以使用算法

找到答案。

高桥先生使用上述算法计算从左下角到达每个方格的方法数。 写入“除以 1,000,000,007 时的余数”。

完成的方格纸的左下部分如下图所示。

但是当我写完之后,我非常兴奋,有成就感,以至于我把方格纸撕掉了一部分。

高桥的手里,有一张方格纸,上面只有某个方格,上面的方格,以及右边的方格都写在上面。

高桥想把这张纸放回原来的位置,但方格纸太大了,他不知道该放哪里。

根据碎片上的信息,找出该碎片位于原始方格纸上从左侧算起有多少个方格,从底部算起有多少个方格。

即从左开始x从下面看正方形y关于方块 如果你写 (x, y) , 给出了写在方格(r, c)、(r, c + 1)、(r + 1, c)中的整数,所以 查找 r 和 c 。

左下方的方块是 (0, 0) 。


入力

输入是按以下格式从标准输入给出的。

A
B
C
  • 1 在线 写在方格 (r, c) 中的整数 有一个答案 A(0 ≦ A < 1,000,000,007) 。
  • 2 在线 写在方格 (r, c + 1) 中的整数 有一个答案 B(0 ≦ B < 1,000,000,007) 。
  • 3 在线 写在方格 (r + 1, c) 中的整数 有一个答案 C(0 ≦ C < 1,000,000,007) 。
  • 0 ≦ r, c < 99,999,999似乎有一个答案 A, B, C 。

出力

指示片段的原始位置。 输出 2 整数 r(0 ≦ r < 99,999,999) 和 c(0 ≦ c < 99,999,999) 以空格分隔。 可能的答案 如果有多个 r, c ,其中 输出 r 最小的那个。 还是答案 如果 1 未确定,r是最小的之一 输出 c 最小的那个。 在输出末尾添加换行符。


入力例1

15
35
21

出力例1

4 2

高桥手中的碎片如下图。

下面显示的位置是原始位置。


入力例2

126
252
210

出力例2

5 4

入力例3

144949225
545897619
393065978

出力例3

314159 365358