Trò chơi ô số

View as PDF

Submit solution

Points: 1400 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem types

Icebearn ô 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

There are no comments at the moment.