Bài 3: Cắt dây (TS10 Nam Định 2025)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1400 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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:

  1. Mỗi lần, chọn đoạn dây dài nhất trong các đoạn hiện có.
  2. 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\) thì cắt thành hai đoạn có độ dài \(u\).
    • Nếu đoạn dây có độ dài lẻ là \(2u+1\) thì 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: 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?

Input

  • Dòng 1: Số nguyên \(n\) (\(2 \le n \le 10^{18}\)).
  • Dòng 2: Số nguyên \(k\) (\(1 \le k \le n-1\)).

Output

  • 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.

Example

Test 1

Input 
100
5
Output 
25 2
Note
  • Lần cắt 1: Chọn đoạn \(100\), cắt thành \(\{50, 50\}\).
  • Lần cắt 2: Chọn một đoạn \(50\), cắt thành \(\{25, 25, 50\}\).
  • Lần cắt 3: Chọn đoạn \(50\) còn lại, cắt thành \(\{25, 25, 25, 25\}\).
  • Lần cắt 4: Chọn một đoạn \(25\), cắt thành \(\{12, 13, 25, 25, 25\}\).
  • Lần cắt 5: Chọn một đoạn \(25\), cắt thành \(\{12, 13, 12, 13, 25, 25\}\).

Sau 5 lần cắt, đoạn dài nhất có độ dài là \(25\) và có \(2\) đoạn như vậy.

Scoring

  • Subtask \(1\) (\(75\%\) số điểm): \(n, k \le 10^4\).
  • Subtask \(2\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: