1900
View as PDF
Submit solution
Points:
1300 (partial)
Time limit:
1.0s
Python 3
2.5s
Memory limit:
256M
Python 3
512M
Input:
1900.INP
Output:
1900.OUT
Author:
Problem type
Allowed languages
C++, Pascal, Python
Statement
Vào năm 1900, Nguyễn Hùng Nam Anh - Một nhà toán học trẻ tuổi đầy tài năng, đã công bố một định lý mới khiến giới học thuật phải kinh ngạc. Anh phát hiện ra rằng:
"Nếu có thể chia một dãy số ra thành hai đoạn liên tiếp và sắp xếp từng đoạn sao cho cả dãy hợp lại trở thành tăng dần thì ta đã tìm thấy một điểm tách k hoàn hảo".
Vấn đề thú vị này đã được Nam Anh đặt ra cho các nhà toán học cùng thời:
Với một dãy số gồm n phần tử, hãy xác định có bao nhiêu cách chọn chỉ số k sao cho nếu:
- 1 \leq k < n;
- sắp xếp dãy số đó từ 1 đến k;
- sắp xếp dãy số đó từ k + 1 đến n;
thì toàn bộ dãy hợp lại sẽ trở thành dãy tăng dần.
sau bao nhiêu năm, bài toán vẫn ở ngay đó. Bạn giúp Nam Anh nhé?
Input, Output và Subtasks
Input: (1900.INP)
- Dòng đầu tiên chứa số nguyên n.
- Dòng thứ hai chứa n số nguyên A_{i}.
Output: (1900.OUT)
- In ra một số nguyên duy nhất là số lượng chỉ số k thỏa mãn yêu cầu.
Subtasks
- Subtask chung: |A_{i}| \leq 10^{9}
- Subtask 1 (20%): 1 \leq n \leq 10^{2};
- Subtask 2 (40%): 1 \leq n \leq 2 * 10^{3};
- Subtask 3 (40%): 1 \leq n \leq 10^{6};
Sample #1
Input (1900.INP)
5
4 2 7 15 8
Output (1900.OUT)
2
Notes
- với dãy {4; 2; 7; 15; 8}, ta có 2 chỉ số hợp lệ:
- k = 2, ta có hai đoạn:
- {4; 2} và {7; 15; 8};
- sắp xếp mỗi đoạn:
- {2; 4} và {7; 8; 15};
- ghép hai đoạn lại với nhau:
- {2; 4; 7; 8; 15} (thỏa mãn điều kiện).
- k = 3, ta có hai đoạn:
- {4; 2; 7} và {15; 8};
- sắp xếp mỗi đoạn:
- {2; 4; 7} và {8; 15};
- ghép hai đoạn lại với nhau:
- {2; 4; 7; 8; 15} (thỏa mãn điều kiện).
- vậy với dãy đã cho, chúng ta có 2 kết quả hợp lệ.
Sample #2
Input (1900.INP)
6
6 5 4 3 2 1
Output (1900.OUT)
0
Notes
- với dãy {6; 5; 4; 3; 2; 1}, ta có 0 chỉ số hợp lệ!
- vậy với dãy đã cho, chúng ta có 0 kết quả hợp lệ.
Comments