C3 - Duyệt mảng

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Hieu Nguyen
Problem types
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    theguy777_jaboi  commented on Jan. 12, 2025, 1:04 a.m.

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


  • 0
    khaibadao  commented on Nov. 2, 2024, 11:17 a.m. ← edit 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  commented on Jan. 24, 2024, 12:59 p.m. ← edit 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  commented on Aug. 13, 2023, 2:24 p.m.

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


    • 0
      18_Lonely  commented on Aug. 15, 2023, 5:49 p.m.

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