Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOS2SUM - Tết Trung thu cả nhà đi chơi

Có sự thay đổi ở giới hạn bài toán. Vui lòng xem kỹ lại phần giới hạn.

Ở một gia đình nọ có 4 người. Người cha tên là Tổng, người mẹ tên là Hai Số. Không biết hai vợ chồng canh ngày tháng thế nào mà 2 đứa con đều sinh ra cùng ngày tháng mặc dù là khác năm. Hai đứa con có tên là Khó và Lắm.

Tối nay là Trung thu, đôi vợ chồng Tổng, Hai Số lên kế hoạch mua cho 2 đứa con Khó, Lắm mỗi đứa X viên kẹo. Để niềm vui được trọn vẹn, X phải là số ưa thích của cả Khó và Lắm. Dõi theo từng ngày Lắm lớn khôn, cặp vợ chòng ấy đã tìm được thông tin về những số mà Lắm thích. Lắm chỉ thích đúng P số đặc biệt. P số này được cha mẹ của Lắm ghi lại nhưng trong quá trình ghi chép lại gặp một số vấn đề nên có thể có trường hợp 1 số bị lặp lại nhiều lần cho nên danh sách được ghi lại sẽ có Q số. Khó là anh nên có vẻ hơi khó chiều hơn. Vì là một lập trình viên giỏi nên Khó đã viết một thủ tục Find(x) bằng PASCAL và input của thủ tục là một dãy A gồm N số không giảm. Dãy số là cố định và x là số cần kiểm tra xem Khó có thích hay không.


procedure Find(x: longint);

var i,j: longint;

Begin

i := 1;

j := n;

while  i < j do

begin

        if A[i] + A[j] = x

begin

writeln(i,’ ‘,j);

exit;

end;

        ìf A[i] + A[j] > x

j := j-1

    else

i := i+1;

end;

writeln(‘-1 -1’);

end;



Biết rằng nếu cặp số được in ra là (-1, -1 ) thì Khó không thích số đó. Giờ cha mẹ của Khó, Lắm phải tìm xem cặp số được in ra sau khi thực hiện thủ tục Find cho từng số trong danh sách Q số. Vì Q khá lớn nên Tổng, Hai Số đã nhờ tới các bạn lập trình viên VNOI_er giải quyết giúp vấn đề này.


Lưu ý: Mảng A được đánh số từ 1 tới N từ trái sang phải.


DỮ LIỆU VÀO


  • Dòng dầu chứa số nguyên dương N.
  • Dòng hai chứa N số miêu tả dãy A (A[i] <= A[i+1]).
  • Dòng ba chứa số nguyên dương Q.
  • Q dòng tiếp theo, dòng thứ i chứa số thứ i trong danh sách Q số mà Lắm thích.


DỮ LIỆU RA

  • Gồm Q dòng, dòng thứ i chứa cặp số được in ra khi thực hiện thủ tục Find cho số thứ i.

RÀNG BUỘC

  • N ≤ 104, Q ≤ 106.
  • 60% số test N ≤ 103, Q  105.
  • 0 ≤ Ai ≤ 109.
  • Các số trong danh sách số đặc biệt của Lắm là số nguyên không âm và tối đa là 2*109.

VÍ DỤ

Dữ liệu vào
6
1 2 3 4 5 6
4
6
9
5
12
Dữ liệu ra
1 5
3 6
1 4
-1 -1


Được gửi lên bởi:Alex & Friends
Ngày:2014-09-05
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOS round 26 - Trần Phan Anh Khoa

hide comments
2017-04-14 15:25:03
sub cả chục lần chỉ vì đọc nhầm dòng giới hạn -_-
@phanduy16
2014-09-08 09:01:14 rểc gềt kuỗc
Sao O(n*n*log(q)) đc có 35 là tnào?
2014-09-07 19:06:41 never give up !!
code ở trên được 60 thôi
2014-09-07 11:41:25 Thủ khoa vãn
sao chua cham dc vay moi nguoi
2014-09-06 21:11:35 Con Bò Huyền Thoại
code pascal của đề sai câu lệnh :)) chắc ng ra đề học C nên quên :))
2014-09-06 19:55:55 Thcs Ðặng Chánh Kỷ
@@ phantom: giống mình thế

Last edit: 2014-09-06 19:56:21
2014-09-06 19:54:28 Lollipop
lấy code trên đề bỏ vào bài là đk 72.5 r :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.