🔗 Bài toán kinh điển: ONEZERO - Ones and zeros
I. Tóm tắt đề bài
Cho một số nguyên dương . Hãy tìm số nguyên dương nhỏ nhất thỏa mãn đồng thời hai điều kiện:
là bội số của (nghĩa là chia hết cho ).
Trong hệ thập phân, chỉ gồm các chữ số 0 và 1 (và phải bắt đầu bằng chữ số 1).
Input:
Dòng đầu tiên là số lượng bộ test ().
dòng tiếp theo, mỗi dòng chứa một số nguyên ().
Output:
Với mỗi số , in ra trên một dòng số nhỏ nhất tương ứng tìm được.
Ví dụ:
Nếu , số nhỏ nhất gồm 0 và 1 chia hết cho 3 là 111.
Nếu , số nhỏ nhất là 1001.
Nếu , số nhỏ nhất là 11101.
II. Tại sao lại dùng BFS?
Bài toán yêu cầu tìm số nhỏ nhất thỏa mãn điều kiện.
Thuật toán BFS duyệt các trạng thái theo từng “lớp” (từ ngắn đến dài). Do đó, khi ta sinh ra các số chỉ gồm 0 và 1 theo thứ tự: …
Số đầu tiên trong quá trình sinh này chia hết cho chắc chắn sẽ là số có giá trị nhỏ nhất.
III. Vấn đề
Các số sinh ra chỉ gồm ‘0’ và ‘1’ có thể dài đến hàng trăm chữ số, vượt qua giới hạn của mọi kiểu dữ liệu số nguyên thông thường nên ta bắt buộc phải dùng string.
Tuy nhiên, nếu chỉ đơn thuần sinh ra các string chỉ chứa kí tự (sử dụng Queue hoặc quay lui) thì độ phức tạp có thể lên đến với k là độ dài xâu. Với , số chữ số có thể lên tới hàng chục, hàng trăm, khiến là một con số không thể tính toán nổi.
IV. Tính chất của đồng dư thức
Toán học đồng dư có một tính chất cực kỳ lợi hại:
Giả sử ta có một số , và ta biết số dư của khi chia cho là .
Khi ta thêm chữ số vào sau số , số mới tạo thành sẽ là .
Số dư của số mới này khi chia cho hoàn toàn có thể được tính dựa trên :
V. Tối ưu sử dụng mảng đánh dấu (pruning)
Vì ta chia lấy dư cho , nên chỉ có tối đa trạng thái số dư (từ 0 đến ).
Giả sử trong quá trình BFS, ta tạo ra hai chuỗi “101” và “1100” và chúng có cùng một số dư khi chia cho . Ta chỉ cần giữ lại chuỗi sinh ra trước (chuỗi ngắn hơn), và bỏ qua chuỗi sinh sau. Vì nếu cả hai cùng đi tiếp một chặng đường giống hệt nhau để đến số dư 0, thì chuỗi ngắn hơn chắc chắn sẽ tạo ra kết quả nhỏ hơn.
Bằng việc sử dụng visited[], ta giới hạn số lượng trạng thái trong Queue tối đa là .
Độ phức tạp thời gian giảm xuống chỉ còn thay vì .
VI. Mã giải
const int limN = 20000 + 5;
int visited[limN];
int trace[limN];
int digit[limN];
int session = 0; // trick tối ưu bộ nhớ thay vì cứ phải memset mỗi testcase
void solve() {
session++;
int n; cin >> n;
queue<int> qu;
int start_r = 1 % n;
if(start_r == 0) return cout << 1 << nl, void();
visited[start_r] = session;
trace[start_r] = -1; // ko có cha
digit[start_r] = 1;
qu.push(start_r);
while(!qu.empty()) {
int r = qu.front(); qu.pop();
if(r == 0) break; // tìm thấy số nhỏ nhất chia hết cho n
for(const int &k: {0, 1}) {
int nr = (r * 10 + k) % n;
if(visited[nr] != session) {
visited[nr] = session;
trace[nr] = r;
digit[nr] = k;
qu.push(nr);
}
}
}
int last = 0;
string res;
while(last != -1) {
res.pb(char('0' + digit[last]));
last = trace[last];
}
reverse(all(res));
cout << res << nl;
}