Bedao Grand Contest 13 - SHOPPING

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.



  • -1
    modwwe  commented on Sept. 13, 2023, 1:05 a.m.

    bai rat hay va y nghia


  • 0
    andinhvinhthanh  commented on June 28, 2023, 1:29 p.m.

    cho em hỏi về cách để chuẩn bị trước số lượng ước từ 1 tới n với ạ


    • 1
      phenomenal  commented on June 28, 2023, 2:21 p.m.

      cách của mình là dùng sàn nguyên tố để đếm ước