题目描述
由两个自然数组成的一对数称之为有序数对。有序是指数对的第一项与第二项是区别的,例如 (0,1),(1,0) 是不一样的数对。
我们对所有的有序数对进行排序,排序规则如下:
- 首先,计算每个数对的两数之和,和较小的数对靠前排列;
- 其次,如果两数之和一样大,则数对中第一项较小的数对靠前排列。
按照这个规则排序,前 6 项数对为
(0,0), (0,1), (1,0), (0,2), (1,1), (2,0)
给定一个整数 k,请求出第 k 个数对。
输入格式
输出格式
6
2 0
数据范围
- 30% 的数据,1≤k≤1,000
- 60% 的数据,1≤k≤1,000,000
- 100% 的数据,1≤k≤1,000,000,000