Bài toán: Hàn Lập luyện cốt nhai

Nhạc đường chủ đứng trước mọi người lớn tiếng nói: "Mọi người nghe cho kỹ, đi theo con đường nhỏ trong rừng trúc phía trước là có thể đi tới luyện cốt nhai của Thất huyền môn. Đoạn đường đầu tiên là trúc lâm đoạn lộ, đi qua đó sẽ là giải đất bích nhai, và cuối cùng sẽ đến một cái sơn nhai". Ai có thể lên được đến đỉnh sơn nhai thì có thể tiến vào được Thất huyền môn. Để có thể trở thành ký danh đệ tử, Hàn Lập phải giải đáp được bài toán được khắc trên vách đá của chính ngọ như sau:

Cho một mảng gồm n phần tử, n là một số nguyên dương lớn hơn 2 và không quá 5 vạn. Mỗi phần tử của mảng có trị tuyệt đối không quá 1 tỉ. Biết rằng floor(n/2) phần tử cuối cùng của mảng là giống nhau còn ceil(n/2) phần tử đầu tiên là tùy ý. Bài toán yêu cầu tìm số k bất kì thỏa mãn tính chất sau: Mỗi tổng của k phần tử liên tiếp nhau đều phải là số nguyên dương. Nếu không tồn tại số k nào thỏa mãn thì in ra -1.
Cấu trúc của input như sau:
+ Dòng đầu tiên: số n
+ Dòng thứ 2: Chứa ceil(n/2) phần tử đầu tiên
+ Dòng thứ 3: Chứa một số duy nhất (Vì floor(n/2) phần tử cuối cùng của mảng đều giống nhau)
Và ouput: Là giá trị của số k cần tìm (nếu có nhiều giá trị của k, in ra k bất kỳ). Nếu không có số k nào thỏa mãn in ra -1.
Ví dụ 1:
3
2 -1
2
Ở đây từ input ta suy ra mảng a = [2,-1,2]. Và đáp án ở đây k=2.
Vì a[1]+a[2]>0(do 2+(-1)=1>0) ; a[2]+a[3]>0 (do (-1)+2=1>0).
Ví dụ 2:
5
2 2 -8
2
Ở đây từ input ta suy ra mảng a = [2,2,-8,2,2]
-> Đáp án ở đây là -1. Vì không có giá trị nào của k thỏa mãn
Ví dụ 3:
6
-2 -2 6
-1
Ở đây từ input ta suy ra mảng a=[-2,-2,6,-1,-1,-1]
Ở đây đáp án k=4. Vì a[1]+a[2]+a[3]+a[4]=(-2)+(-2)+6+(-1)=1>0 và a[2]+a[3]+a[4]+a[5]=2>0 và a[3]+a[4]+a[5]+a[6]=3>0

* Chú ý: ceil(x) - tức là cận trên của x - là số nguyên gần x nhất và lớn hơn hoặc bằng x.
            Ví dụ: ceil(5.5)=6; ceil(5)=5.
              floor(x) - tức là cận dưới của x - là số nguyên gần x nhất và nhỏ hơn hoặc bằng x.
           Ví dụ: floor(5.5)=5; floor(5)=5.

Bạn hãy cố gắng giúp Hàn Lập thực hiện được ước nguyện của mình nhé!

Nhận xét