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.

n khách hàng tham gia, khách hàng thứ i nhận được một số nguyên ai (ai ≠ 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 ai \le v ]

  • Có ít nhất y khách hàng có số may mắn thỏa mãn: [ u \le -ai \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: [ a1, a2, ..., an ] thỏa mãn: [ 0 < |a1| < |a2| < ... < |an| < 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)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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.