問題文
高桥君纵横 10^8 我决定使用带有正方形的方格纸来解决以下问题。
``重复从左下方格开始向右或向上移动一个方格的操作,并计算到达每个方格的方式数。 除以 1,000,000,007 求余数。 ”
高桥喜欢动态规划,所以他立即意识到这个问题可以用动态规划来解决。
具体来说
- 属于最左列或最底行的所有单元格 写入 1 。
- 如果对于尚未写入的方格,左侧方格和底部方格都写入了整数,则 2 平方和 将除以1,000,000,007 得到的余数写在该方格中。
- 重复步骤 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