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ả:
Hieu Nguyen
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

Hãy đọc nội quy trước khi bình luận.


  • 0
    theguy777_jaboi  đã bình luận lúc 12, Tháng 1, 2025, 1:04

    làm sao để không bị tle


  • 0
    khaibadao  đã bình luận lúc 2, Tháng 11, 2024, 11:17 ← sửa 3

    Solution : Để a[i] + a[j]*a[j] == k, ta có thể nhân ra ở đây là với mỗi số a[j] = (long)sqrt(k - a[i]) x (long)sqrt(k - a[i]) Ta sử dụng thêm một unordered_map (để có thể tối ưu thời gian thay vì sử dụng map)

    ! Code : !unordered_map <long, int> maa; ! for(int i = 0 ; i < n ; ++i){ ! cin >> a[i]; ! ++maa[a[i]]; ! } a[i] và a[i] cũng có thể là một cặp Sau mỗi vòng lặp thì ta giảm sự xuất hiện của phần tử a[i] xuống 1 lần Code mẫu : for(int i = 0; i < n ; ++i){ long x = sqrt(k - a[i]); // tìm kiếm a[j] if(x*x == k - a[i]){ // kiểu tra liệu x có hợp lệ hay không if(maa[x]){ cnt += maa[x]; // số lần xuất hiện của x cũng chính là số cặp được tạo thành } } --maa[a[i]]; // giảm số lần xuất hiện của a[i] } Chúc các bạn thành công hehe:33


  • 0
    dinhvantung0611  đã bình luận lúc 24, Tháng 1, 2024, 12:59 ← sửa 2

    Ý 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


  • -1
    ThanhMoiTapCode1  đã bình luận lúc 13, Tháng 8, 2023, 14:24

    Mn cho em xin ý tưởng bài này với ạ em dùng tknp mà không được:v


    • 0
      18_Lonely  đã bình luận lúc 15, Tháng 8, 2023, 17:49

      Kiểm tra số chính phương để giảm số lần duyệt.