Dãy Chia Hết
Xem PDFHôm nay và , \(2\) nam thần của làng K-pop đang đi chơi với nhau. May mắn thay họ gặp 1 cô em gái xinh đẹp tên là Jennie. Jennie vốn đã hâm mộ \(2\) người từ lâu nên đã đố họ \(1\) bài toán. Ai giải ra trươc là sẽ là người được đi chơi, hẹn hò với Jennie.
Bài toán là cho 1 dãy số nguyên dương \(A_1, A_2,…,A_n (n≤10^6, A_i≤10^9)\). 1 dãy con liên tiếp không rỗng của \(A\) được xem là dãy “ngu ngốc“ khi tổng phần tử của dãy con đó chia hết cho số nguyên dương \(k (1≤ k ≤10^6)\). Jennie đố và hãy tìm cách chia dãy \(A\) thành \(2\) dãy con “ngu ngốc” không giao nhau sao cho tổng độ dài \(2\) dãy là lớn nhất. rất muốn được hẹn hò với Jennie nhưng vì mải ngắm nhìn nhan sắc tuyệt trần của cô nên anh không có tâm trí nào mà giải toán nữa. Bạn hãy giúp nhé !
Yêu cầu:
- Hãy tìm tổng độ dài lớn nhất.
Input:
- Dòng đầu tiền lần lượt là \(n\) và \(k\), dòng thứ \(2\) là các số \(A_i\).
Output:
- \(1\) số duy nhất là kết quả, nếu không có cách chia thì in ra \(0\).
Scoring:
-
Subtask \(1\) (\(50\%\) số điểm): có \(n≤10^4\).
-
Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.
Example:
Test 1
Input
3 2
1 2 3Output
0Note
không có cách chia.
Test 1
Input
4 2
1 2 3 4Output
4Note
chia 2 dãy \([1,2,3]\) và \([4]\).
Bình luận
ai chỉ mình được 100% bài này được không, tối đa có được 81% à
e nghĩ phải là i - modulo[partial_sum[i] % k] + 1 mới đúng chứ nhỉ
e bỏ + 1 đi thì ac
sao cai output cua e lai sai dung 1 don vi nhi
.
ad có tutorial không ạ, tại em cứ bị vướng ở cái vụ khi cái prefix sum % k == 0 thì xử lí cứ lỗi sao ý
why do i lost on 13 test ?
.
Anh bin9638 và algorit viết editorial cho 3 bài cuối của div2 Champion contest với ạ. Tuy contest diễn ra đã lâu nhưng em vẫn chưa có ý tưởng tối ưu nào cho các bài đó. Em xin cảm ơn!
cho em xin 1 test nhỏ để thử với ạ :(( mấy test em sinh em thấy kết quả nó đúng nhưng nộp lại sai 🙁