Cho hai số nguyên K và S. Đếm số bộ ba có thứ tự (x,y,z) sao cho mỗi số nằm trong đoạn từ 0 đến K và tổng của ba số bằng S.
Input
Một dòng chứa hai số nguyên K và S.
Output
In số bộ ba (x,y,z) thỏa 0≤x,y,z≤K và x+y+z=S.
Constraints
2≤K≤2500.
0≤S≤3K.
Scoring
Subtask 1 (50% số điểm): K≤100.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
2 2
Output
6
Giải thích: Sáu bộ ba hợp lệ là (0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0) và (2,0,0). Vì thứ tự được phân biệt nên kết quả là 6.
Lời giải tóm tắt
Ý tưởng: Duyệt mọi x và y trong [0,K], rồi đặt z = S-x-y. Tăng đáp án khi z cũng thuộc [0,K].
Chứng minh tính đúng đắn: Mỗi bộ ba hợp lệ có đúng một cặp đầu (x,y) và khi cặp đó được xét, giá trị z bị xác định duy nhất. Ngược lại, mỗi lần thuật toán tăng đáp án tạo ra một bộ ba đúng cận và đúng tổng.
Độ phức tạp:O(K²) thời gian và O(1) bộ nhớ.
Lỗi cài đặt thường gặp: Đếm bộ ba không xét thứ tự.
Lỗi cài đặt thường gặp: Dùng cận z < K và bỏ các nghiệm có z = K.