Hướng dẫn cho Tính tổng (OLP MT&TN 2021 CT)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)
\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\color{orange}{\text{Hướng dẫn}}\)
-
Xét các số \(X\) có các chữ số bằng nhau và \(1 \leq X \leq 10^{1000}\)
-
Kết quả của một giá trị \(v \leq 1000\) là \(min\Big(\frac{X}{v}\ \ |\ \ X\ \ \vdots\ \ v\Big)\) hoặc \(-1\) nếu \(\nexists X\ \ \vdots\ \ v\)
-
Nhận xét: Nếu \(v = 10k\) hoặc \(v = 16k\) hoặc \(v = 25k\) với \(k \in \mathbb{N}\) thì sẽ không tồn tại số \(X\) như thế, ngược lại mọi số đều tồn tại kết quả
\(\color{goldenrod}{\text{Tiếp cận}}\)
-
Sử dụng bignum với các phép toán đông dư (mod), phép chia và phép so sánh để xuất kết quả:
-
Tiền xử lí tính toán bằng việc sàng, sau đó lưu lại mảng tiền xử lí vào code, rồi sau đó sử dụng mảng đã được tính toán sẵn để tính giá trị
Đưa kết quả về dạng (\(X_v = rep_v\) lần chữ số \(dig_v\)) và \(\frac{X}{v}\) là kết quả
\(\color{purple}{\text{Độ phức tạp}}\)
- Dùng bignum: \(O(1000 \times 9 \times 1000)\) thời gian
\(O(1000 \times 9)\) số số bignum cần duyệt
\(O(1000)\) thời gian để tính giá trị modulo, phép chia và so sánh kết quả
Hằng số cao
- Dùng tiền xử lí: \(O(1000 \times 9 \times 1000)\) thời gian tạo code - \(O(1000)\) truy vấn
\(O(1000 \times 9)\) số số bignum cần duyệt
\(O(1000)\) để tính toán modulo, phép chia và so sánh kết quả (có thể tối ưu)
Có thể tối ưu để hằng số thấp (mặc dù không cần thiết)
\(O(1000)\) trong thời gian biên dịch lại mảng
\(O(1000)\) trong việc tìm giá trị \(\frac{X}{v}\)
\(\color{green}{\text{Code sinh code }}\): Tiền xử lí, Toán học
\(^{^{\color{purple}{\text{Độ phức tạp : }} O(N^2)\ \color{purple}{\text{thời gian}}\ ||\ O(N^2)\ \color{purple}{\text{bộ nhớ}}}}\)
C++
#include <iostream>
#include <vector>
using namespace std;
const int LIM = 1000;
const int UPPER = 1100;
int rep[LIM + 1];
int dig[LIM + 1];
void sieve()
{
for (int i = 1; i <= LIM; ++i) rep[i] = dig[i] = 999999;
for (int v = 10; v <= LIM; v += 10) rep[v] = dig[v] = 0;
for (int v = 16; v <= LIM; v += 16) rep[v] = dig[v] = 0;
for (int v = 25; v <= LIM; v += 25) rep[v] = dig[v] = 0;
for (int r = 1; r <= UPPER; ++r)
{
for (int v = 1; v <= LIM; v += 2)
{
int m = 0;
for (int d = 1; d <= r; ++d)
m = (10 * m + 1) % v;
if (m != 0) continue;
for (int d = 1; d <= 9; ++d)
{
int t = d * v;
if (t > LIM) break;
if (rep[t] < r) continue;
if (dig[t] < d) continue;
rep[t] = r;
dig[t] = d;
}
}
}
}
void make_accepted_code_by_string()
{
sieve();
cout << "#include <iostream>\n";
cout << "\n";
cout << "using namespace std;\n";
cout << "\n";
cout << "string res[" << LIM + 1 << "] = {\n";
for (int v = 0; v <= LIM; ++v)
{
cout << " \"";
if (rep[v] == 0)
{
cout << -1;
}
else
{
int p = 0;
bool ok = false;
for(int j = 0; j < rep[v]; ++j)
{
p = 10 * p + dig[v];
if (p >= v) ok = true;
if (ok)
{
cout << p / v;
p %= v;
}
}
}
cout << "\"";
if (v != LIM) cout << ",";
cout << "\n";
}
cout << "};\n";
cout << "\n";
cout << "int main()\n";
cout << "{\n";
cout << " int n;\n";
cout << " cin >> n;\n";
cout << " cout << res[n];\n";
cout << " return 0;\n";
cout << "}\n";
}
void make_accepted_code_by_num()
{
sieve();
cout << "#include <iostream>\n";
cout << "\n";
cout << "using namespace std;\n";
cout << "\n";
cout << "int rep[" << LIM + 1 << "] = {\n";
for (int v = 0; v <= LIM; ++v)
{
cout << rep[v];
if (v < LIM) cout << ", ";
}
cout << "\n";
cout << "};\n";
cout << "\n";
cout << "int dig[" << LIM + 1 << "] = {\n";
for (int v = 0; v <= LIM; ++v)
{
cout << dig[v];
if (v < LIM) cout << ", ";
}
cout << "\n";
cout << "};\n";
cout << "\n";
cout << "int main()\n";
cout << "{\n";
cout << " int n;\n";
cout << " cin >> n;\n";
cout << "\n";
cout << " if (rep[n] == 0)\n";
cout << " {\n";
cout << " cout << -1;\n";
cout << " }\n";
cout << " else\n";
cout << " {\n";
cout << " int p = 0;\n";
cout << " bool ok = false;\n";
cout << " for(int j = 0; j < rep[n]; ++j)\n";
cout << " {\n";
cout << " p = 10 * p + dig[n];\n";
cout << " if (p >= n) ok = true;\n";
cout << " if (ok)\n";
cout << " {\n";
cout << " cout << p / n;\n";
cout << " p %= n;\n";
cout << " }\n";
cout << " }\n";
cout << " }\n";
cout << "\n";
cout << " return 0;\n";
cout << "}\n";
}
int main()
{
make_accepted_code_by_num();
return 0;
}
\(\color{green}{\text{Code tham khảo }}\): Tiền xử lí, Toán học
\(^{^{\color{purple}{\text{Độ phức tạp : }} O(N)\ \color{purple}{\text{thời gian}}\ ||\ O(N)\ \color{purple}{\text{bộ nhớ}}}}\)
C++
#include <iostream>
using namespace std;
int rep[1001] = {
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 3, 6, 6, 3, 0, 16, 3, 18, 0, 3, 2, 22, 3, 0, 6, 3, 6, 28, 0, 15, 0, 2, 16, 6, 9, 3, 18, 6, 0, 5, 6, 21, 2, 9, 22, 46, 0, 6, 0, 16, 6, 13, 9, 2, 6, 18, 28, 58, 0, 60, 15, 6, 0, 6, 2, 33, 16, 22, 0, 35, 9, 8, 3, 0, 18, 2, 6, 13, 0, 9, 5, 41, 6, 16, 21, 28, 2, 44, 0, 6, 22, 15, 46, 18, 0, 96, 42, 2, 0, 4, 16, 34, 6, 6, 13, 53, 27, 108, 0, 3, 0, 112, 18, 22, 28, 6, 58, 16, 0, 22, 60, 5, 15, 0, 6, 42, 0, 21, 0, 130, 6, 18, 33, 27, 16, 8, 22, 46, 0, 46, 35, 6, 0, 28, 8, 6, 3, 148, 0, 75, 18, 16, 6, 15, 6, 78, 13, 13, 0, 22, 27, 81, 5, 6, 41, 166, 6, 78, 0, 18, 21, 43, 28, 0, 0, 58, 44, 178, 0, 180, 6, 60, 22, 3, 15, 16, 46, 6, 0, 95, 0, 192, 96, 6, 42, 98, 6, 99, 0, 33, 4, 28, 48, 5, 34, 22, 0, 18, 0, 30, 13, 35, 53, 21, 27, 15, 108, 8, 0, 48, 3, 222, 0, 0, 112, 113, 18, 228, 0, 6, 28, 232, 6, 46, 58, 13, 48, 7, 0, 30, 22, 27, 60, 42, 5, 18, 15, 41, 0, 50, 18, 22, 42, 48, 0, 256, 21, 3, 0, 28, 130, 262, 6, 13, 18, 44, 33, 268, 0, 5, 0, 6, 8, 0, 66, 69, 46, 15, 0, 28, 46, 141, 35, 18, 6, 5, 0, 272, 0, 96, 8, 146, 42, 58, 3, 6, 148, 66, 0, 21, 75, 4, 0, 60, 48, 153, 6, 34, 0, 155, 6, 312, 78, 18, 13, 79, 13, 28, 0, 53, 66, 144, 81, 0, 81, 108, 5, 46, 0, 110, 41, 3, 166, 33, 0, 336, 78, 112, 0, 30, 18, 42, 21, 66, 43, 173, 84, 116, 0, 6, 0, 32, 58, 35, 44, 48, 178, 179, 0, 342, 180, 22, 6, 8, 60, 366, 0, 5, 0, 13, 15, 186, 16, 0, 46, 84, 18, 378, 0, 42, 95, 382, 0, 6, 192, 21, 96, 388, 0, 176, 42, 130, 98, 13, 18, 99, 99, 18, 0, 200, 33, 30, 4, 81, 84, 6, 48, 204, 0, 8, 34, 58, 66, 41, 0, 46, 18, 418, 0, 140, 30, 46, 13, 0, 35, 60, 53, 6, 0, 215, 0, 432, 30, 84, 108, 198, 8, 219, 0, 18, 48, 221, 3, 44, 222, 148, 0, 32, 0, 10, 112, 75, 113, 6, 18, 152, 228, 48, 0, 460, 6, 154, 0, 15, 232, 233, 18, 33, 0, 78, 58, 42, 13, 0, 48, 13, 7, 239, 0, 6, 30, 66, 22, 96, 81, 486, 60, 81, 0, 490, 15, 112, 18, 18, 0, 35, 41, 498, 0, 166, 50, 502, 18, 4, 22, 78, 42, 508, 0, 8, 0, 18, 256, 34, 21, 46, 6, 43, 0, 52, 84, 261, 130, 0, 262, 240, 0, 506, 0, 58, 18, 30, 44, 53, 33, 178, 268, 6, 0, 540, 5, 180, 0, 108, 6, 91, 8, 60, 0, 252, 66, 13, 69, 3, 46, 278, 15, 42, 0, 16, 28, 281, 138, 112, 141, 18, 35, 284, 0, 570, 6, 95, 30, 0, 0, 576, 272, 192, 0, 41, 96, 26, 8, 18, 146, 293, 42, 90, 0, 98, 0, 592, 18, 48, 148, 99, 66, 299, 0, 300, 42, 33, 75, 22, 4, 202, 0, 84, 0, 138, 144, 51, 153, 15, 6, 88, 34, 618, 0, 66, 155, 44, 0, 0, 312, 18, 78, 48, 0, 315, 13, 30, 79, 42, 39, 6, 28, 35, 0, 32, 53, 107, 66, 21, 144, 646, 81, 58, 0, 15, 81, 326, 108, 130, 0, 8, 138, 658, 0, 220, 110, 48, 41, 18, 3, 308, 166, 222, 0, 60, 0, 224, 336, 0, 78, 338, 112, 96, 0, 113, 30, 341, 18, 8, 294, 228, 0, 78, 0, 230, 43, 6, 173, 46, 84, 80, 116, 232, 0, 700, 18, 18, 0, 138, 32, 4, 174, 708, 0, 13, 44, 330, 48, 6, 178, 7, 179, 359, 0, 34, 342, 30, 180, 0, 22, 726, 6, 81, 0, 336, 60, 61, 366, 42, 0, 66, 15, 246, 0, 18, 78, 742, 15, 148, 186, 41, 16, 53, 0, 125, 0, 50, 84, 75, 54, 27, 378, 22, 0, 380, 42, 108, 95, 144, 382, 174, 0, 192, 0, 256, 192, 193, 21, 0, 96, 3, 388, 90, 0, 70, 176, 84, 0, 78, 130, 393, 98, 262, 0, 112, 18, 60, 99, 39, 99, 199, 18, 368, 0, 44, 200, 8, 33, 66, 30, 268, 4, 202, 0, 810, 84, 5, 6, 81, 0, 126, 204, 6, 0, 820, 8, 822, 34, 0, 174, 413, 198, 276, 0, 69, 0, 48, 46, 166, 18, 15, 418, 419, 0, 812, 140, 28, 30, 78, 138, 22, 0, 141, 0, 66, 105, 213, 60, 18, 53, 856, 6, 26, 0, 15, 215, 862, 0, 43, 432, 272, 30, 26, 0, 66, 108, 96, 198, 0, 24, 438, 219, 146, 0, 440, 42, 441, 48, 174, 221, 886, 3, 42, 0, 18, 222, 414, 148, 178, 0, 66, 32, 420, 0, 208, 10, 21, 112, 180, 75, 151, 113, 4, 0, 455, 0, 82, 152, 60, 228, 130, 144, 459, 0, 153, 460, 210, 6, 0, 154, 34, 0, 464, 0, 18, 232, 155, 233, 16, 18, 936, 66, 312, 0, 940, 78, 110, 0, 54, 42, 473, 39, 24, 0, 79, 48, 952, 39, 95, 7, 28, 239, 8, 0, 465, 6, 53, 30, 192, 66, 322, 22, 144, 0, 970, 243, 46, 486, 0, 0, 976, 81, 44, 0, 108, 490, 982, 15, 98, 112, 138, 18, 462, 0, 495, 0, 110, 210, 99, 123, 166, 498, 3, 0
};
int dig[1001] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 4, 1, 2, 5, 0, 1, 6, 1, 0, 7, 2, 1, 8, 0, 2, 9, 4, 1, 0, 1, 0, 3, 2, 5, 4, 1, 2, 1, 0, 1, 2, 1, 4, 5, 2, 1, 0, 7, 0, 3, 4, 1, 6, 5, 8, 1, 2, 1, 0, 1, 2, 3, 0, 5, 6, 1, 4, 3, 0, 1, 8, 1, 2, 0, 4, 7, 2, 1, 0, 9, 2, 1, 4, 5, 2, 3, 8, 1, 0, 1, 4, 1, 2, 5, 0, 1, 2, 9, 0, 1, 6, 1, 8, 5, 2, 1, 4, 1, 0, 1, 0, 1, 2, 5, 4, 3, 2, 7, 0, 1, 2, 3, 4, 0, 6, 1, 0, 1, 0, 1, 4, 1, 2, 5, 8, 1, 6, 1, 0, 3, 2, 1, 0, 5, 2, 7, 4, 1, 0, 1, 8, 9, 2, 5, 4, 1, 2, 3, 0, 7, 6, 1, 4, 5, 2, 1, 8, 1, 0, 1, 4, 1, 6, 0, 0, 3, 2, 1, 0, 1, 2, 1, 8, 5, 2, 1, 4, 9, 0, 1, 0, 1, 2, 5, 4, 1, 6, 1, 0, 1, 2, 7, 4, 5, 2, 9, 0, 1, 0, 1, 4, 3, 2, 5, 8, 7, 2, 3, 0, 1, 2, 1, 0, 0, 2, 1, 4, 1, 0, 1, 8, 1, 6, 5, 4, 3, 2, 1, 0, 1, 2, 9, 4, 5, 6, 1, 8, 3, 0, 1, 4, 1, 2, 5, 0, 1, 2, 7, 0, 9, 2, 1, 8, 5, 2, 3, 4, 1, 0, 1, 0, 1, 2, 0, 4, 1, 2, 3, 0, 1, 6, 1, 4, 5, 2, 7, 0, 1, 0, 1, 4, 1, 2, 5, 8, 9, 2, 1, 0, 7, 2, 3, 0, 5, 6, 1, 4, 3, 0, 1, 8, 1, 2, 5, 4, 1, 6, 1, 0, 3, 2, 1, 4, 0, 2, 1, 8, 7, 0, 1, 4, 3, 2, 5, 0, 1, 2, 3, 0, 1, 2, 7, 8, 5, 2, 1, 4, 1, 0, 9, 0, 1, 6, 5, 4, 1, 2, 1, 0, 1, 2, 3, 4, 5, 2, 1, 0, 9, 0, 7, 4, 1, 2, 0, 8, 1, 6, 1, 0, 1, 2, 1, 0, 5, 2, 3, 4, 1, 0, 1, 8, 3, 2, 5, 4, 1, 2, 1, 0, 1, 2, 1, 4, 5, 2, 1, 8, 1, 0, 3, 4, 7, 6, 5, 0, 3, 2, 1, 0, 1, 2, 9, 8, 0, 6, 1, 4, 1, 0, 1, 0, 1, 2, 5, 4, 1, 6, 1, 0, 7, 2, 1, 4, 5, 2, 3, 0, 1, 0, 1, 4, 1, 2, 5, 8, 1, 2, 9, 0, 1, 2, 1, 0, 5, 2, 1, 4, 7, 0, 1, 8, 1, 6, 0, 4, 9, 2, 1, 0, 1, 2, 1, 4, 5, 6, 1, 8, 1, 0, 1, 4, 1, 2, 5, 0, 7, 6, 1, 0, 3, 2, 1, 8, 5, 2, 1, 4, 1, 0, 7, 0, 3, 2, 5, 4, 1, 2, 3, 0, 1, 6, 1, 4, 0, 2, 1, 0, 1, 0, 9, 4, 1, 6, 5, 8, 3, 2, 7, 0, 1, 2, 1, 0, 5, 2, 1, 4, 3, 0, 1, 8, 7, 2, 5, 4, 1, 6, 1, 0, 3, 2, 1, 4, 5, 2, 9, 8, 1, 0, 1, 4, 3, 2, 0, 0, 1, 2, 1, 0, 7, 2, 1, 8, 5, 2, 1, 4, 1, 0, 3, 0, 1, 6, 5, 4, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6, 1, 0, 1, 0, 1, 4, 1, 2, 5, 8, 1, 6, 1, 0, 9, 2, 7, 0, 0, 2, 1, 4, 1, 0, 1, 8, 1, 2, 5, 4, 7, 2, 9, 0, 1, 6, 1, 4, 5, 2, 1, 8, 1, 0, 7, 4, 1, 2, 5, 0, 9, 2, 1, 0, 1, 2, 1, 8, 5, 6, 1, 4, 1, 0, 1, 0, 1, 2, 0, 4, 1, 6, 1, 0, 3, 2, 1, 4, 5, 2, 1, 0, 1, 0, 1, 4, 3, 2, 5, 8, 1, 2, 3, 0, 1, 6, 1, 0, 5, 2, 7, 4, 1, 0, 9, 8, 1, 2, 5, 4, 3, 2, 1, 0, 7, 2, 1, 4, 0, 6, 1, 8, 9, 0, 1, 4, 1, 2, 5, 0, 1, 6, 1, 0, 1, 2, 1, 8, 5, 2, 9, 4, 7, 0, 1, 0, 3, 2, 5, 4, 1, 2, 3, 0, 1, 2, 1, 4, 5, 2, 1, 0, 1, 0, 3, 4, 1, 6, 0, 8, 7, 2, 1, 0, 1, 2, 9, 0, 5, 6, 1, 4, 3, 0, 7, 8, 1, 2, 5, 4, 1, 2, 1, 0, 9, 2, 1, 4, 5, 2, 3, 8, 1, 0, 1, 4, 3, 2, 5, 0, 1, 2, 3, 0, 1, 6, 1, 8, 0, 2, 1, 4, 1, 0, 1, 0, 7, 6, 5, 4, 9, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 0, 1, 4, 1, 2, 5, 8, 1, 2, 1, 0, 7, 2, 1, 0, 5, 2, 3, 4, 1, 0, 1, 8, 3, 2, 0, 4, 1, 2, 3, 0, 1, 6, 1, 4, 5, 2, 1, 8, 1, 0, 9, 4, 1, 6, 5, 0, 1, 2, 1, 0, 1, 2, 7, 8, 5, 2, 1, 4, 9, 0, 1, 0, 1, 2, 5, 4, 7, 6, 1, 0, 1, 2, 1, 4, 0, 2, 9, 0, 1, 0, 7, 4, 3, 2, 5, 8, 1, 2, 1, 0, 1, 2, 1, 0, 5, 2, 1, 4, 1, 0, 3, 8, 1, 6, 5, 4, 3, 2, 7, 0, 1, 2, 9, 4, 5, 2, 1, 8, 1, 0, 1, 4, 7, 2, 0, 0, 1, 2, 1, 0, 1, 2, 1, 8, 5, 2, 1, 4, 1, 0, 1, 0, 3, 2, 5, 4, 1, 2, 9, 0
};
int main()
{
int n;
cin >> n;
if (rep[n] == 0)
{
cout << -1;
}
else
{
int p = 0;
bool ok = false;
for(int j = 0; j < rep[n]; ++j)
{
p = 10 * p + dig[n];
if (p >= n) ok = true;
if (ok)
{
cout << p / n;
p %= n;
}
}
}
return 0;
}
Bình luận