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

View as PDF

Submit solution


Points: 0.07 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO US-Open 2008 - Bảng Bạc
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.



  • -25
    minhdunghaizz   commented on Oct. 20, 2021, 3:37 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 6
      This_is_a_name   commented on Oct. 20, 2021, 3:47 p.m. edited

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