Bài viết: 28 
4096
129
Cho dãy n số nguyên không âm a1, a2, an. Người ta tiến hành chọn ra 2 chỉ số i, j sao cho i < j
Và xóa khỏi dãy 2 số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn.
Yêu cầu: Cho dãy số a1, a2, an. Hãy đếm số lượng cách chọn 2 chỉ số i, j thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.
Dữ liệu nhập: gồm 2 dòng
- Dòng 1: Chứa số nguyên n (2 ≤ n ≤ 106)
- Dòng 2: Chứa n số nguyên không âm a1, a2, an (0 ≤ ai ≤ 109)
Dữ liệu xuất:
- Là một số nguyên cho biết số cách chọn 2 chỉ số i, j thỏa mãn.
Thuật toán:
Code:
Và xóa khỏi dãy 2 số ai, aj để tổng giá trị các số còn lại trong dãy là số chẵn.
Yêu cầu: Cho dãy số a1, a2, an. Hãy đếm số lượng cách chọn 2 chỉ số i, j thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.
Dữ liệu nhập: gồm 2 dòng
- Dòng 1: Chứa số nguyên n (2 ≤ n ≤ 106)
- Dòng 2: Chứa n số nguyên không âm a1, a2, an (0 ≤ ai ≤ 109)
Dữ liệu xuất:
- Là một số nguyên cho biết số cách chọn 2 chỉ số i, j thỏa mãn.
Thuật toán:
- Ta sẽ đếm số lượng các số chẵn và lẻ trong dãy, đồng thời xác định tổng các phần tử trong dãy là lẻ hay chẵn.
- Nếu tổng của dãy là một số lẻ, tức là ta phải xóa một số lẻ và 1 số chẵn để tổng trở về chẵn. ⇒ Với c số chẵn và l số lẻ, là có số lượng các cặp có thể xóa là c*l.
- Nếu tổng của dãy là một số chẵn, ta phải xóa 2 số chẵn hoặc 2 số lẻ. Tức tổng số cách xóa sẽ bằng tổng số cách chọn ra 2 phần tử chẵn hoặc 2 phần tử lẻ từ 2 tập c và l.
- Xét riêng từng tập c và l, ví dụ tập c có 5 phần tử, khi thêm một phần tử nữa vào tập thì ta sẽ có thêm 5 cách ghép phần tử thứ 6 đó với 5 phần tử kia. Tức tổng quát, với n phần tử, ta sẽ có 1+2+.. +n-1 cách chọn 2 phần tử bất kỳ.
Code:
Mã:
#include <bits/stdc++.h>
using namespace std;
long long int a, n, anschan, ansle, chan, le, fn;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("xoso.inp", "r", stdin);
//freopen("xoso.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a;
if (!(a%2)) chan++; else le++;
fn = (fn+a)%2;
}
if (fn) cout << chan*le; else{
for (int i = 1; i < chan; i++) anschan += i;
for (int i = 1; i < le; i++) ansle += i;
cout << anschan + ansle;
}
//cout << " " << fn;
return 0;
}
Last edited by a moderator:
