HSG THPT Hải Phòng 2021 - Bài 3
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ và một số nguyên ~k~.
Hãy tìm hai chỉ số ~p, q~ (~1 \leq p, q \leq n; p \neq q~) sao cho ~\frac{a_p + a_q}{2} = k~.
Input
Dòng 1: Chứa hai số nguyên ~n~ và ~k~.
Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~.
Output
Hai chỉ số ~p, q~ tìm được.
Trong trường hợp có nhiều chỉ số ~p, q~ thỏa mãn, chỉ cần in ra một kết quả bất kỳ thỏa mãn. Nếu không tồn tại cặp chỉ số thỏa mãn yêu cầu, ghi ra hai số ~0~.
Các số trên một dòng của kết quả phải ghi cách nhau ít nhất một dấu cách.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~60\%~ | ~n \leq 5000, |k| \leq 10^9, |a_i| \leq 10^9~ |
| 2 | ~20\%~ | ~5000 \leq n \leq 10^5, |k| \leq 10^5, |a_i| \leq 10^5~ |
| 3 | ~20\%~ | ~5000 \leq n \leq 10^5, |k| \leq 10^9, |a_i| \leq 10^9~ |
Sample Input 1
6 4
1 3 2 5 8 6
Sample Output 1
2 4
Sample Input 2
3 5
1 3 2
Sample Output 2
0 0
Notes
Trong ví dụ thứ nhất, có nhiều bộ chỉ số (~p; q~) thỏa mãn điều kiện đề bài như:
(~2; 4~)
(~4; 2~)
(~3; 6~)
(~6; 3~)
Bình luận
Mình tạo 1 struct lưu vị trí và giá trị, sau đó sort và dùng two pointers.
bài này ta có thể lưu chỉ số của dãy a thành 1 ma trận sau đó ta sắp xếp chúng lại rồi dùng 2 con trỏ
dùng dict nhanh hơn nhé
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài này không tìm kiếm nhị phân cũng AC mà ?
ap dung two sum trong leetcode :))
này chắc hash table nhỉ
sử dụng unordered_map
Dùng 2 con trỏ tốt hơn là dùng tìm kiếm nhị phân =))
dùng tknp kiểu gì b , mình chỉ biết làm 2 trỏ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Tìm kiếm nhị phân.