OKHOA2 - Ổ khóa 2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Có vẻ như ổ khóa lần trước không làm khó được An, nên lần này người bạn của cậu ta quyết định gửi sang một món quà được giấu trong chiếc hộp lớn hơn (và tất nhiên ổ khóa của nó cũng nhiều nút hơn). Cách mở khóa vấn giống lần trước (xem tại đây)

Nhiệm vụ của bạn vẫn là cho biết trong trường hợp xấu nhất thì An phải mất bao nhiêu lần bấm nút để có thể mở được ổ khóa.

Dữ liệu nhập: Một số nguyên dương N duy nhất là số nút trên hộp quà (1  ≤ N ≤ 109)

Dữ liệu xuất: Một số nguyên dương duy nhất là số lần bấm nút trong trường hợp xấu nhất. Vì kết quả có thể rất lớn, nên bạn chỉ cần xuất ra phần dư của kết quả sau khi chia cho 109+7

Ví dụ

  • input
    2
    output
    3
  • input
    3
    output
    7

Trong bộ test thứ hai: gọi thứ tự bấm nút đúng là (3, 2, 1). An có thể bấm lần lượt 2 nút 1, 2 và no sẽ sai (đã bấn 2 lần: 1 2) lúc này An biết chắc rằng nút đầu tiên theo thứ tự là 3. Cậu ta nhấn nút số 3, còn lại 2 nút, cậu ta có thể bấm nút số 1 và sai (đã bấm 4 lần) Như vậy cậu ta biết rằng nút đầu tiên theo thứ tự là 3, nút tiếp theo là 2, còn lại nút cuối cùng chính là 1, bây giờ cậu ta chỉ cần bấm đúng thứ tự (3, 2 ,1) là mở được ở khóa, như vậy trường hợp xấu nhất là 7 lần bấm nút, phần dư sau khi chia 7 cho 109+7 cũng là 7 nên kết quả xuất ra là 7

Back to Top