首页 > ACM题库 > HDU-杭电 > HDU 1654 Roman Numerals-DFS-[解题报告] C++
2013
12-21

HDU 1654 Roman Numerals-DFS-[解题报告] C++

Roman Numerals

问题描述 :

The original system of writing numbers used by the early Romans was simple but cumbersome. Various letters were used to represent important numbers, and these were then strung together to represent other numbers with the values decreasing monotonically from left to right. The letters they used and the numbers that were represented are given in the following table.
I 1        V 5 
X 10        L 50 
C 100        D 500 
M 1000          
Thus 1993 was written as MDCCCCLXXXXIII. This system was then superseded by a partially place-oriented system, whereby if the above rule of decreasing values was broken, it meant that the immediately preceding (lower) value was deemed to be `negative’ and was subtracted from the higher (out of place) value. In this system 1993 was usually written as MCMXCIII. There is still some controversy as to which letters could precede which other letters, but for the purposes of this problem we will assume the following restrictions:

1.
A letter from the left column can never appear more than three times in a row, and there can never be more than one other occurrence of that letter.

2.
A letter from the right column can never appear more than once.

3.
Once a letter has been used in a `negative’ position, all subsequent characters (apart from the one immediately following) may not be greater than that character.
Thus we could write MXMIII for 1993 or CCXCIV for 294, however we could not write ILV for 54, nor could we write LIL for 99. Note that 299 could be written as CCXCIX or CCIC

Given a Roman sum, we can either interpret it as such or as an encoding of an Arabic sum. Thus V+V=X could be interpreted as an ambiguous encoding of an Arabic sum with V {1, 2, 3, 4} and X = 2 * V. Similarly, X+X=XX could be interpreted as a correct Roman sum but an impossible Arabic encoding (apart from the trivial encoding X = 0) and XX+XX=MXC as an incorrect Roman sum, but a valid encoding with M = 1, X = 9, and C = 8.

Write a program that will read in sums in Roman numerals and determine whether or not they are correct as Roman sums and also whether they are impossible, ambiguous or valid as Arabic encodings. Assume that zero will never appear on its own or as a leading digit, and that no two Roman numerals map onto the same Arabic digit.

输入:

Input will consist of a series of lines, each line consisting of an apparent Roman sum, i.e. a valid Roman number, a plus sign (+), another valid Roman number, an equal sign (=) and another valid Roman number. No Roman number will contain more than 9 letters. The file will be terminated by a line consisting of a single #.

输出:

Output will consist of a series of lines, one for each line of the input, and each containing two words. The first word will be one of (Correct, Incorrect) depending on whether the Roman sum is or is not correct. The second word will be separated from the first by exactly one space and will be one of the set (impossible, ambiguous, valid) depending on the Arabic sum.

样例输入:

V+V=X
X+X=XX
XX+XX=MXC
#

样例输出:

Correct ambiguous
Correct impossible
Incorrect valid

UVA_185

    第一部分就不详细说了,把字符串翻译成整数即可,关键在于第二部分,这个就像小的时候玩的填数字的数学题。

    首先,我们不妨分析一下题目的特征,并试图找尽量多的回溯的条件。

    显然我们应该从个位加和算起,这样既符合我们的运算习惯,也方便我们对表达式求值。我们不妨设对竖式的每一列的分析都是x+y+s=z的形式,其中s为前一位进上来的余数,那么我们当然选择去枚举x和y的值,这样z就自然确定了,如果枚举z的值话就显得麻烦多了。

    在枚举x和y的时候都会遇到三种情况,第一种情况是这个字符在前面的运算中已被赋了一个值了,第二种情况是这个字符还没有被赋过值,第三种情况就是不存在这一位(说道这里,我们预处理的时候可以保证表示和的这个字符串是最长的,否则是无解的)。如果已被赋值,自然只能取那个值,对于不存在这一位的情况同已被赋值类似,看作是0就可以了。如果没有被赋值,那么我们就要挑和之前的不重复的值赋给这个字符。

    在判断z的这一步会提供几个回溯的条件。同上面分析x、y一样,我们也需要把z分为已确定和未确定两种状态来分析。如果z已经确定,那么我们就要看x+y+s的个位是否和z的值相等,如果不等就不用继续搜了,否则就继续向下深搜。如果z未确定,那么我们就要看x+y+s的个位这个值是否已被赋给其他字符,如果已经赋给别的字符了,那么就不用继续搜了,如果没有赋给其他字符,就把这个值赋给z这个字符,然后继续向下深搜。

    在所有的字符都被赋值完成之后,我们还要判断一下,剩余的余数是否为0,以及有没有某个字符串最高位是0的情况,如果都满足题意就把计数的cnt自加1。如果此后cnt变为了2,那么就必然有多解,同时我们也没有必要去找更多的解了,直接不断return把所有dfs结束即可。

#include<stdio.h>
#include<string.h>
char str[50], a[15], b[15], c[15];
int A, B, C, v[128], num[128], cnt, vis[15][128], hash[15];
void init()
{
    int i, j, k, x, y, z;
    A = strchr(str, '+') - str;
    B = strchr(str, '=') - strchr(str, '+') - 1;
    C = strlen(str) - (strchr(str, '=') - str) - 1;
    x = y = z = 0;
    for(i = 0, j = A - 1; str[i] != '+'; i ++, j --)
    {
        a[j] = str[i];
        if(str[i + 1] != '+' && v[str[i + 1]] > v[str[i]])
            x -= v[str[i]];
        else
            x += v[str[i]];
    }
    for(++ i, j = B - 1; str[i] != '='; i ++, j --)
    {
        b[j] = str[i];
        if(str[i + 1] != '=' && v[str[i + 1]] > v[str[i]])
            y -= v[str[i]];
        else
            y += v[str[i]];
    }
    for(++ i, j = C - 1; str[i]; i ++, j --)
    {
        c[j] = str[i];
        if(str[i + 1] && v[str[i + 1]] > v[str[i]])
            z -= v[str[i]];
        else
            z += v[str[i]];
    }
    if(x + y == z)
        printf("Correct ");
    else
        printf("Incorrect ");
}
int dfs(int cur, int s)
{
    int i, j, k, x, y, z, unx, uny, unz;
    if(cur == C)
    {
        if(s == 0 && num[a[A - 1]] != 0 && num[b[B - 1]] != 0 && num[c[C - 1]] != 0)
        {
            ++ cnt;
            if(cnt >= 2)
                return 1;
        }
        return 0;
    }
    z = 0;
    unx = 1;
    if(cur >= A)
    {
        x = 0;
        unx = 0;
    }
    else if(num[a[cur]] != -1)
    {
        x = num[a[cur]];
        unx = 0;
    }
    for(i = (unx ? 0 : 9); i < 10; i ++)
    {
        if(unx && hash[i])
            continue;
        if(unx)
        {
            hash[i] = 1;
            x = num[a[cur]] = i;
        }
        uny = 1;
        if(cur >= B)
        {
            y = 0;
            uny = 0;
        }
        else if(num[b[cur]] != -1)
        {
            y = num[b[cur]];
            uny = 0;
        }
        for(j = (uny ? 0 : 9); j < 10; j ++)
        {
            if(uny && hash[j])
                continue;
            if(uny)
            {
                hash[j] = 1;
                y = num[b[cur]] = j;
            }
            unz = 1;
            if(num[c[cur]] != -1)
                unz = 0;
            z = (x + y + s) % 10;
            k = (x + y + s) / 10;
            if(unz)
            {
                if(!hash[z])
                {
                    hash[z] = 1;
                    num[c[cur]] = z;
                    if(dfs(cur + 1, k))
                        return 1;
                    hash[z] = 0;
                    num[c[cur]] = -1;
                }
            }
            else
            {
                if(z == num[c[cur]])
                {
                    if(dfs(cur + 1, k))
                        return 1;
                }
            }
            if(uny)
            {
                hash[j] = 0;
                num[b[cur]] = -1;
            }
        }
        if(unx)
        {
            hash[i] = 0;
            num[a[cur]] = -1;
        }
    }
    return 0;
}
void solve()
{
    int i, j, k;
    if(A > C || B > C)
    {
        printf("impossible\n");
        return ;
    }
    memset(num, -1, sizeof(num));
    memset(hash, 0, sizeof(hash));
    cnt = 0;
    dfs(0, 0);
    if(cnt == 0)
        printf("impossible\n");
    else if(cnt == 1)
        printf("valid\n");
    else
        printf("ambiguous\n");
}
int main()
{
    v['I'] = 1, v['X'] = 10, v['C'] = 100, v['M'] = 1000;
    v['V'] = 5, v['L'] = 50, v['D'] = 500;
    for(;;)
    {
        gets(str);
        if(str[0] == '#')
            break;
        init();
        solve();
    }
    return 0;
}



解题报告转自:http://www.cnblogs.com/staginner/archive/2011/12/21/2296222.html