Một số gọi là Hill Number nếu khi đi từ trái qua phải của số, giá trị các chữ số sẽ không giảm, đến một lúc nào đó các giá trị sẽ không tăng.
Ví dụ:
123321 là Hill number và 101 không phải là hill number.
Yêu cầu đếm: số lượng số nhỏ hơn số N cho trước mà là Hill Number, số N có thể lên tới 70 chữ số.
Bài toán có nhiều test case, kết quả không quá long long.
Link đề: http://codeforces.com/gym/100827
Làm thế nào đề giải quyết được bài này, cảm ơn mọi người.
Gọi duyet(int i, int dig, bool inc, bool ok, bool greater0) là xét đến chữ số thứ i, cấu hình xây dựng được từ 1..i-1 có nghĩa:
dig: chữ số chọn thứ i - 1
inc = true: đang ko giảm, = false ngược lại
ok = true: đã nhỏ hơn n
greater0: đã lớn hơn 0
Đpt là O(70 * 10 *10* 2 *2 * 2 * số truy vấn). Mình đã thử trên CF và đã AC
Cảm ơn bạn rất nhiều :)
Cho mình hỏi tại sao phải có greater0 ?
Đề chuẩn của nó là tìm từ 1..n có bao nhiêu số, chứ ko phải 0..n - 1. Trong cái file đề trên CF có đó bạn.
Còn vì sao lớn hơn 0 thì có trường hợp mình chọn tất cả đều là 0000..00 -> không thỏa mãn
