[Mảng 1 Chiều Cơ Bản]. Bài 50. Số cặp chẵn
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
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho mảng A[] gồm N phần tử, 28Tech có một câu hỏi đó là trong mảng A[] có bao nhiêu cặp số A[i] và A[j] với i khác j mà tổng 2 số này là 1 số chẵn. Nhiệm vụ của bạn là đếm giúp anh ta số cặp thỏa mãn.
Đầu vào
• Dòng 1 là N : số lượng phần tử trong mảng
• Dòng 2 là N số trong mảng cách nhau 1 dấu cách
Giới hạn
1<=N<=10^6
0<=A[i]<=10^6
Đầu ra
In ra số cặp thỏa mãn
Ví dụ :
Input 01
8
11 17 8 18 7 10 3 18
Output 01
12
Bình luận
for(int i=0; i < n-1;i++) { for(int j=i+1;j < n; j++) { tong=a[i]+a[j]; if(tong %2==0) dem++; tong=0; } }cout << dem;
Sao lại bị lỗi runtime mn nhỉ ?
include <bits/stdc++.h>
define ll long long
using namespace std; int mod = 1e9 + 7; int a[1000005];
long long combination(int n, int k) { if (k > n) return 0; if (k == 0 || k == n) return 1;
}
int main() { int n; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; } int k = 2; int odd = 0; int even = 0; for(int i = 0; i < n; i++) { if(a[i] % 2 == 0) even++; else odd++; } cout << combination(odd, k) + combination(even, k); }
Cho những ai muốn tham khảo thì hướng giải của mình là tìm số lượng số chẫn và số lẻ. Sau đó công 2 tổ hợp chập 2 của lẻ và chẵn lại vì C + C = C và L + L = C
áp dụng lý thuyết : A%2=0 <=> (a%2 + b%2)%2 = 0 với (A=a+b) -> a%2 = b%2 = 0 hoặc a%2 = b%2 = 1 => đếm cặp cùng chẵn hoặc cùng lẻ
include <bits/stdc++.h>
using namespace std;
int main() {
}
include <iostream>
include <vector>
using namespace std; int main() { int N; cin >> N; vector<int> A(N); int d1 = 0, d2 = 0; for (int i = 0; i < N; ++i) { cin >> A[i]; if (A[i] % 2 == 0) { d1++; } else { d2++; } } long long pairs = (long long)d1 * (d1 - 1) / 2 + (long long)d2 * (d2 - 1) / 2; cout << pairs << endl; return 0; }
include <bits/stdc++.h>
using namespace std;
define ll long long;
int main() { iosbase::syncwith_stdio(0); cin.tie(0);cout.tie(0); int n,x,dem1=0,dem2=0; cin>>n; while(n--) { cin>>x; if(x%2==0) dem1++; else dem2++; } if(dem1>1) dem1--; else dem1=0; if(dem2>0) dem2--; else dem2=0; cout<<(1lldem1(dem1+1)/2)+(1lldem2(dem2+1)/2); return 0; }
Ai cho em xin hướng giải bài này với ạ
Em cảm ơn 2 người nhiều ạ <3
Ý tưởng : Bài này đếm số lượng số chẳn và số lượng số lẻ . Số chẳn được tạo thành khi ta cộng 2 số chẳn hoặc 2 số lẻ . Vd : 8 11 17 8 18 7 10 3 18 Số lượng số chẳn là : 8 18 10 18 thì ta sẽ có 6 cặp, số 8 có 3 cặp, số 18 có 2 cặp, số 10 có 1 cặp => số lượng số cặp chẳn sẽ là : tổng từ 1 đến n-1 với n là số lượng số chẳn: ta sẽ dùng công thức : n(n+1)/2 để tính tổng , vd : có 4 số chẳn thì số cặp chẳn sẽ là : tổng từ 1 đến n-1 là : tổng từ 1 đến 3: 3(3+1)/2=6 ta cũng là tương tự như vậy để tính số cặp lẻ . Sau đó cộng số cặp lẻ và cặp chẳn lại là có kq Nhưng lưu ý : TH1 : chỉ có 1 số lẻ , thì số cặp lẻ sẽ là 0 vd : 3 2 4 6 Thì ta có số cặp lẻ là 0 , số cặp chẳn là 3 => kết quả là 3 TH2 : chỉ có 1 số chẳn thì số cặp chẳn sẽ là 0 vd : 8 3 5 7 9 Thì ta có số cặp chẳn là 0 , số cặp lẻ 6=> kết quả là 6
dùng đếm pp + tính chất thôi, L+L = C, C+C = C