Hướng dẫn cho Số đối xứng lẻ (Contest ôn tập #03 THTA 2023)
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:
Sub 1:
Đệ quy quay lui sinh toàn bộ các số ODD, lưu vào mảng để sắp xếp lại và in ra số thứ \(n\).
Solution
-
Viết hàm
backtrack(x)để xây dựng một bộ số ODD. Tham số \(x\) là phần đã được tạo ra, lần lượt thêm các chữ số \(1, 3, 5, 7, 9\) vào xâu \(x\) và gọi đệ quy. -
Với giới hạn \(n \leq 10^5\), có thể tính được độ dài của số ODD lớn nhất cần xây dựng là \(7\) vì \(5^1*2 + 5^2*2 + 5^3*2 + 5^4*2 + 5^5*2 + 5^6*2 + 5^7*2 = 195310 > 10^5\).
-
Bắt đầu gọi đệ quy với backtrack(xâu rỗng). Thêm tất cả các \(x\) sau khi được ép kiểu sang int vào mảng. Sắp xếp và in ra kết quả.
code
odd = []
def backtrack(x):
if len(x) > 7:
return
if len(x) > 0:
odd.append(int(x + x[::-1]))
odd.append(int(x[:-1] + x[::-1]))
for i in '13579':
backtrack(x + i)
backtrack('')
# print(len(odd))
odd.sort()
n = int(input())
print(odd[n - 1])
Sub 2:
Tính chất các chữ số lẻ:
- Tạm biến đổi các chữ số lẻ sang các số từ \(0\) đến \(4\) như sau: \(1 \to 0\); \(3 \to 1\); \(5 \to 2\); \(7 \to 3\); \(9 \to 4\), và gọi chúng là những số OD
Các số chỉ gồm các chữ số lẻ sau khi biến đổi sẽ có dạng:
1 0
3 1
5 2
7 3
9 4
11 00
13 01
15 02
17 03
19 04
31 10
33 11
35 12
37 13
39 14
51 20
53 21
...
- Như vậy, các số ODD đầu tiên sẽ là:
0, 1, 2, 3, 4; 00, 11, 22, 33, 44; 000, 010, 020, ..., 090, 101, 111, 121, ... 191, 202, ..., 444; 0000, 0110, 0220, ... - Nếu chia thành các nhóm có \(1\) chữ số, \(2\) chữ số, ..., ta sẽ có:
- Nhóm \(1\) gồm \(5\) số có \(1\) chữ số
- Nhóm \(2\) gồm \(5\) số có \(2\) chữ số
- Nhóm \(3\) gồm \(10\) số có \(3\) chữ số
- Nhóm \(4\) gồm \(10\) số có \(4\) chữ số
- ...
- Nhóm \(i\) có \(5^{(i+1)/2}\) số có \(i\) chữ số
Vậy trong một nhóm các số ODD có \(m\) chữ số thì có tính chất gì đặc biệt?
Tính chất đối xứng:
-
Các số đối xứng có \(m\) chữ số được tạo ra bằng cách:
- Tạo ra số ODD có \((m + 1) / 2\) chữ số gọi là số \(x\).
- Gọi số \(y\) là số \(x\) sau khi đảo ngược.
- Nếu \(m\) chẵn thì lấy \(y\) ghép vào sau \(x\).
- Nếu \(m\) lẻ thì bỏ đi một chữ số cuối của \(x\) rồi lấy \(y\) ghép vào sau \(x\).
Ví dụ: - \(m = 6 \to n = 3\). Một trong những số ODD có thể tạo ra là \(x = 031 \to y = 130\). M chẵn nên tạo được số ODD tương ứng là \(031130\), số trên thực tế sẽ là \(173371\).
- \(m = 5 \to n = 3\). Một trong những số ODD có thể tạo ra là \(x = 031 \to y = 130\). M lẻ nên tạo được số ODD tương ứng là \(03130\), số trên thực tế sẽ là \(17371\).
-
Xét trong mỗi nhóm có \(m\) chữ số, đây chính là cách biểu diễn của một hệ cơ số \(5\) (gồm cách chữ số từ \(0\) đến \(4\)) của các số nguyên từ \(0\) đến \(5^m-1\):
Bảng hệ cơ số 5 với m = 3:
0 000
1 001
2 002
3 003
4 004
5 010
6 011
7 012
8 013
9 014
10 020
11 021
12 022
13 023
...
119 434
120 440
121 441
122 442
123 443
124 444
Solution
Thuật toán:
- Duyệt qua các độ dài \(m\) lần lượt từ \(1\):
- Với mỗi độ dài chẵn có \(m\) chữ số, sẽ có \(5^{m/2}\) số ODD được tạo ra. Nếu \(n <= 5^{m/2}\) thì xác định được đáp án có m chữ số. Nếu không \(n -= 5^{m/2}\)
- Với mỗi độ dài lẻ có \(m\) chữ số, sẽ có \(5^{(m+1)/2}\) số ODD được tạo ra. Nếu \(n <= 5^{(m+1)/2}\) thì xác định được đáp án có m chữ số. Nếu không \(n\) giảm đi một lượng \(5^{(m+1)/2}\)
- Kết thúc quá trình, xác định được đáp án sẽ thuộc nhóm nào và thứ tự của đáp án trong nhóm đó.
- Việc còn lại chỉ việc in ra kết quả theo cách tạo ra nó như trên: biễu diễn n-1 dưới dạng ngũ phân (có thể chuyển trược tiếp sang dạng các số lẻ thập phân), ghép thêm nửa còn lại để thành số đối xứng và in ra kết quả trên thực tế ở dạng các chữ số lẻ thập phân.
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n; cin >> n;
int len = 0, x = 5, e = 1, cnt = 0, last = 0;
while (cnt < n) {
last = cnt;
cnt += x;
x *= e;
e ^= 5 ^ 1;
++len;
}
n -= last;
--n;
string dig = "13579";
string s = "";
while (n > 0) {
s = dig[n % 5] + s;
n /= 5;
}
while (s.size() * 2 < len) s = '1' + s;
if (len & 1)
cout << s.substr(0, s.size() - 1);
else
cout << s;
reverse(s.begin(), s.end());
cout << s;
return 0;
}
Bình luận