Xếp dãy bàn

Xem PDF

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

nguyenminhhai021009 là vị vua của vương quốc ABC.Hôm nay ông cho các binh lính của mình luyện tập để chuẩn bị cho trận chiến với quân của vua siêu chép code là Nguyen_Le_Huy_Khanh và vua siêu gáy to là imbigbrain bằng cách cho binh lính tham gia cuộc thi do mình tổ chức, cuộc thi mang tên CHÉP CODE (CCC) . Có \(n\) binh lính tham gia cuộc thi lần này, người thứ \(i\) đánh số báo danh là \(i\). Biết người thứ \(i\) chỉ muốn ngồi với người thứ \(i^2\). Hãy tính số dãy bàn mà ông vua nguyenminhhai021009 cần chuẩn bị ít nhất. Vì quá mệt mỏi vì việc xây dựng đất nước xong nên nguyenminhhai021009 đi ngủ rồi. Bạn hãy giúp vua nguyenminhhai021009 nhé.

Input

  • Duy nhất 1 số \(n\)

Output

  • Duy nhất 1 số là kết quả bài toán

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n\le 10^{18}\)
  • Subtask \(2\) (\(60\%\) số điểm): \(n\le 10^{255}\)

Example

Test 1

Input
10
Output
8
Note

Giải thích: Có 8 dãy bàn cần chuẩn bị:
\((1)\)
\((2, 4)\)
\((3, 9)\)
\((5)\)
\((6)\)
\((7)\)
\((8)\)
\((10)\)

Test 2

Input
100
Output
91

Bình luận


  • 3
    PhanHuyKhang    3:30 p.m. 22 Tháng 1, 2022

    ủa test 2 có phải 2, 4, 16 chung ko


    • 1
      huyhau6a2    5:32 p.m. 21 Tháng 1, 2022

      ai ac bài này qua bài đèn cầy đi, tương tự thôi

      1 phản hồi

      • 2
        nguyenminhhai021009    9:06 a.m. 21 Tháng 1, 2022 đã chỉnh sửa

        Update: Bộ test đã được anh stack_queue_4977 sửa rồi mọi người vào làm bình thường nha.


        • 3
          huyhau6a2    7:59 a.m. 18 Tháng 1, 2022 đã chỉnh sửa

          xin lỗi mọi người nha, minh tạo test nhầm cho bài đèn cầy rồi up lại, lát mình sẽ nhờ bạn sửa test lại nha, đừng submit kẻo bị wa nha, khi nào fix xong mình sẽ báo