Khách hàng may mắn
Xem dạng PDF
Gửi bài giải
Điểm:
5,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Nhân dịp năm mới, siêu thị tổ chức chương trình khách hàng may mắn.
Có ~n~ khách hàng tham gia, khách hàng thứ ~i~ nhận được một số nguyên ~a_i (a_i ≠ 0)~.
Ban tổ chức cần tìm hai số nguyên dương ~u, v (u ≤ v)~ sao cho:
Có ít nhất ~x~ khách hàng có số may mắn thỏa mãn: ~u \le a_i \le v~
Có ít nhất ~y~ khách hàng có số may mắn thỏa mãn: ~u \le -a_i \le v~
Trong tất cả các cặp ~(u, v)~ thỏa mãn:
- Ưu tiên cặp có giá trị ~v - u~ nhỏ nhất.
- Nếu có nhiều cặp cùng nhỏ nhất, chọn cặp có ~u~ nhỏ nhất.
Nếu không tồn tại cặp nào thỏa mãn yêu cầu, in ra ~-1~.
Input
- Dòng đầu tiên chứa ba số nguyên dương ~n, x, y~ ~(1 ≤ n ≤ 2 × 10^5, x, y ≤ n)~
- Dòng thứ hai chứa ~n~ số nguyên: ~a_1, a_2, ..., a_n~ thỏa mãn: ~0 < |a_1| < |a_2| < ... < |a_n| < 10^6~
Output
- Nếu tồn tại cặp ~(u, v)~ thỏa mãn, in ra hai số ~u v~.
- Nếu không tồn tại, in ra ~-1~.
Sample Input
4 1 2
1 -2 -3 4
Sample Output
1 3
Giải thích
Có 3 cặp ~(u, v)~ thỏa mãn:
- ~(1, 4) với v - u = 3~
- ~(1, 3) với v - u = 2~
- ~(2, 4) với v - u = 2~
Trong đó ~(1, 3)~ có ~v - u~ nhỏ nhất và ~u~ nhỏ nhất.
Giới hạn
- 50% số test: ~n ≤ 2 × 10^2, |ai| ≤ 10^3~
- 30% số test: ~2 × 10^2 < n ≤ 2 × 10^3, |ai| ≤ 10^6~
- 20% số test: ~2 × 10^3 < n ≤ 2 × 10^5, |ai| ≤ 10^6~
Bình luận