Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho mảng arr, tìm trong mảng arr có tồn tại 3 phần tử arr[i] + arr[j] + arr[k] = key, với key là giá trị cho trước. In giá trị arr[i], arr[j] và arr[k] ra màn hình.

• a) Thiết kế giải thuật với ĐPT (độ phức tạp) về thời gian tùy ý.
• b) Thiết kế giải thuật với ĐPT về thời gian là ~O(n^2)~.

Đề gốc là bài thiết kế giải thuật (viết hàm), không có định dạng vào/ra; định dạng dưới đây được quy ước để chấm bài. Bộ test có ~n~ tới ~3000~ nên chỉ thuật toán ~O(n^2)~ (câu b) mới qua được hết.

Dữ liệu vào

• Dòng đầu gồm 2 số nguyên ~n~ và ~key~.
• Dòng thứ hai gồm ~n~ số nguyên ~arr_0, arr_1, \ldots, arr_{n-1}~ của mảng.

Kết quả

• Nếu tồn tại 3 vị trí khác nhau ~i, j, k~ thỏa ~arr_i + arr_j + arr_k = key~ thì in 3 giá trị ~arr_i, arr_j, arr_k~ trên một dòng, cách nhau một dấu cách (có nhiều bộ thì in bộ nào cũng được, thứ tự 3 số tùy ý).
• Nếu không tồn tại thì in NO.

Giới hạn

• ~1 \le n \le 3000~.
• ~|arr_i| \le 10^9~, ~|key| \le 2 \cdot 10^9~.

Sample Input 1

6 24
12 3 4 1 6 9

Sample Output 1

3 9 12

Giải thích

Mảng ~[12, 3, 4, 1, 6, 9]~ và ~key = 24~. Ta có ~12 + 3 + 9 = 24~ nên in ra 3 giá trị đó. In 12 3 9 hay 3 9 12 đều đúng.