#5456. Cặp số có tổng K (TWOSUM)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một dãy số A gồm N số nguyên đã được sắp xếp tăng dần và một số nguyên Target . Hãy tìm chỉ số của hai phần tử sao cho tổng của chúng bằng Target . Nếu có nhiều cặp, in ra cặp bất kỳ. Nếu không có, in ra No solution. (Chỉ số tính từ 1).

Dữ liệu:

  • Dòng 1: Hai số nguyên N Target .
  • Dòng 2: N số nguyên A_i ( |A_i| \le 10^9 ).

Kết quả:

  • Hai số nguyên là chỉ số của hai phần tử tìm được, cách nhau bởi dấu cách.

Ví dụ:

Dữ liệu:

4 9
2 7 11 15

Kết quả:

1 2

Giới hạn:

  • 70% số test có 1 \le N \le 1000 (Chấp nhận dùng 2 vòng lặp O(N^2) ).
  • 30% số test có 1000 < N \le 10^6 (Bắt buộc dùng Hai con trỏ - Two Pointers O(N) ).