@Aki Tsuki; @Luân Đào; @Nguyễn Nhật Minh
Sau bao ngày, nay trở lại cũng đã gặp những "cao thủ lập trình", nay tại hạ xin mạn phép nhờ các vị giúp đỡ
Hàng cây
Một trang trại lớn có n cây cảnh với độ cao khác nhau từng đôi. Các cây này được xếp theo một hàng dọc. Ông chủ trang trại là người có đầu óc thẩm mỹ nên hàng cây được bố trí có tính chất không đơn điệu sau đây: “Đi từ đầu hàng đến cuối hàng không có 3 cây (không nhất thiết phải liên tiếp) có chiều cao giảm dần”.
Một hôm ông chủ mua thêm một cây cảnh mới có chiều cao lớn hơn chiều cao của tất cả các cây đã có. Ông ta muốn xếp cây cảnh mới vào một trong n +1 vị trí có thể của hàng cây đang có (vào vị trí đầu hàng, vị trí sau cây thứ nhất của hàng, vị trí sau cây thứ hai của hàng, ..., vị trí sau cây thứ n của hàng) sao cho hàng cây thu được vẫn thỏa mãn yêu cầu về tính không đơn điệu nêu trên.
Yêu cầu:
• Hãy cho biết có bao nhiêu cách xếp cây cảnh cao nhất mới mua vào hàng cây sao cho vẫn đảm bảo điều kiện về tính không đơn điệu.
• Giả sử mỗi ngày ông chủ muốn xếp n+1 cây đã có thành hàng cây đảm bảo yêu cầu về tính không đơn điệu và hai hàng cây của hai ngày khác nhau là không trùng nhau, hãy giúp ông chủ tính xem việc đó có thể diễn ra nhiều nhất là bao nhiêu ngày.
Dữ liệu: Vào từ file văn bản TREELINE.INP
• Dòng thứ nhất chứa hai số nguyên dương n và h tương ứng là số lượng cây và chiều cao của cây cao nhất. Biết rằng n ≤ 105, h ≤ 106.
• Dòng thứ hai chứa n số nguyên dương (mỗi số đều nhỏ hơn h) tương ứng là dãy chiều cao của n cây được xếp ban đầu.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản TREELINE.OUT
• Dòng thứ nhất ghi một số nguyên là số cách xếp cây cao nhất vào hàng cây.
• Dòng thứ hai ghi một số nguyên là phần dư trong phép chia số ngày lớn nhất tìm được cho 109.
