SUBSUM
View as PDF
Submit solution
Points:
100.00
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho dãy ~A~ gồm ~N~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_N~. Một dãy con của ~A~ là một dãy khác rỗng thu được bằng cách chọn ra từ ~A~ một số phần tử và giữ nguyên thứ tự của chúng.
Với một dãy con ~A_i={a_{i1},𝑎_{i2},…,a_{ik}}, S=a_{i1} + a_{i2}+…+a_{ik}~ gọi là tổng của dãy con đó.
Cho trước hai số nguyên dương ~P~ và ~Q~, có bao nhiêu giá trị ~S~ khác nhau từ các tổng của các dãy con của ~A~, lớn hơn hoặc bằng ~P~ và bé hơn hoặc bằng ~Q~ ~(P ≤ S ≤ Q)~.
Dữ liệu vào gồm:
- Dòng đầu ghi ba số nguyên dương ~N, P, Q~ ~(1 ≤ N ≤ 100, 1 ≤ P < Q ≤ 100)~
- Dòng tiếp theo ghi ~N~ số nguyên dương của dãy ~A~, mỗi số cách nhau một dấu cách ~(0 < a_i ≤ 100, i = 1, 2, …, N)~.
Kết quả gồm một dòng ghi một số là số dãy con tìm được.
Ví dụ
INPUT
6 3 7
8 2 3 10 5 5
OUTPUT
3
Giải thích
Có 3 tổng có giá trị khác nhau: 3, 5, 7 (2 + 5).
Biết rằng:
- Có 30% số tests có ~N ≤ 20~.
- Có 60% số tests có ~N ≤ 40~.
Comments
iloveameliawatson