Tìm cặp số

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Cho một mảng số nguyên \(A\) có \(N\) phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm vị trí của hai phần tử khác nhau bất kỳ sao cho tổng của chúng có giá trị là \(X\). Nếu trong dãy \(A\) không tồn tại hai phần tử khác nhau có tổng là \(X\) thì in ra "No solution".

Input

Dòng đầu chứa 2 số nguyên \(N\) và \(X\).
Dòng tiếp theo chứa \(N\) số nguyên \(A_i\).

Output

Hai vị trí \(i\) và \(j\) khác nhau sao cho tổng ở hai vị trí này có giá là \(X\). In vị trí phần tử nhỏ hơn trước phần tử lớn hơn.
Nếu không tồn tại in ra "No solution".

Constants

\(2 \leq N \leq 10^6\) và \(0 \leq A_i, X \leq 10^9\)

Example

Test 1

Input

6 16
2 3 5 7 9 12

Output

4 5

Bình luận

include <bits/stdc++.h>

define endl '\n'

typedef long long ll;
using namespace std;

int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);

ll n,x; 
cin>>n>>x; 
ll* a = new ll[n];
for(ll i = 0;i<n;i++){
    cin>>a[i]; 
}
ll left = 0; ll right = n -1;

while(left < right){
    ll sum = a[left] + a[right];

    if(sum==x){
        cout<< left + 1 << " " << right+1; 
        return 0; 
    }else if(sum < x){
        left++; 
    }else{
         right--; 
    }
}
cout<<"No solution"; 
delete[]a;

}

Phản hồi

UserZero • 11:45 a.m. 2 Tháng 3, 2025 •

\(10^6\) hơi ít. Vậy thì mảng không sort vẫn đc

0
Phản hồi Chia sẻ

def find_two_sum(N, X, A):
left, right = 0, N - 1

while left < right:
    total = A[left] + A[right]
    if total == X:
        print(left + 1, right + 1)  # In ra vị trí, nhớ cộng 1 vì mảng bắt đầu từ chỉ số 1
        return
    elif total < X:
        left += 1
    else:
        right -= 1

print("No solution")

Nhập dữ liệu

N, X = map(int, input().split())
A = list(map(int, input().split()))

Gọi hàm tìm kiếm

find_two_sum(N, X, A)

Phản hồi

dxuhai • 2:50 p.m. 12 Tháng 5, 2024 •

cũng dễ

This comment is hidden due to too much negative feedback. Click here to view it.

-8
Phản hồi Chia sẻ

SBD02_Long • 7:38 a.m. 12 Tháng 5, 2024 •

#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 16;
int a[M];
int main()
{
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int l = 1, r = n; l < r; ++l)
{
while (l < r - 1 && a[l] + a[r] > x) --r;
if (a[l] + a[r] == x)
{
cout << l << ' ' << r;
return 0;
}
}
cout << "No solution";
return 0;
}

0
Phản hồi Chia sẻ

kietlqt • 4:14 p.m. 9 Tháng 5, 2024 •

This comment is hidden due to too much negative feedback. Click here to view it.

-6
Phản hồi Chia sẻ

kietlqt • 4:14 p.m. 9 Tháng 5, 2024 •

dễ vãi

This comment is hidden due to too much negative feedback. Click here to view it.

-6
Phản hồi Chia sẻ

tuanhung2206_ÁHASDHASHDJ • 5:55 p.m. 21 Tháng 1, 2024 •

ảo thật đấy

-4
Phản hồi Chia sẻ

MinhTri2400811 • 10:50 a.m. 14 Tháng 1, 2024 •

ẢO THUẬT ĐẾI

This comment is hidden due to too much negative feedback. Click here to view it.

-5
Phản hồi Chia sẻ

huynocode • 11:14 a.m. 17 Tháng 5, 2023 •

trường hợp no solusion làm sao vậy ạ?

0
Phản hồi Chia sẻ

19 bình luận nữa