Bình phương (THTB TQ 2017)

Xem PDF

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

Bé Cam hôm nay đến lớp học Toán và được cô dạy về bình phương của một số. Cô cho Cam một bảng \(A\) kích thước \(10^{6} \times 10^{6}\) phần tử. Các dòng được đánh số từ \(1\) đến \(10^{6}\) theo chiều từ dưới lên trên, các cột được đánh số từ \(1\) đến \(10^{6}\) theo chiều từ trái sang phải. Phần tử nằm ở hàng \(i\), cột \(j\) được kí hiệu là \(A_{ij}\) được tính bằng công thức \(A_{ij} = i^{2} + j^{2}\).

Cô giáo tạo ra dãy \(B\) đánh số từ \(1\) đến \(10^{12}\) gồm toàn bộ các phần tử của bảng \(A\) rồi sắp xếp theo thứ tự không giảm. Sau đó cô hỏi Cam xem số thứ \(K\) trong dãy \(B\) có giá trị là bao nhiêu? Lúc đầu cô đưa số \(K\) nhỏ nên Cam còn đếm được. Khi số \(K\) lớn lên, Cam không còn tính nhẩm trong đầu được nữa, Cam muốn các bạn thi Tin học trẻ hôm nay giúp bé tìm đáp án cho câu hỏi của cô giáo nhé. Hình bên là ảnh Cam chụp góc trái dưới cùng bảng \(A\).

Sau khi chuyển các phần tử của bảng \(A\) vào dãy \(B\) và sắp theo thứ tự không giảm thì Cam có những phần tử đầu tiên của dãy \(B\)\(\{2, 5, 5, 8, 10, 10, 13, 13, 17, 17, 18, \ldots \}\) Khi cô hỏi \(K=5\) thì Cam đã ngay lập tức đưa ra được đáp án là \(10\). Các bạn hãy giúp bé với những số \(K\) lớn hơn nhé.

Input

  • Một dòng duy nhất chứa một số nguyên dương \(K\) \((1 \leq K \leq 10^{12})\).

Output

  • In ra một số nguyên là số thứ \(K\) trong dãy \(B\).

Scoring

  • Subtask \(1\) (\(60\%\) số điểm): \(1 \le K \le 10^5\).
  • Subtask \(2\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

Test 1

Input
5
Output
10

Bình luận