[C10_ND_25] Cắt dây
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python
An có một sợi dây có độ dài ~n~. An thực hiện ~k~ lần cắt dây như sau:
- Mỗi lần, chọn đoạn dây dài nhất trong các đoạn hiện có.
- Cắt thành ~2~ đoạn dây theo cách sau:
- Nếu đoạn dây có độ dài chẵn là ~2u~ cắt thành hai đoạn có độ dài ~u~.
- Nếu đoạn dây có độ dài lẻ là ~2u + 1~ cắt thành hai đoạn có độ dài là ~u~ và ~u + 1~.
Sau ~k~ lần, An có tổng cộng ~k + 1~ đoạn dây.
Yêu cầu
Em hãy cho biết, sau ~k~ lần cắt độ dài đoạn dây dài nhất và số lượng đoạn dài nhất An có là bao nhiêu?
Dữ liệu đầu vào
Gồm hai dòng:
- Dòng thứ nhất: Số nguyên ~n~ ~(2 \le n \le 10^{18})~.
- Dòng thứ hai: Số nguyên ~k~ ~(1 \le k \le n - 1)~.
Dữ liệu đầu ra
Gồm hai số là độ dài đoạn dây dài nhất và số lượng đoạn dài nhất mà An có sau ~k~ lần cắt.
Ràng buộc dữ liệu
- Có 75% số test tương ứng với 75% số điểm có ~1 \le n, k \le 10^4~.
- Có 25% số test tương ứng với 25% số điểm không có ràng buộc gì thêm.
Ví dụ
Ví dụ 1
INPUT
100
5
OUTPUT
25 2
Giải thích:
- Lần cắt ~1~ có ~2~ đoạn: ~50~, ~50~
- Lần cắt ~2~ có ~3~ đoạn: ~25~, ~25~, ~50~
- Lần cắt ~3~ có ~4~ đoạn: ~25~, ~25~, ~25~, ~25~
- Lần cắt ~4~ có ~5~ đoạn: ~12~, ~13~, ~25~, ~25~, ~25~
- Lần cắt ~5~ có ~6~ đoạn: ~12~, ~13~, ~12~, ~13~, ~25~, ~25~
Bình luận
suytj