Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TREELINE - VOI 2011 Hàng cây

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/treeline


Một trang trại lớn có n cây cảnh với độ cao khác nhau từng đôi một. Các cây này được xếp theo một hàng dọc. Ông chủ trang trại là một 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 them một cây cảnh mới có chiều cao lớn hơn chiều cao tất cả các cây đã có. Ông muốn xếp cây cảnh mới vào 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, vị trí sau cây thứ hai, … , 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 giố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:

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 <= 10^5, h <= 10^6.

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ả:

  • Dòng thứ nhất ghi một số nguyên là số cách sắp 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 10^9.

Ví dụ:

Dữ liệu

Kết quả

2 2011

11 1

2

5


Ràng buộc: 50% số tests ứng với 50% số điểm của bài có 2 <= n <= 15


Được gửi lên bởi:VOJ Team
Ngày:2011-01-12
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2011

hide comments
2019-11-26 15:59:50
bài này catalan nha :D
đừng làm phức tạp hóa

Last edit: 2019-11-26 16:01:57
2019-07-13 13:10:02
DIO was here, but he can solve :((
2018-11-26 08:46:53
nhức đầu quá
2017-10-07 09:47:14
bài này phải dùng heap+ quy hoạch động các bạn nhé
2017-10-07 09:30:13
hello
2017-10-07 09:30:02
i am bang
2017-07-22 11:10:10
https://vietcodes.github.io/code/22

Last edit: 2017-08-06 10:51:33
2015-01-05 14:01:25 to_yeu_mao_hieu_dong


Last edit: 2015-01-05 15:51:56
2011-01-14 10:20:45 Sâu Lười
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 10^9.
2011-01-14 03:37:35 Thỏ con làm bánh
Các anh admin cho em hỏi là số ngày tối đa in ra theo mod 10^9 hay mod (10^9+7) thế ạ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.