Test Message

d299: 程式設計師的面試問題

內容

程式設計師的面試到底有多困難？

請推理出以下 10 個字母所代表的數字( 0 ~ 9 )。

重複的字母為相同的阿拉伯數字。

  FORTY

  　TEN

+)  TEN
_______

  SIXTY

請以 XXXXX + XXX + XXX = XXXXX 的格式輸出所有可能(這些 X 就是數字)。

請複製上述格式再將 X 改為數字,避免因為空白的關係而造成 WA 。

輸入

本題沒有輸入

無

輸出

每組輸出為一行，格式為

XXXXX + XXX + XXX = XXXXX

(這些 X 就是數字)

(略)

解題思路

用 dfs 窮舉所有可能，出現答案之後不再進行判斷快速跳出遞迴。

完整程式碼

AC (55ms, 76KB)
#include <stdio.h>

int ans[10], isUse[10];

char dfs(int now, int step)
{
    int i, j;

    if (step == 10)
    {
        if (ans[1] * 10000 + ans[4] * 1000 + ans[5] * 100 + ans[7] * 10 + ans[9]
            + 2 * (ans[7] * 100 + ans[0] * 10 + ans[3])
            == ans[6] * 10000 + ans[2] * 1000 + ans[8] * 100 + ans[7] * 10 + ans[9])
        {
            printf("%d%d%d%d%d + %d%d%d + %d%d%d = %d%d%d%d%d\n",
                ans[1], ans[4], ans[5], ans[7], ans[9],
                ans[7], ans[0], ans[3],
                ans[7], ans[0], ans[3], ans[6], ans[2], ans[8], ans[7], ans[9]);
            return 1;
        }
        return 0;
    }
    for (i = 0; i < 10; i++)
    {
        if (isUse[i]) continue;
        ans[step] = i;
        isUse[i] = 1;
        if (dfs(i, step + 1))
            return 1;
        isUse[i] = 0;
    }
    return 0;
}

int main()
{
    dfs(0, 0);
    return 0;
}