SPOJ.COM - Thuật toán bài ONEZERO - Ones and zeros

Posted on September 25th, 2016

Đề 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

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à 10*x và 10*x + 1. Khi đó, đảm bảo rằng các số sẽ chỉ toàn 0 và 1.

Lời giải

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 mình 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 mình 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 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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Spoj
BFS, Graph and Tree