首页 > ACM题库 > HDU-杭电 > hdu 4692 Great Sequence待解决[解题报告]C++
2015
09-17

hdu 4692 Great Sequence待解决[解题报告]C++

Great Sequence

问题描述 :

A great sequence S is a sequence contains N decimal integers, i.e. S = (x[1], x[2], …, x[N]). S should also satisfy following rules:
a[i] ≤ x[i] ≤ b[i]
ds[i] c[i] ds[i+1], where ds[i] is the digit sum of x[i] and c[i] is one of the following relational operators: "=", "<", "<=", ">", ">=" and "!=".
Obviously, there are a lot of great sequences. You are asked to find the K-th least great sequence in lexicographic order.

输入:

There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers 1 ≤ N ≤ 100, 1 ≤ K ≤ 1016, as described above.
In the next N-1 lines, each line contains three elements, a[i], b[i] and c[i], where a[i] and b[i] are integers (1 ≤ a[i] ≤ b[i] ≤ 1018) while c[i] is one of the following strings: "=", "<", "<=", ">", ">=" and "!=".
The last line of each test cases contains only two integers, a[N] and b[N] (1 ≤ a[N] ≤ b[N] ≤ 1018).

输出:

There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers 1 ≤ N ≤ 100, 1 ≤ K ≤ 1016, as described above.
In the next N-1 lines, each line contains three elements, a[i], b[i] and c[i], where a[i] and b[i] are integers (1 ≤ a[i] ≤ b[i] ≤ 1018) while c[i] is one of the following strings: "=", "<", "<=", ">", ">=" and "!=".
The last line of each test cases contains only two integers, a[N] and b[N] (1 ≤ a[N] ≤ b[N] ≤ 1018).

样例输入:

3 15
9 10 <=
99 100 =
1 300
3 20
9 10 <=
99 100 =
1 300

样例输出:

10 100 100
OUT OF RANGE