Tìm hai số có tổng cho trước

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Cho một dãy gồm ~n~ số nguyên dương và một số nguyên ~k~. Hãy kiểm tra xem có hai phần tử ở hai vị trí khác nhau trong dãy mà tổng bằng ~k~ hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n, k~ (~2 \le n \le 10^5~, ~1 \le k \le 2 \times 10^9 + 1~).

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, \dots, a_n~ (~a_i \le 10^9~).

Kết quả

In ra YES nếu tồn tại cặp thỏa mãn, ngược lại in NO.

Ví dụ

Ví dụ 1

Input:

5 9
2 7 11 15 1

Output:

YES

Ví dụ 2

Input:

3 100
1 2 3

Output:

NO

Giải thích

Duyệt từng phần tử ~x~, kiểm tra xem ~k - x~ đã xuất hiện trước đó chưa (dùng set), rồi mới thêm ~x~ vào. Thử mọi cặp mất ~n^2 = 10^{10}~ phép tính, quá chậm.


Đang tải...