Hướng dẫn giải của [VT Thiếu nhi] BÀI 08: TICH9
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số cặp ~(i, j)~ với ~i < j~ sao cho tích ~A_i \cdot A_j~ có chữ số tận cùng bằng 9. Các ~A_i~ có thể dài tới 100 chữ số nên đọc dạng chuỗi và chỉ lấy chữ số hàng đơn vị. Tích có tận cùng 9 khi cặp chữ số tận cùng là (1,9), (9,1), (3,3) hoặc (7,7).
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Thử mọi cặp ~(i, j)~ và kiểm tra tích hai chữ số tận cùng có tận cùng bằng 9. Nếu chỉ nộp sub này: đúng 7/10 test.
Sub 2: Đếm theo chữ số tận cùng — ~O(n)~
Đếm số phần tử có mỗi chữ số tận cùng ~c_0..c_9~, rồi đáp số là ~c_1 \cdot c_9 + \binom{c_3}{2} + \binom{c_7}{2}~. Chạy riêng sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Chương trình đọc ~n~ và các số dạng chuỗi; nếu ~n \le 1000~ gọi sub1, còn lại gọi sub2.
Số test: 10 (chương trình đầy đủ đúng 10/10; sub1 xử lý 6 test, sub2 xử lý 4 test).
#include <bits/stdc++.h>
using namespace std;
int n;
string s[100005]; // A_i co the rat lon (<= 10^100) nen doc dang chuoi
int d[100005]; // d[i] = chu so hang don vi cua A_i (tich 2 so co tan cung 9 chi phu thuoc tan cung)
// Sub 1: vet can. Thu moi cap (i, j) voi i < j, kiem tra tich d[i]*d[j] co tan cung bang 9. O(n^2)
// Dung khi n <= 1000
void sub1() {
long long cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (d[i] * d[j] % 10 == 9) cnt++;
cout << cnt << "\n";
}
// Sub 2: day du. Tich co tan cung 9 khi tan cung 2 so la (1,9), (9,1), (3,3) hoac (7,7).
// Dem so luong moi tan cung roi to hop. O(n).
void sub2() {
long long c[10] = {0};
for (int i = 1; i <= n; i++) c[d[i]]++;
long long cnt = c[1] * c[9] + c[3] * (c[3] - 1) / 2 + c[7] * (c[7] - 1) / 2;
cout << cnt << "\n";
}
int main() {
freopen("TICH9.INP", "r", stdin);
freopen("TICH9.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
d[i] = s[i].back() - '0';
}
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận