Submit solution
Points:
1400 (partial)
Time limit:
2.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem types
Allowed languages
C, C++, Pascal, pypy3, Python, scratch
n ô có giá trị 1,2,3,4,\ldots n. Anh ấy có thể sắp xếp các ô thành x hàng và y cột (y=\frac{n}{x} và nếu n không chia hết cho x thì y+1) và sắp xếp các ô từ trái qua phải và khi đi đến hàng thứ x thì xuống và bắt đầu xếp các số tiếp theo thứ tự tăng dần:
Ví dụ với n = 6:
Người chơi sẽ bắt đầu từ ô 1 sẽ chiến thắng khi đến ô n, người chơi có thể di chuyển như sau:
- Đi sang ô có cạnh chung với ô đang đứng.
- Không được đi sang ô có giá trị là số nguyên tố.
Yêu cầu: Tìm x nhỏ nhất sao cho người chơi có thể dành chiến thắng.
Input, Output and Scoring
Input (bàn phím
)
- Gồm một dòng duy nhất chứa số nguyên dương n (n\le 10^{18}).
- Dữ liệu luôn đảm bảo có đường đi hợp lệ.
Output (màn hình
)
- In ra số nguyên x nhỏ nhất thỏa mãn đề bài
Scoring
- Subtask 1 (10\%): n\le 10.
- Subtask 2 (20\%): n\le 1000.
- Subtask 3 (30\%): n\le 2\times 10^6.
- Subtask 4 (40\%): không có giới hạn gì thêm.
Test 1
Input (bàn phím
)
6
Output (màn hình
)
5
Test 2
Input (bàn phím
)
9
Output (màn hình
)
7
Comments