Bài 5. Tìm kiếm (HSG THPT TP. Hải Phòng 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT TP. Hải Phòng 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng ~A~ có ~n~ số nguyên dương ~\{a_1, a_2, \ldots, a_n\}~.

Với mỗi số nguyên dương ~a_i~, tìm số nguyên dương ~a_j (j > i)~ với ~j~ nhỏ nhất thỏa mãn ~a_j~ có nhiều ước hơn ~a_i~; nếu không có số ~a_j~ thỏa mãn thì kết quả tìm kiếm là −1.

Dữ liệu vào

Gồm hai dòng (dữ liệu đảm bảo ~max\{a_i\} - min\{a_i\} \le 10^6~):

  • Dòng 1: Chứa số nguyên dương ~n (n \le 2 \times 10^5)~.
  • Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n (a_i \le 10^6)~.

Kết quả

Một dòng có ~n~ số nguyên theo thứ tự là kết quả tìm kiếm theo yêu cầu.

Ví dụ

Input 1

6
6 18 7 10 9 8

Output 1

18 -1 10 -1 8 -1

Số ước tương ứng của các số là 4, 6, 2, 4, 3, 4. Với ~a_1 = 6 (4~ ước), số đầu tiên bên phải có nhiều ước hơn là 18 (6 ước). Với ~a_2 = 18~ không có số nào bên phải nhiều ước hơn 6 nên kết quả −1. Tương tự cho các phần tử còn lại.

Ràng buộc

  • Subtask 1 (20% số điểm): ~n \le 10^3~ và ~a_i \le 10^4~.
  • Subtask 2 (50% số điểm): ~n > 10^3~ và ~a_i \le 10^6~.
  • Subtask 3 (30% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...