Dominative Divide

Xem dạng PDF

Gửi bài giải

Điểm: 5,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Một dãy số x1, x2, ..., xm được gọi là dominative nếu tồn tại một giá trị k xuất hiện nhiều hơn m/2 lần. Ví dụ:

Dãy [3,2,2] là dominative vì giá trị xuất hiện 2 lần, lớn hơn 3/2

Dãy [1,2,3,2] không phải dominative vì không có giá trị nào xuất hiện nhiều hơn 4/2 = 2

Yêu cầu: Cho dãy a1, a2, ..., an, bạn cần đếm số cách chia dãy này thành các đoạn con liên tiếp sao cho mỗi đoạn con đều không dominative.


Đầu vào:

Dòng đầu tiên chứa số nguyên n (1 <= n <= 3000)

Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 <= ai <= 10^9)

Đầu ra:

In ra số cách chia thỏa mãn chia lấy dư cho 10^9 + 7


Input:
4  
3 6 6 9
Output:
2

Ở test này, có 2 cách chia là [3,6,6,9] hoặc [3,6],[6,9]

Input:
6  
1 2 1 2 1 2
Output:
4

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.