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

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++, 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

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)~.

Comments

Please read the guidelines before commenting.

-45

minhdunghaizz commented on Oct. 20, 2021, 8:37 a.m.

include<bits/stdc++.h>

using namespace std; int n,k,dem=0; void giai (int x) { if(x<=k){ dem++;return; } int x1=(n-k)/2; int x2=x-x1; if(x1-x2==k||x2-x1==k){ giai(x1); giai(x2); } else { dem++; return; } } int main () { cin>>n>>k; giai(n); cout<<dem; return 0; }

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

4

This_is_a_name commented on Oct. 20, 2021, 8:47 a.m. ← edited →

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