0.Số gần nhị phân

Submit solution
Points: 3 (partial)
Time limit: 0.347s
Memory limit: 20M
Author:
themiscscvn
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một số nguyên được gọi là "gần nhị phân" nếu hệ thập phân của nó chỉ chứa số 0 và 1. Ví dụ: 0, 1, 10, 11, 101, 11011 là số "gần nhị phân"

Bạn được cho số nguyên dương n. Hãy tìm số lượng số "gần nhị phân" nhỏ nhất sao cho tổng các này bằng n.

Input

Số n (n ≤ 10^6).

Output

Số lượng số "gần nhị phân" tìm được.

Example

Input

9

Output

9

Input

32

Output

3

Giải thích test 1: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9

Giải thích test 2: 11 + 11 + 10 = 32

Comments


  • 0
    SonTrau_CNTTVA2_K63  commented on Jan. 7, 2023, 11:56 a.m.

    Bài này làm khá tốn não nhưng em ăn may 4 lần submit là AC ạ :3


  • 2
    DuyAnhhh  commented on Aug. 21, 2020, 4:11 p.m.

    Đề bài hay thực sự,cảm ơn anh tác giả ^^


    • 1
      Phuc_CNTT3_K60  commented on Aug. 21, 2020, 4:40 p.m.

      chả biết anh tác giả có lường trước được thế này không =))


      • 1
        TICHPX  commented on Aug. 22, 2020, 8:37 a.m.

        manhdt17 đâu rồi ra mặt cho các em ấy cảm ơn


  • 2
    cotyey  commented on Feb. 28, 2018, 11:05 a.m.

    find max ....


  • 1
    socoladaica  commented on Nov. 22, 2017, 10:52 a.m.

    quất hẳn mũ 30 cho các bạn sợ


  • 1
    TICHPX  commented on Nov. 21, 2017, 10:00 a.m.

    Cho số n có \(10^6\) chữ số đi


    • 4
      Giang_CNTT3_K60  commented on Aug. 21, 2020, 4:27 a.m.

      thêm bài lại là nữa thầy ạ :)


      • 1
        TICHPX  commented on Aug. 21, 2020, 4:32 a.m.

        Chả có nhẽ


    • 1
      themiscscvn  commented on Nov. 21, 2017, 11:51 a.m.

      Sao thầy có thể làm như thế @@.