SPOJ.COM – Thuật toán bài ONEZERO – Ones and zeros
Đề bài:
Ta cần tìm 1 số dương mà dạng biểu diễn của nó trong hệ thập phân bao gồm chỉ toàn số 0, 1 và có ít nhất một số 1, ví dụ: 101. Nếu một số mà không có dạng như vậy thì ta có thể nhân nó với một vài số nguyên dương khác để được một số như vậy.
Đầu vào:
Cho một số K là số lượng test case (K cỡ 1000), mỗi test case bao gồm K dòng. Mỗi dòng là một số nguyên n, 1 <= n <= 20000.
Đầu ra:
Với mỗi một test case, tìm số nguyên dương nhỏ nhất là bội số của n thoả mãn là nó chỉ bao gồm toàn số 0, 1 và bắt đầu bằng số 1.
Ví dụ:
Đầu vào:
3
17
11011
17
Đầu ra:
11101
11011
11101
Các bạn có thể tham khảo đề bài tiếng anh và submit code tại: http://www.spoj.com/problems/ONEZERO/
Phân tích:
- Nếu đầu vào là 1 thì suy ra luôn đầu ra là 1 + Ở bài toán này ta sẽ dùng thuật toán tìm kiếm theo chiều rộng - BFS. Với trạng thái đầu tiên là số 1. + Với chú ý là: Nếu trạng thái hiện tại là số x, thì 2 trạng thái kề với nó là 10x và 10x + 1. Khi đó, đảm bảo rằng các số sẽ chỉ toàn 0 và 1.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include <iostream> | |
| using namespace std; | |
| const int MAX = 20005; | |
| int N, Exist[MAX], Parent[MAX]; | |
| int current, expanding, remainder, len; | |
| char Digit[MAX], Temp[MAX]; | |
| int queue[MAX]; | |
| int fr, re, leng; | |
| void Enqueue(int remainder) | |
| { | |
| queue[re] = remainder; | |
| re = (re + 1) % MAX; | |
| leng++; | |
| } | |
| int Dequeue() | |
| { | |
| int c = queue[fr]; | |
| fr = (fr + 1) % MAX; | |
| leng--; | |
| return c; | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); | |
| // Comment trước khi submit | |
| freopen("input.txt","r",stdin); | |
| int K; | |
| cin >> K; | |
| for(int i = 0; i < K; i++) | |
| { | |
| cin >> N; | |
| for(int i = 0; i < N; i++) | |
| { | |
| Exist[i] = 0; | |
| Parent[i]= 0; | |
| Digit[i] = '0'; | |
| Temp[i] = '0'; | |
| } | |
| // Nếu đầu vào là 1 => số cần tìm cũng là 1 | |
| if(N == 1) | |
| { | |
| cout << 1 << endl; | |
| continue; | |
| } | |
| // Duyệt tất cả các trạng thái | |
| Parent[1] = -1; | |
| Digit[1] = '1'; | |
| Exist[1] = 1; | |
| Enqueue(1); | |
| while(leng > 0) | |
| { | |
| current = Dequeue(); | |
| for(int i = 0; i < 2; i++) | |
| { | |
| // xét trạng thái kề với current | |
| expanding = current * 10 + i; | |
| remainder = expanding % N; | |
| if(Exist[remainder] == 0) | |
| { | |
| Exist[remainder] = 1; | |
| Parent[remainder] = current; | |
| Digit[remainder] = i + '0'; | |
| Enqueue(remainder); | |
| } | |
| } | |
| } | |
| // Truy lại số cần tìm | |
| current = 0; | |
| len = 0; | |
| while(true) | |
| { | |
| Temp[len++] = Digit[current]; | |
| if(Parent[current] == -1) break; | |
| else current = Parent[current]; | |
| } | |
| for(int i = len - 1; i >= 0; i--) | |
| cout << Temp[i]; | |
| cout << endl; | |
| } | |
| return 0; | |
| } |
Code by Phạm Văn Lâm