Vạn Dân Đường
Hôm nay, Keqing phụ giúp Xiangling bán bánh mì ở Vạn Dân Đường. Hằng ngày có rất nhiều vị khách tới đây mua bánh mì của hai người. Vị khách thứ i trong ngày sẽ mua i cái bánh. Hôm nay, Keqing và Xiangling sẽ cùng nhau bán n bánh mì đến khi không còn đủ bánh cho khách mua nữa và đóng cửa kết thúc một ngày làm việc. Những chiếc bánh còn thừa trong ngày sẽ được bán tiếp vào các ngày tiếp theo đến khi hết bánh thì thôi.
Để tăng năng suất, Keqing và Xiangling sẽ thay phiên nhau bán bánh. Keqing sẽ bán bánh cho các vị khách lẻ, còn Xiangling sẽ bán bánh cho các vị khách chẵn. Hỏi sau một thời gian bán bánh, Keqing sẽ bán được bao nhiêu cái bánh
Đầu vào
1 số tự nhiên \(n\) là số lượng bánh mì
Đầu ra
Lượng bánh Keqing bán
Giới hạn
50%: \(1 \le n \le 10^{12}\)
50%: \(1 \le n \le 10^{18}\) (bao lâu mới bán được 1 tỷ tỷ cái bánh mì)
Ví dụ 1
Đầu vào
12
Đầu ra
6
Giải thích
Nhật ký bán bánh mì của Keqing:
Ngày 1: Keqing bán bánh mì cho vị khách thứ 1 và 3
Xiangling bán bánh mì cho vị khách thứ 2 và 4
Tổng kết: Số bánh Keqing bán: 4
Số bánh Xiangling bán: 6
Số bánh còn lại: 2
Ngày 2: Keqing bán bánh mì cho vị khách thứ 1
Xiangling không bán được bánh mì cho ai cả
Tổng kết: Số bánh Keqing bán: 1
Số bánh Xiangling bán: 0
Số bánh còn lại: 1
Ngày 3: Keqing bán bánh mì cho vị khách thứ 1
Xiangling không bán được bánh mì cho ai cả
Tổng kết: Số bánh Keqing bán: 1
Số bánh Xiangling bán: 0
Số bánh còn lại: 0
Hết bánh, sau 3 ngày Keqing bán được tổng cộng 6 cái bánh và Xiangling cũng bán được 6 cái bánh
Comments
Ý tưởng: Sử dụng tìm kiếm nhị phân
Mỗi ngày có 1 lượng khách mua bánh từ 1 -> k => Tổng số bánh mỗi ngày bán là : 1+2+...+k = k(k+1)/2;
Ở mỗi ngày, cần phải tìm số k sao cho 1+2+...+k <= số bánh còn lại;
Tổng số bánh của Kelquing đã bán trong 1 ngày là bình phương của số các số lẻ trong dãy 1 -> k với k tìm được ở mỗi ngày (số các số lẻ trong dãy = (k+1)/2 )
tôi nhận ra là mình cần ôn lại môn toán:)))
Đầu tiên cần phải tìm số K sao cho tổng cấp cộng Sk <= n
đỉnk quá