Practice OLP MT&TN lần 7 - năm 2026 - Bảng Không Chuyên

Cô giáo Mẫn đang dẫn dắt đội ngũ kỹ sư phát triển ứng dụng đọc báo SetNews. Để tối ưu hóa thuật toán phân phối các bài báo vào bộ nhớ đệm (cache), hệ thống cần chia tổng số lượng bài viết \(n\) thành các cụm đều nhau.

Cô Mẫn yêu cầu team phát triển phải tìm ra cách chia sao cho kích thước của một cụm (gọi là \(d\)) là lớn nhất có thể để giảm thiểu số lượng cụm cần quản lý. Tuy nhiên, để đảm bảo tính phân tán, kích thước \(d\) không được phép là một ước tầm thường của \(n\) (nghĩa là \(d\) phải khác 1 và \(n\)).

Nhiệm vụ của bạn là giúp team SetNews viết một chương trình nhận vào số nguyên dương \(n\) và in ra ước dương \(d\) lớn nhất thỏa mãn yêu cầu của cô giáo Mẫn. Nếu không tồn tại cách chia nào hợp lệ, hãy in ra -1.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(n\).
• Giới hạn: \(n \le 10^{14}\).

Output

• In ra một số nguyên duy nhất là ước dương không tầm thường lớn nhất của \(n\). Nếu không có ước nào thỏa mãn, in ra -1.

Example

6

3

Scoring

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

Cô Mẫn cùng team đang xây dựng một tính năng mới mang tên "Giải đố nhận tin VIP" cho SetNews. Mỗi ngày, hệ thống sẽ tự động sinh ra một mã khóa bảo mật dựa trên một số nguyên dương \(x\) ban đầu để thử thách người dùng.

Thuật toán tạo mã khóa của SetNews thực hiện chính xác \(k\) bước biến đổi. Ở mỗi bước, giá trị của \(x\) được cập nhật theo quy luật sau:

• Gọi \(a\) là số nguyên tạo thành bằng cách sắp xếp các chữ số của \(x\) theo thứ tự tăng dần (bỏ qua các chữ số \(0\) vô nghĩa ở đầu nếu có).
• Gọi \(b\) là số nguyên tạo thành bằng cách sắp xếp các chữ số của \(x\) theo thứ tự giảm dần.
• Nếu \(x\) là số chẵn, giá trị mới của \(x\) được gán bằng hiệu: \(x = b - a\).
• Nếu \(x\) là số lẻ, giá trị mới của \(x\) được gán bằng hiệu: \(x = x - a\).

Ví dụ, với \(x = 104\):

• \(x\) là số chẵn.
• Sắp xếp tăng dần: \(014 \rightarrow a = 14\).
• Sắp xếp giảm dần: \(410 \rightarrow b = 410\).
• Giá trị \(x\) mới: \(x = 410 - 14 = 396\).

Yêu cầu: Cho giá trị ban đầu \(x\) và số bước biến đổi \(k\), hãy giúp cô Mẫn và team SetNews xác định giá trị cuối cùng của mã khóa \(x\) sau khi thực hiện đủ \(k\) phép biến đổi.

Input

• Dòng duy nhất chứa hai số nguyên dương \(x\) và \(k\) \((1 \le x,k \le 10^{18})\).

Output

• In ra một số nguyên duy nhất là giá trị của \(x\) sau \(k\) bước biến đổi.

Example

21 2

0

104 2

594

Scoring

• Subtask 1 (\(30\%\) số điểm): \(x, k \le 10^5\)
• Subtask 2 (\(30\%\) số điểm): \(x \le 10^{18}, k \le 10^5\)
• Subtask 3 (\(40\%\) số điểm): \(x, k \le 10^{18}\)

Cô giáo Mẫn đang dẫn dắt đội ngũ phát triển phần mềm cho ứng dụng đọc báo SetNews. Để tăng trải nghiệm cá nhân hóa, ứng dụng có một tính năng sắp xếp giao diện hiển thị các chuyên mục tin tức trên trang chủ. Giả sử SetNews có \(n\) chuyên mục khác nhau được đánh số từ 1 đến \(n\). Cách sắp xếp các chuyên mục này trên màn hình được biểu diễn bởi một hoán vị của tập hợp \((1, 2, \dots, n)\).

Hiện tại, giao diện của người dùng đang hiển thị các chuyên mục theo thứ tự hoán vị \(p_1, p_2, \dots, p_n\). Cô giáo Mẫn yêu cầu team phát triển thêm một nút bấm "Trượt Chuyên Mục" để gợi ý luồng tin mới. Thay vì xáo trộn ngẫu nhiên, khi người dùng bấm nút này, thuật toán sẽ tìm hoán vị có thứ tự từ điển lớn hơn hoán vị hiện tại đúng \(k\) bước. Cụ thể, nếu gọi \(rank(p)\) là thứ tự từ điển của hoán vị \(p\), hệ thống cần tìm hoán vị \(q\) sao cho \(rank(q) - rank(p) = k\). Quy ước hoán vị tăng dần \((1, 2, \dots, n)\) có rank là 1, và hoán vị giảm dần \((n, n-1, \dots, 1)\) có rank là \(n!\).

Bạn hãy giúp team SetNews viết phần lõi thuật toán cho tính năng này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) mô tả số lượng chuyên mục và số bước trượt.
• Dòng thứ hai chứa \(n\) số nguyên phân biệt \(p_1, p_2, \dots, p_n\) là một hoán vị của tập \((1, 2, \dots, n)\), thể hiện thứ tự hiển thị hiện tại. Dữ liệu đảm bảo rằng \(rank(p) + k \le n!\).

Output

• In ra một dòng duy nhất chứa \(n\) số nguyên phân biệt \(q_1, q_2, \dots, q_n\) là hoán vị thể hiện thứ tự hiển thị của các chuyên mục sau khi người dùng bấm nút trượt.

Example

4 1
1 2 3 4

1 2 4 3

Scoring

• Subtask 1 (80 points): \(n \le 10^5, k \le 10^5\)
• Subtask 2 (20 points): \(n \le 10^5, k \le 10^{12}\)