Đăng nhập để hỏi chi tiết
HELP
Cho dãy a gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3. Nói cách khác, bạn phải đếm xem có bao nhiêu cặp chỉ số i, j (1 ≤ i < j ≤ n) sao cho tổng ai + aj chia hết cho 3.
Dữ liệu:
- Dòng 1: Một số nguyên duy nhất n (1 ≤ n ≤ 105).
- Dòng 2: Ghi n số nguyên dương a1, a2, ..., an (1 ≤ ai ≤ 105, ) là các phần tử của dãy.
Kết quả:
- Một dòng duy nhất ghi số lượng cặp số của dãy a có tổng chia hết cho 3.
Ví dụ:
BAI4.INP
BAI4.OUT
Giải thích
5
3 4 2 3 4
3
3 cặp số tìm được có chỉ số là: (1,4) (2,3) (3,5)
4
3 6 9 12
6
6 cặp số tìm được có chỉ số là: (1,2) (1,3), (1,4), (2,3) (2,4) (3,4)
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
TRẢ LỜI
Hint:
lấy từng phần tử của A chia cho 3 tìm phần tử sử dụng mảng đánh dấu
a[n % 3]++
tính giá tri: (a[0] * (a[0] - 1)) / 2 + (a[1] * a[2])
(a[0] * (a[0] - 1)) / 2 chọn 2 phần tử chia hết cho 3
(a[1] * a[2]) : số cách chọn tổng 2 phần tử chia hết cho 3
#include <bits/stdc++.h>
using namespace std;
void solve()
{
long long tt, a[4] = {0, 0, 0, 0};
cin >> tt;
while (tt--){
long long n;
cin >> n;
a[n % 3]++;
}
cout << a[0] * (a[0] - 1) / 2 + (a[1] * a[2]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
52 vote
#danglam228
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("BAI4.INP", "r", stdin);
freopen("BAI4.OUT", "w", stdout);
cin >> n;
vector<int> f(3, 0);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
f[x % 3]++;
}
long long e = (long long)f[0] * (f[0] - 1) / 2;
e += (long long)f[1] * f[2];
cout << e << endl;
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
52 vote
Đăng nhập để hỏi chi tiết
Bạn muốn hỏi điều gì?
Đặt câu hỏiTham Gia Group Dành Cho Lớp 8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí
Bảng tin
Bạn muốn hỏi điều gì?
Đặt câu hỏi
Cơ quan chủ quản: Công ty Cổ phần Công nghệ Giáo dục Thành Phát
Tải ứng dụng
Inbox: m.me/hoidap247online
Trụ sở: Tầng 7, Tòa Intracom, số 82 Dịch Vọng Hậu, Cầu Giấy, Hà Nội.
Giấy phép thiết lập mạng xã hội trên mạng số 331/GP-BTTTT do Bộ Thông tin và Truyền thông.