[Phú Thọ - 23] Khách hàng may mắn
Nhân dịp năm mới, để thu hút khách hàng đến mua sắm, siêu thị Hùng Vương tổ chức chương trình khách hàng may mắn: mỗi khách hàng đến siêu thị đều nhận được một số may mắn, khách hàng thứ i nhận số may mắn là số nguyên a_i được tạo tự động bằng máy tính. Kết thúc chương trình có n khách hàng nhận được số may mắn. Ban tổ chức tiến hành quay số trúng thưởng, những khách hàng may mắn sẽ nhận được phần thưởng của siêu thị. Để đảm bảo tính khách quan Ban tổ chức nhờ một khách hàng bắt thăm ngẫu nhiên hai số nguyên x, y (1 <= x, y <= n) sau đó sử dụng một chương trình máy tính để tìm ra hai số u, v (0 < u <= v <= 10^6) thỏa các điều kiện sau:
- Số lượng người có số may mắn a_i thỏa mãn u <= a_i <= v tối thiểu là x.
- Số lượng người có số may mắn a_j thỏa mãn u <= -a_j <= v tối thiểu là y.
- Hiệu v - u là nhỏ nhất.
Sau khi tìm được hai số u, v thỏa mãn các điều kiện trên khách hàng có số may mắn a_i thỏa mãn u <= |a_i| <= v sẽ được nhận phần thưởng của siêu thị.
Yêu cầu: Hãy giúp Ban tổ chức tìm hai số u, v thỏa mãn các điều kiện trên.
- Số lượng người có số may mắn a_i thỏa mãn u <= a_i <= v tối thiểu là x.
- Số lượng người có số may mắn a_j thỏa mãn u <= -a_j <= v tối thiểu là y.
- Hiệu v - u là nhỏ nhất.
Sau khi tìm được hai số u, v thỏa mãn các điều kiện trên khách hàng có số may mắn a_i thỏa mãn u <= |a_i| <= v sẽ được nhận phần thưởng của siêu thị.
Yêu cầu: Hãy giúp Ban tổ chức tìm hai số u, v thỏa mãn các điều kiện trên.
Dữ liệu vào: Từ file KHMM.INP
- 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 (0 < |a_1| < |a_2| < ... < |a_n| < 10^6).
- Dòng thứ hai chứa n số nguyên a_1, a_2, ..., a_n (0 < |a_1| < |a_2| < ... < |a_n| < 10^6).
Kết quả: Ghi ra file KHMM.OUT
Một dòng duy nhất là hai số u, v tìm được (các số cách nhau một dấu cách). Nếu có nhiều cặp số (u, v) thỏa mãn bài toán thì in ra cặp số (u, v) có u nhỏ nhất; nếu không tìm được u, v thỏa mãn yêu cầu thì in ra -1.
Ví dụ:
KHMM.INP 4 1 2 1 -2 -3 4 KHMM.OUT 1 3
Giải thích:
Có 3 cặp số u, v thỏa mãn các điều kiện:
- Cặp {u = 1, v = 4} có v - u = 3
- Cặp {u = 1, v = 3} có v - u = 2
- Cặp {u = 2, v = 4} có v - u = 2
=> Cặp {u = 1, v = 3} có v - u nhỏ nhất và u nhỏ nhất.
- Cặp {u = 1, v = 4} có v - u = 3
- Cặp {u = 1, v = 3} có v - u = 2
- Cặp {u = 2, v = 4} có v - u = 2
=> Cặp {u = 1, v = 3} có v - u nhỏ nhất và u nhỏ nhất.
Giới hạn:
- Có 50% số test tương ứng 50% số điểm của bài có n <= 2.10^2, |a_i| <= 10^2.
- Có 30% số test tương ứng 30% số điểm của bài có 2.10^2 < n <= 2.10^3, |a_i| <= 10^4.
- Có 20% số test tương ứng 20% số điểm của bài có 2.10^3 < n <= 2.10^5, |a_i| <= 10^6.
- Có 30% số test tương ứng 30% số điểm của bài có 2.10^2 < n <= 2.10^3, |a_i| <= 10^4.
- Có 20% số test tương ứng 20% số điểm của bài có 2.10^3 < n <= 2.10^5, |a_i| <= 10^6.
Comments