Bedao Grand Contest 13 - SHOPPING
View as PDF
Vừa mới lĩnh lương, Alob và Bice quyết định dành ra số tiền ~n~ đồng đi shopping hâm nóng tình cảm. Alob muốn dành toàn bộ số tiền của mình để mua búp bê, còn Bice sẽ dành toàn bộ số tiền của mình để mua lego.
Trong siêu thị có vô số loại lego và búp bê, loại lego thứ ~i~ có giá là ~i~ đồng và loại búp bê thứ ~i~ cũng có giá là ~i~ đồng. Hai bạn sẽ chia nhau ~n~ đồng tiền theo ý thích và đi mua sắm, mỗi người chỉ mua một loại đồ chơi duy nhất (có thể mua nhiều món đồ cùng loại) đến khi hết tiền sao cho số tiền mang đi không thừa không thiếu và mỗi bạn mua được ít nhất một món đồ chơi.
Chẳng hạn, nếu ~n=8~, một cách mua có thể là: Alob và Bice mỗi người được chia ~4~ đồng; Alob mua ~2~ con búp bê giá ~2~ đồng, còn Bice mua ~1~ lego giá ~4~ đồng. (Lưu ý Alob không thể mua ~1~ con búp bê giá ~3~ đồng (do không sử dụng hết tiền) hoặc một con ~3~ đồng một con ~1~ đồng (do chỉ được mua ~1~ loại đồ chơi)).
Hãy tính xem Alob và Bice có tổng bao nhiêu cách mua đồ.
Input
Một số nguyên duy nhất là số nguyên dương ~n~ là số tiền mà Alob và Bice có (~1 \leq n \leq 10^6~).
Output
Một số nguyên duy nhất là số cách mua đồ có thể của Alob và Bice.
Scoring
Subtask ~1~ (~40~ điểm): ~n \leq 500~.
Subtask ~2~ (~60~ điểm): Không có điều kiện gì thêm.
Sample Input 1
2
Sample Output 1
1
Sample Input 2
4
Sample Output 2
8
Notes
Trong test thứ nhất, chỉ có duy nhất ~1~ cách mua sắm là: Alob dùng ~1~ đồng mua búp bê giá ~1~ đồng, Bice dùng ~1~ đồng mua lego giá ~1~ đồng.
Trong test thứ hai, có tổng cộng ~8~ cách chia thỏa mãn là:
Alob mua ~1~ búp bê giá ~1~ đồng, Bice mua ~1~ lego giá ~3~ đồng.
Alob mua ~1~ búp bê giá ~1~ đồng, Bice mua ~3~ lego giá ~1~ đồng.
Alob mua ~1~ búp bê giá ~2~ đồng, Bice mua ~1~ lego giá ~2~ đồng.
Alob mua ~1~ búp bê giá ~2~ đồng, Bice mua ~2~ lego giá ~1~ đồng.
Alob mua ~2~ búp bê giá ~1~ đồng, Bice mua ~1~ lego giá ~2~ đồng.
Alob mua ~2~ búp bê giá ~1~ đồng, Bice mua ~2~ lego giá ~1~ đồng.
Alob mua ~3~ búp bê giá ~1~ đồng, Bice mua ~1~ lego giá ~1~ đồng.
Alob mua ~1~ búp bê giá ~3~ đồng, Bice mua ~1~ lego giá ~1~ đồng.
Comments
bai rat hay va y nghia
cho em hỏi về cách để chuẩn bị trước số lượng ước từ 1 tới n với ạ
cách của mình là dùng sàn nguyên tố để đếm ước