Đếm số truy vấn có tổng đoạn là số chẵn
Thay vì in ra từng tổng, có bài chỉ cần biết bao nhiêu truy vấn cho tổng chẵn. Đây là
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Thay vì in ra từng tổng, có bài chỉ cần biết bao nhiêu truy vấn cho tổng chẵn. Đây là dạng rút gọn của bài cộng dồn tiền tố: vẫn dựng mảng pref, nhưng mỗi truy vấn chỉ cần kiểm tra tính chẵn lẻ của pref[r] - pref[l - 1] rồi tăng một bộ đếm.
Yêu cầu
Cho mảng a gồm n số nguyên đánh số từ 1 đến n và q câu hỏi dạng (l, r). Hãy đếm xem có bao nhiêu câu hỏi mà tổng a[l] + a[l+1] + ... + a[r] là số chẵn. Số 0 được coi là số chẵn. Cả hai đầu l và r đều được tính vào tổng.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. In đúng một số nguyên trên một dòng duy nhất.
Input
- Dòng thứ nhất: số nguyên n là số phần tử (1 <= n <= 20).
- Dòng thứ hai: n số nguyên a[1] đến a[n], cách nhau bởi dấu cách (|a[i]| <= 10000).
- Dòng thứ ba: số nguyên q là số câu hỏi (1 <= q <= 10).
- q dòng tiếp theo: mỗi dòng hai số nguyên l rồi r, cách nhau bởi dấu cách
(1 <= l <= r <= n).
Output
- Một số nguyên duy nhất trên một dòng: số câu hỏi có tổng đoạn là số chẵn.
Ràng buộc
- 1 <= n <= 20, 1 <= q <= 10, |a[i]| <= 10000.
- Số âm chẵn vẫn được tính là số chẵn, ví dụ -4 là số chẵn.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
3
2 1 3
3
1 1
1 2
1 3
Output
2
Ví dụ 2
Input
4
1 2 3 4
3
1 1
1 2
2 4
Output
0
Giải thích
Với dữ liệu vào:
Ba tổng lần lượt là 2, 3 và 6, trong đó 2 và 6 là số chẵn, nên kết quả là:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
