Những con đường quanh nông trang

Xem dạng PDF

Gửi bài giải


Điểm: 0,07 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
USACO US-Open 2008 - Bảng Bạc
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Các con bò của nông dân John có sở thích là hay đi khám phá những vùng xung quanh nông trang. Ban đầu, tất cả ~N~ ~(1 \le~ ~N~ ~\le~ ~10^9~) con bò tập trung thành 1 nhóm và cùng bắt đầu chuyến đi trên 1 con đường. Cho tới khi gặp một ngã ba đường thì chúng đôi khi chọn cách chia làm 2 nhóm nhỏ hơn (mỗi nhóm ít nhất 1 bò) và mỗi nhóm lại tiếp tục hành trình trên con đường của nhóm chúng. Khi một trong những nhóm này gặp 1 ngã ba khác thì nhóm này lại có thể tách ra tiếp, và cứ như vậy.

Các con bò đã hình thành nên 1 quy tắc về việc chia nhóm như sau: nếu chúng có thể chia thành 2 nhóm mà chênh lệch số bò của 2 nhóm là đúng bằng ~K~ ~(1 \le K \le 1000)~ thì tại ngã ba đó chúng sẽ chia làm 2; nếu không thì chúng sẽ dừng cuộc hành trình và đứng ở đó nhấm nháp cỏ non.

Giả sử rằng luôn có những ngã ba mới trên các con đường, hãy tính xem cuối cùng có bao nhiêu nhóm bò tất cả.

Input

2 số nguyên cách nhau bởi dấu cách: ~N~ và ~K~.

Output

Một số nguyên cho biết số lượng nhóm bò sau cùng.

Sample Input

6 2

Sample Output

3

Note

Cuối cùng có ~3~ nhóm bò ~(1~ nhóm có ~2~ bò, ~1~ nhóm có ~1~ và ~1~ nhóm có ~3)~.

  6
 / \
2   4
   / \
  1   3

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -42
    minhdunghaizz  đã bình luận lúc 20, Tháng 10, 2021, 8:37

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 5
      This_is_a_name  đã bình luận lúc 20, Tháng 10, 2021, 8:47 chỉnh sửa

      có đăng thì tag spoiler bạn ơi :). bạn làm thế mù mắt người đọc :)