AOJ 0220 Binary Digit A Doctor Loved

方針

深さ優先探索です．全探索なので頭悪い解法かなと思いながらもたかだかO(2^12)っぽいので余裕だろーとか思いながらやりました．

コード

double n;
double x[12];

int tmp[12];
int ans[12];

void dfs(int p, double sum)
{
    if(sum > n || p > 12)
        return;

    if(n == sum)
    {
        memcpy(ans, tmp, sizeof tmp);
        return;
    }

    tmp[p] = 1;
    dfs(p + 1, sum + x[p]);
    tmp[p] = 0;
    dfs(p + 1, sum);

    return;
}

int main()
{
    for(double i = 0, a = 1 << 7; i < 12; i++, a /= 2)
        x[static_cast<int>(i)] = a;

    while(cin >> n, n >= 0)
    {
        bool f = true;
        fill(ans, ans + 12, -1);
        dfs(0, 0);

        for(int i = 0; i < 12; i++)
            if(ans[i] < 0)
            {
                puts("NA");
                f = false;
                break;
            }

        if(f)
            for(int i = 0; i < 12; i++)
                cout << ans[i] << (i == 7 ? "." : "") << (i == 11 ? "\n" : "");
    }
}