Số Tình Nghĩa
Đề bài
Số "tình nghĩa" là số thoả mãn các điều kiện sau:
- các chữ số của nó chỉ bao gồm 4 hoặc 7;
- số lượng chữ số $4$ bằng số lượng chữ số $7$.
Ví dụ: $4774$, $477744$ là các ví dụ về số "tình nghĩa".
Yêu cầu: Cho trước số nguyên dương $n$. Hãy in ra số "tình nghĩa" nhỏ nhất mà không nhỏ hơn $n$.
Input
- Dòng thứ nhất chứa số $t$ $(1 \le t \le 100)$ – thể hiện số lượng testcase.
- $t$ dòng tiếp theo, mỗi dòng chứa số nguyên $n$ $(1 \le n \le 10^9)$.
Output
- Ứng với mỗi testcase, in ra đáp án cần tìm.
2
1
7347
74Giải thích: số tình nghĩa nhỏ nhất là $47$ nên với $n = 1$ đáp án là $47$. Với $n = 73$ thì $47 < 73$ không được, số tình nghĩa kế tiếp là $74 \ge 73$ nên đáp án là $74$.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngChỉ có 4 hoặc 7 → dãy nhị phân
Chỉ có 2 lựa chọn: hoặc 4, hoặc 7. Thấy có 2 lựa chọn như vậy thì hiểu ngay ra dãy nhị phân rồi nè. Cho bit 0 là số 4, bit 1 là số 7. Ví dụ dãy nhị phân 0110 thì sẽ là số 4774:
Vì số chữ số 4 phải bằng số chữ số 7 nên độ dài của số tình nghĩa luôn là số chẵn. Vậy ta chỉ sinh dãy nhị phân có các chiều dài chẵn, không cần sinh các dãy nhị phân có chiều dài lẻ làm gì: sinh độ dài $2, 4, 6, 8, 10$. Vì số $n$ tối đa $10^9$ (có 10 chữ số) nên chỉ cần sinh tối đa dãy nhị phân chiều dài $10$ là phủ hết tụi nó rồi (số tình nghĩa độ dài 10 nhỏ nhất là $4444477777 > 10^9$).
Và với từng dãy chỉ lấy những dãy nào có số lượng bit 0 bằng số lượng bit 1. Đếm thử xem có bao nhiêu số như vậy: độ dài $L$ thì chọn $\frac{L}{2}$ vị trí cho bit 0 trong $L$ vị trí, tức là $C_L^{L/2}$ số:
| Độ dài $L$ | Số dãy nhị phân $2^L$ | Số tình nghĩa | Nhỏ nhất | Lớn nhất |
|---|---|---|---|---|
| 2 | 4 | 2 | 47 | 74 |
| 4 | 16 | 6 | 4477 | 7744 |
| 6 | 64 | 20 | 444777 | 777444 |
| 8 | 256 | 70 | 44447777 | 77774444 |
| 10 | 1024 | 252 | 4444477777 | 7777744444 |
| Tổng | 350 | |||
Đó thì cứ tạo ra hết tất cả các số. Và bản chất của các dãy nhị phân khi sinh theo thứ tự từ 00…0 tới 11…1 nó cũng sẽ có tính chất tăng dần (bit 0 ↔ chữ số 4 nhỏ hơn, bit 1 ↔ chữ số 7 lớn hơn, cùng độ dài thì so sánh từ trái qua giống hệt nhau), và độ dài ngắn sinh trước độ dài dài, nên danh sách các số được tạo ra mặc nhiên sẽ có thứ tự tăng dần, ta cũng không cần phải đi sắp xếp. Em sẽ thấy chỉ có 350 số thôi.
Và danh sách các số đã có thứ tự tăng dần thì với mỗi test case em đi tìm kiếm nhị phân ra kết quả số đầu tiên thoả $\ge n$ thôi, gọi hàm lower_bound là xong.
res.2)
res tự động tăng dần (350 số). Mỗi truy vấn $n$: in *lower_bound(res.begin(), res.end(), n).Minh hoạSinh nhị phân ra số tình nghĩa
Em chọn độ dài $L$ (2, 4 hoặc 6) và nhập $n$, rồi bấm Tiếp để xem từng dãy nhị phân được sinh ra, dãy nào cân bằng thì đổi thành số tình nghĩa, cuối cùng tìm số đầu tiên $\ge n$:
Cách 1Sinh nhị phân + lower_bound
Code sinh nhị phân mình tự viết theo cơ chế quen thuộc: từ dãy hiện tại, đi từ cuối dãy ngược về tìm bit 0 đầu tiên, bật nó lên 1 và cho toàn bộ các bit phía sau về 0. Nếu không còn bit 0 nào (dãy toàn 1) thì vòng lặp kết thúc ($i = -1$).
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n = 2;
vector<long long> res;
while(n <= 10){
int a[n] = {0};
int i;
do{
int cnt0 = 0;
for(int i = 0; i < n; ++i){
if(a[i] == 0){
cnt0++;
}
}
if(cnt0 == n - cnt0){
long long sum = 0;
for(int i = 0; i < n; ++i){
sum = sum * 10;
if(a[i] == 0){
sum += 4;
}
else{
sum += 7;
}
}
res.push_back(sum);
}
for(i = n - 1; i >= 0; --i){
if(a[i] == 0){
a[i] = 1;
for(i++; i < n; ++i){
a[i] = 0;
}
break;
}
}
}while(i != -1);
n += 2;
}
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
cout << *lower_bound(res.begin(), res.end(), n) << '\n';
}
return 0;
}from bisect import bisect_left
# Sinh các dãy nhị phân độ dài chẵn 2, 4, ..., 10 theo thứ tự tăng dần
# bit 0 -> chữ số 4, bit 1 -> chữ số 7; chỉ lấy dãy có số bit 0 = số bit 1
res = []
for n in range(2, 11, 2):
for mask in range(1 << n): # mask tăng dần = dãy nhị phân tăng dần
bits = [(mask >> (n - 1 - i)) & 1 for i in range(n)]
if bits.count(0) == n - bits.count(0):
s = 0
for b in bits:
s = s * 10 + (7 if b else 4)
res.append(s)
data = open(0).read().split()
t = int(data[0])
out = []
for k in range(1, t + 1):
n = int(data[k])
out.append(str(res[bisect_left(res, n)])) # giống lower_bound
print("\n".join(out))Giải thích một số chỗ trong code:
int a[n] = {0};tạo dãy nhị phân đầu tiên toàn bit 0 (ứng với số $44\ldots4$).- Vòng
for(i = n - 1; i >= 0; --i)sinh dãy nhị phân kế tiếp. Biếnikhai báo bên ngoàido…whileđể sau vòng lặp còn dùng được: nếu không tìm thấy bit 0 nào thìigiảm tới $-1$ → điều kiệnwhile(i != -1)sai → đã sinh xong độ dài này. - Trong
maincó 2 biến tênn:int nở trên là độ dài dãy nhị phân, cònlong long ntrong vòngwhile(t--)là số $n$ của từng test (biến bên trong che biến bên ngoài). lower_bound(res.begin(), res.end(), n)trả về vị trí phần tử đầu tiên $\ge n$ trong mảng đã tăng dần bằng tìm kiếm nhị phân, dấu*phía trước để lấy giá trị tại vị trí đó.
Đánh giá độ phức tạp: phần sinh chạy cố định $2^2 + 2^4 + \ldots + 2^{10} \approx 1\,364$ dãy, mỗi dãy $O(10)$; mỗi truy vấn $O(\log 350)$.
Code này nộp bài thì time = 0.02 s và memory = 3.1 MB là tốc độ & bộ nhớ tối ưu nhất (tính đến thời điểm mình viết bài này).
Cách 2Sinh hoán vị + set
Hoặc có 1 hướng xử lý khác mà không dùng đến sinh nhị phân, đó là sinh hoán vị. Cũng vẫn như trên ta sẽ sinh ra các dãy hoán vị có độ dài chẵn: $2, 4, 6, 8, 10$. Ví dụ với độ dài 4 thì khởi đầu sẽ là: 1 2 3 4, thì ta hiểu ứng với số lẻ sẽ là số 7, ứng với số chẵn sẽ là số 4. Độ dài chẵn nên số lượng số lẻ luôn bằng số lượng số chẵn → số tạo ra chắc chắn có số chữ số 4 bằng số chữ số 7.
| # | Hoán vị | Số tạo ra | Vào set |
|---|---|---|---|
| 1 | 1 2 3 4 | 7474 | số mới |
| 2 | 1 2 4 3 | 7447 | số mới |
| 3 | 1 3 2 4 | 7744 | số mới |
| 4 | 1 3 4 2 | 7744 | trùng, set bỏ qua |
| 5 | 1 4 2 3 | 7447 | trùng, set bỏ qua |
| 6 | 1 4 3 2 | 7474 | trùng, set bỏ qua |
| 7 | 2 1 3 4 | 4774 | số mới |
| 8 | 2 1 4 3 | 4747 | số mới |
| … tổng cộng $4! = 24$ hoán vị nhưng chỉ có $C_4^2 = 6$ số khác nhau. | |||
Vì có thể bị trùng nên là ta sẽ dùng cấu trúc dữ liệu set để lưu trữ các số được tạo ra và sẽ đảm bảo không bị trùng, và dữ liệu trong set cũng được sắp xếp theo thứ tự tăng dần, từ đó ta tìm kiếm nhị phân luôn bằng se.lower_bound(n).
Với việc sinh nhị phân trước đó thì ta phải tự viết code cơ chế sinh nhị phân, nhưng với việc sinh hoán vị thì C++ đã hỗ trợ sẵn hàm next_permutation sẽ rất tiện lợi nhanh gọn cho ta: nó biến dãy thành hoán vị kế tiếp theo thứ tự từ điển và trả về false khi dãy đã là hoán vị cuối cùng. Vậy áp dụng ý tưởng trên vào thì code sẽ như sau:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n = 2;
set<long long> se;
while(n <= 10){
int a[n + 1];
for(int i = 1; i <= n; ++i){
a[i] = i;
}
do{
long long sum = 0;
for(int i = 1; i <= n; ++i){
sum *= 10;
if(a[i] % 2 != 0){
sum += 7;
}
else{
sum += 4;
}
}
se.insert(sum);
} while (next_permutation(a + 1, a + n + 1));
n += 2;
}
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
cout << *se.lower_bound(n) << '\n';
}
return 0;
}from bisect import bisect_left
from itertools import permutations
# Sinh hoán vị của 1..n (n = 2, 4, ..., 10): số lẻ -> 7, số chẵn -> 4
# Dùng set để bỏ các số trùng, rồi sắp xếp để tìm kiếm nhị phân
se = set()
for n in range(2, 11, 2):
for p in permutations(range(1, n + 1)):
s = 0
for x in p:
s = s * 10 + (7 if x % 2 else 4)
se.add(s)
res = sorted(se)
data = open(0).read().split()
t = int(data[0])
out = []
for k in range(1, t + 1):
n = int(data[k])
out.append(str(res[bisect_left(res, n)]))
print("\n".join(out))Với code này thì time = 0.59 s và memory = 3.2 MB. Time chạy lâu hơn là vì dùng cấu trúc dữ liệu set: bản chất set là cấu trúc cây nên mỗi dữ liệu đưa vào sẽ mất chi phí $O(\log)$ chứ không tối ưu như mảng chỉ là $O(1)$ khi đưa mỗi phần tử vào cuối. Mà ở đây số lần đưa vào set rất nhiều: mỗi hoán vị một lần, độ dài 10 thôi đã là $10! = 3\,628\,800$ lần.
Cách 3Không cần sinh độ dài 10
Một suy nghĩ tối ưu thêm là bài này cho $N$ tối đa là $10^9$, và đề yêu cầu tìm ra số tình nghĩa nhỏ nhất thoả $\ge N$. Vậy ta có cần sinh ra các số tình nghĩa có độ dài 10 không? Vì ta đã biết số tình nghĩa độ dài 8 lớn nhất sẽ là $77774444$, vậy nếu số $N$ mà lớn hơn số này, tức là $N$ từ $77774445$ đến $10^9$, thì đáp án sẽ là số tình nghĩa tiếp theo, là số có độ dài 10 nhỏ nhất: 4444477777.
Vậy lúc này ta chỉ cần sinh các số tình nghĩa có độ dài $2, 4, 6, 8$ thôi và xét thêm điều kiện ràng buộc là được. Ta chỉnh lại code dùng set ở trên như sau:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n = 2;
set<long long> se;
while(n <= 8){
int a[n + 1];
for(int i = 1; i <= n; ++i){
a[i] = i;
}
do{
long long sum = 0;
for(int i = 1; i <= n; ++i){
sum *= 10;
if(a[i] % 2 != 0){
sum += 7;
}
else{
sum += 4;
}
}
se.insert(sum);
} while (next_permutation(a + 1, a + n + 1));
n += 2;
}
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
if(n > 77774444){
cout << 4444477777;
}
else{
cout << *se.lower_bound(n);
}
cout << '\n';
}
return 0;
}from bisect import bisect_left
from itertools import permutations
# Chỉ sinh hoán vị độ dài 2, 4, 6, 8; n > 77774444 thì đáp án là 4444477777
se = set()
for n in range(2, 9, 2):
for p in permutations(range(1, n + 1)):
s = 0
for x in p:
s = s * 10 + (7 if x % 2 else 4)
se.add(s)
res = sorted(se)
data = open(0).read().split()
t = int(data[0])
out = []
for k in range(1, t + 1):
n = int(data[k])
if n > 77774444:
out.append("4444477777")
else:
out.append(str(res[bisect_left(res, n)]))
print("\n".join(out))Và kết quả time chạy giờ đây là 0.02 s, bằng với time chạy nhanh nhất của bài đó. Tại sao chỉ 1 thay đổi nhỏ mà lại rút ngắn time từ 0.59 s xuống còn 0.02 s? Ta hãy hiểu rằng với độ dài $X$ thì sẽ có $X!$ hoán vị. Nên khi ta bỏ qua việc liệt kê ra hết các hoán vị có độ dài 10 nghĩa là ta đã bỏ qua được việc phải xét $10! = 3\,628\,800$ dãy hoán vị. Mà mỗi dãy có độ dài 10 nên tổng số phần tử đã bỏ qua được là $3\,628\,800 \times 10$ $= 36\,288\,000$ (36 triệu 288 ngàn) phần tử. Chỉ 1 thay đổi nhỏ nhưng đã giúp giảm tải rất nhiều phép xử lý cho máy tính, vì thế mới tăng tốc được như vậy.
So sánhSinh nhị phân hay sinh hoán vị?
Vậy nếu so sánh giữa cách làm sinh nhị phân và cách làm sinh hoán vị thì nên làm cách nào hơn? Thì ta hiểu rằng với sinh nhị phân, dãy nhị phân có độ dài $X$ ta sẽ chỉ có $2^X$ dãy thôi, trong khi đó với dãy hoán vị thì là $X!$ dãy. Em xem bảng này là thấy được sự chênh lệch rất lớn:
| Độ dài $X$ | Sinh nhị phân $2^X$ | Sinh hoán vị $X!$ |
|---|---|---|
| 2 | 4 | 2 |
| 4 | 16 | 24 |
| 6 | 64 | 720 |
| 8 | 256 | 40.320 |
| 10 | 1.024 | 3.628.800 |
| 12 | 4.096 | 479.001.600 |
| 22 | 4.194.304 | 1.124.000.727.777.607.680.000 |
Nếu bài này mà nhu cầu cần phải sinh ra độ dài 12 thì với việc sinh nhị phân thì $2^{12} = 4\,096$ vẫn bình thường không vấn đề gì, nhưng nếu sinh hoán vị thì $12! = 479\,001\,600$ (hơn 479 triệu) thì chắc chắn sẽ bị TLE. Nếu giả sử bài này mà số tình nghĩa cần sinh ra có độ dài lên tới 22 chữ số thì cách làm sinh nhị phân cũng vẫn sẽ ổn vì $22 \cdot 2^{22} = 92\,274\,688$ (92 triệu 274 ngàn 688) vẫn dưới ngưỡng 100 triệu của 1 giây, nhưng nếu là sinh hoán vị thì $22! = 1\,124\,000\,727\,777\,607\,680\,000$ thì em nghĩ máy tính chạy nổi không? 😅
next_permutation đã có sẵn gọi vào cho nhanh, thay vì tự code ra cách sinh nhị phân, để còn thời gian làm các bài khác.