#229. ROBOT - Di chuyển Robot

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho một bảng ô vuông kích thước vô hạn. Các dòng được đánh số từ 1 theo thứ tự trừ trên xuống dưới, các cột được đánh số từ 1 theo thứ tự từ trái qua phải. Ô vuông nằm trên giao của dòng thứ i và cột thứ j được gọi là ô (i;j) , và tại ô vuông đó có ghi số nguyên i×j .

Một con robot xuất phát tai ô (1;1) , trong mỗi bước, con robot có thể đi đến một trong bốn ô kề cạnh với ô robot đang đứng. Robot không được phép đi ra ngoài bảng ô vuông.

Yêu cầu: Hãy cho biết số bước ít nhất để robot đi đến một ô vuông bất kỳ được ghi số nguyên n ?

Dữ liệu vào:

  • Gồm một số nguyên n\ (1≤n≤10^{12}) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất số bước ít nhất cần tìm.

Ví dụ:

Dữ liệu vào:
6
Dữ liệu ra:
3
Dữ liệu vào:
12
Dữ liệu ra:
5
Dữ liệu vào:
11
Dữ liệu ra:
10

Chú ý: 50\% số điểm tương ứng n≤10^6 .