C3 - Duyệt mảng
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho dãy số nguyên dương gồm ~N~ phần tử ~a_1, a_2, ..., a_N~. In ra số lượng cặp (~i, j~) thỏa mãn:
- ~1 ≤ i ≤ j ≤ N~;
- ~a_i + a^2_j = X~ với ~X~ cho trước.
Input
- Dòng đầu gồm 2 số nguyên dương ~N~ và ~K~ (~N ≤ 10^5 , K ≤ 10^9~);
- Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ (~a_i ≤ 500~).
Output
- In ra số cặp (~i, j~) thỏa mãn.
Sample
Input #1
3 5
1 2 1
Output #1
1
Giải thích: Có 1 cặp số thỏa mãn tại chỉ số ~(i, j) = (0, 1)~, ~a_0 + a^2_1 = 1 + 2^2 = 5.~
Problem source: Kc97ble - Free Contest
Bình luận
Ý tưởng: Nếu code trâu việc TLE sẽ xảy ra. Vậy có cách duyệt nào tối ưu hơn không ?
ai + aj^2 = X. Mà điều kiện cho của bài là X, ai, aj luôn là 1 số dương. Vậy nếu aj^2 >= X thì sẽ không thể tồn tại số ai để ai + aj^2 = X. Vậy ta chỉ cần tìm ai khi aj^2 < X (1 <= i <= j <= N), thời gian chạy code sẽ giảm và ta sẽ AC (Đây là cách dễ hiểu, đơn giản, còn nhiều cách tối ưu hơn).
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG
Mn cho em xin ý tưởng bài này với ạ em dùng tknp mà không được:v
Kiểm tra số chính phương để giảm số lần duyệt.