Lớp Bùa Chú
Đề bài
Mô tả
Trong lớp Bùa Chú của giáo sư Flitwick, các học sinh luyện tập một chuỗi phép thuật. Mỗi phép thuật có một chỉ số năng lượng phép thuật (có thể âm, dương hoặc bằng ). Một phép thuật có năng lượng âm nghĩa là phép đó hút năng lượng từ môi trường xung quanh.
Giáo sư Flitwick muốn tìm số lượng đoạn con liên tiếp của chuỗi phép thuật sao cho tổng năng lượng phép thuật trong đoạn đó bằng đúng .
Một đoạn con liên tiếp là một dãy các phần tử liền kề với .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và — số lượng phép thuật và tổng năng lượng cần tìm.
- Dòng thứ hai chứa số nguyên — chỉ số năng lượng của mỗi phép thuật.
Dữ liệu ra
- In ra một số nguyên duy nhất — số lượng đoạn con liên tiếp có tổng bằng .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 5 1 2 3 4 5 |
2 | Có 2 đoạn con có tổng bằng : đoạn (tổng ) và đoạn (tổng ). |
| 7 3 3 -1 2 -1 3 -1 2 |
6 | Có 6 đoạn con có tổng bằng : (vị trí 1), (vị trí 1-4), (vị trí 2-5), (vị trí 3-6), (vị trí 4-7), và (vị trí 5). |
Ghi chú
- Kết quả có thể rất lớn, cần dùng kiểu dữ liệu 64-bit.
https://oj.chuyentin.pro/problem/charms
Bình luận