uva 185 Roman Numerals

最新推荐文章于 2019-12-20 14:45:51 发布

hackerwin7

最新推荐文章于 2019-12-20 14:45:51 发布

阅读量2.2k

点赞数

分类专栏： ACM_DFS ACM_剪枝文章标签： DFS剪枝 DFS记录栈

本文链接：https://blog.csdn.net/hackerwin7/article/details/16862713

版权

ACM_DFS 同时被 2 个专栏收录

17 篇文章

订阅专栏

ACM_剪枝

12 篇文章

订阅专栏

题目地址：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=121

题目描述：

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:

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.

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

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 $\in$ {1, 2, 3, 4} and X = 2 * V. Similarly, X+X=XXcould 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

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

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.

Sample input

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

Sample output

Correct ambiguous
Correct impossible
Incorrect valid

题意：

给出一个加法式，要你分别用罗马式的规则和阿拉伯式的规则来判断是否可行（罗马式）或 0个情况成立 1个情况成立 2个或以上情况成立（阿拉伯式）

题解：

首先，对于罗马式的判断是否正确，直接将罗马式转换成普通数字形式，然后判断等式是否成立即可。

罗马式的转换规则：当前指针指向的数位i，j是它相邻左边一位的指向指针，j有两种情况：1、若j所指的数位的等级（M>D>C>L>X>V>I）小于i所指的等级那么i的数位减去j的数位，j继续往左移； 2、j所指的数位的等级大于等于i所指的数位等级，那么i就加上j所指的数位等级。重复1、2、步骤直到把罗马数字串走完即可转换为普通数字。

然后，对于阿拉伯数字，实际上可以把问题转换为类似于 abcd+efgh=ijkl（蓝桥杯某道水题。。。） ,然后枚举a~l的数位使等式成立。这样我们直接DFS，以a~l为深度，判断符合等式成立的有几种情况即可。这里需要注意的是：

1、在输入中有形如XX+XX=MXC ，MXC中的X与XX中的X是同一个X 所以当有一个X确定后那么同样的有X的数位都要确定成X，这里可以作为一种剪枝条件，具体可以在DFS中设立一个记录栈，记录每位取值的情况，当DFS到当前位时，判断当前位之前是否有与当前位相同X的位，那么当前位的取值就不能从0~9枚举了，而要直接取值成之前的那个相同位X的值，这个值可通过伴随DFS的记录栈得到。比如串：XXXXMXC 栈：11115?? 。？表示还没填值，这样DFS到第一个问号时，依此下标去遍历之前的数位串中找到串[3] 与当前的串[5]是相同的，所以串[5]只能取1.注意只需要找到第一个之前的相同位即可，不用全部找出来，根据递推的特征，前面之前的几个已经保证是相等的了。另外，这个剪枝要好好写，判断是否是相同位要放到for（0~9）的外面去写（既然已经确定没有相同位了才进入for（0~9）的循环去枚举所有值，确定有相同位那就直接取这个值了，而不必进入循环里面去取0~9）。结果自己犯2 把它写到里面导致TLE了一次。

2、关于前导0的特殊情况，题目中提到不能出现前导0和单独0 这种情况。实际上就是广义的前导0的情况，包含了单独为0的那种情况。我们可以这样处理，在DFS中，每次数位取0的时候我们设一个单独标志flag0=1 说明目前存在前导0的情况，当在下次的，下下次的DFS中有数位取非零的情况那么flag0=0 表示这个非0的数位将他之前的那些所谓的前导0都抵消了，例如000-> 0001 （从左到右对应从低位到高位） 1将它前面的三个前导0抵消了。这样每当DFS到一个数值分界点时即刚好把这个数组成完毕，如abcd的d efgh的h，刚好能组成一个数的时候我们判断flag0 当前是否存在前导0的情况，若存在则剪枝（而数字在未完成状态时存在前导0是允许继续进入DFS的）。这样就把所有的前导0情况都避免了。

3、关于剪枝：我们知道abcd+efgh 即四位数+四位数可能等于四位数也可能等于五位数，而ijkl是一个四位数（由于不允许前导0，所以也不可能是三位二位。。。只能是实打实的四位数），对于比如abcd+efgh=ijkl 那么我们可以通过DFS到h刚完成时特定判断一下两个操作数想加的结果的位数是否等于原定结果的位数，如果不等于，那么我们没必要再DFS这条路径了，等式两边位数都不相同，怎么可能等式成立呢（两个人性别都不相同，怎么可能谈恋爱呢 orz...），所以我们剪掉这条路径。、

4、还是关于剪枝：当我们得到阿拉伯成立的情况已经有2种了，就没必要再DFS了，直接完全退出DFS（注意是完全退出，而不是单单退出某一条搜索路径），2种及以上的答案都是ambiguous

代码：（朴素的DFS）

其实感觉可以用hashtable 来实现重复X位的取值情况。

/*
naming roules:
basic var is lowercase
function name and struct class type name is highercase
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
char GStr[30+5]={'\0'};
int len=0;
char GStrL[10+5]={'\0'};//left operand
int lenL=0;
int NumL=0;//the num for roman and arabic
char GStrR[10+5]={'\0'};//right operand
int lenR=0;
int NumR=0;
char GStrS[10+5]={'\0'};//sum result
int lenS=0;
int NumS=0;
char GStrN[30+5]={'\0'};
int lenN=0;
int numstack[30+5]={0};
int numtop=0;
/*predeal the GStr to the GStrL and GStrR and GStrS*/
int Predeal()
{
	int i=0;
	len=strlen(GStr);
	lenL=0;
	lenR=0;
	lenS=0;
	lenN=0;
	i=len-1;
	memset(GStrN,'\0',sizeof(GStrN));
	//get the GStrS,the substring 's number low number bit at the GStrS's low string bit
	memset(GStrS,'\0',sizeof(GStrS));
	while(GStr[i]!='=')
	{
		GStrS[lenS++]=GStr[i];
		i--;
	}
	i--;//exclude the '='
	//get the GStrR,the substring 's number low number bit at the GStrR's low string bit
	memset(GStrR,'\0',sizeof(GStrR));
	while(GStr[i]!='+')
	{
		GStrR[lenR++]=GStr[i];
		i--;
	}
	i--;//exclude the '+'
	//get the GStrL,the substring 's number low number bit at the GStrL's low string bit
	memset(GStrL,'\0',sizeof(GStrL));
	while(i>=0)
	{
		GStrL[lenL++]=GStr[i];
		i--;
	}
	// the stirng and number 's bit is one by one map: low to lwo  high to high
	//get the GStrN that is GStr except the '+' and the '=' and change to the low bit to high bit sort
	strcat(GStrN,GStrL);
	strcat(GStrN,GStrR);
	strcat(GStrN,GStrS);
	return(0);
}
/*get the normal numner according to the Roman map list*/
int GetN(char c)
{
	switch(c)
	{
		case 'I':
		return(1);
		case 'V':
		return(5);
		case 'X':
		return(10);
		case 'L':
		return(50);
		case 'C':
		return(100);
		case 'D':
		return(500);
		case 'M':
		return(1000);
	}
	return(0);//error return digit
}
/*roman string num to the normal numbers*/
int RomanTransNum(char s[],int l)
{
	int i=0,j=i+1;//i is pointer represent the  higher positive value j is the pointer represent the lower negative value
	int sum=0;
	while(i<=l-1)
	{
		j=i+1;//j initialize
		sum+=GetN(s[i]);//the i is high so it must add to the sum
		while(j<=l-1)
		{
			if(GetN(s[i])>GetN(s[j]))
			{
				sum-=GetN(s[j]);//high - low  note it may be continuously occurate,so use sum-=low
			}
			else
			{
				break;
			}
			j++;//j pointer gohead
		}
		i=j;//i pointer gohead
	}
	return(sum);
}
/*judge the Roman number is correct or incorrect*/
int Roman()
{
	int lnum=0,rnum=0,snum=0;//left right and sum
	//roman number string transform to number
	lnum=RomanTransNum(GStrL,lenL);
	rnum=RomanTransNum(GStrR,lenR);
	snum=RomanTransNum(GStrS,lenS);
	if(snum==lnum+rnum)
	{
		printf("Correct");
	}
	else
	{
		printf("Incorrect");
	}
	return(0);
}
/*judge the cur is whether a repeat bit*/
bool IsReBit(int cur,int &num)
{
	//get the index of the GStrN,GStrN map to the numstack
	int curindex=cur-1;//this is num's  index
	int i=0;
	//find the same x in the prestring (only one) ,because  this is recursive, if third x  = second x  then  the third x must = first x,because in the before,we have let the first x=second x
	for(i=curindex-1;i>=0;i--)
	{
		if(GStrN[curindex]==GStrN[i])
		{
			num=numstack[i];
			return(true);
		}
	}
	return(false);
}
/*the cur is the depth of the GStr exclude the '+'and'=' 's  length 1->a 2->b ... 9->i*/
int flag0=0;//the flag0=1 says there is the preceding 0,when we meet the present bit is 0  the flag0<=1, if the higher bit >0 then this flag0<=0,the higher bit has offset the preceding 0 
int match=0;//0 is impossible 1 is valid 2 is ambiguous
int DFS(int cur)
{
	//prune the match ==2
	if(match>=2)//the answer has been generated,we need not to DFS in. this is global end the DFS,we can place this global prune at the all DFS behind,let it completely end the DFS quickly
	{
		return(0);
	}
	//prune the left (number + right number )'s bit length != lenS , it must be not equal so we prune it,this is the partial end the DFS(end the a boundary of the DFS)
	if(cur==lenL+lenR+1)//NumL and NumR has been generated
	{
		int NumLR=NumL+NumR;
		int bitLR=0;
		while(NumLR>0)
		{
			bitLR++;
			NumLR/=10;
		}
		if(bitLR!=lenS)
		{
			return(0);
		}
	}
	if(cur>lenL+lenR+lenS)//the recursive's end
	{
		if(NumL+NumR==NumS)
		{
			match++;
		}
	}
	else
	{
		int i=0;
		int num=0;//num is 0~9
		int bit=0;//the bit of the number
		int bitnum=1;// sum += num*  bitnum  bitnum=10^bit
		if(cur<=lenL)//cur point the left number
		{
			bit=cur-1;//num*10^0  num*10^1......
			for(i=1;i<=bit;i++)
			{
				bitnum*=10;
			} 
			if(IsReBit(cur,num))
			{
				NumL+=num*bitnum;
				numstack[numtop]=num;
				numtop++;
				if(num==0)
				{
					flag0=1;
				}
				else
				{
					flag0=0;
				}
				//prune the preceding 0
				if(cur==lenL&&flag0==1)//when the left number generate is finished it must not have preceding 0
				{
					;
				}
				else
				{
					DFS(cur+1);
					if(match>=2)
					{
						return(0);
					}
				}
				numtop--;
				NumL-=num*bitnum;
			}
			else
			{
				for(num=0;num<=9;num++)
				{
					NumL+=num*bitnum;
					numstack[numtop]=num;
					numtop++;
					if(num==0)
					{
						flag0=1;
					}
					else
					{
						flag0=0;
					}
					//prune the preceding 0
					if(cur==lenL&&flag0==1)//when the left number generate is finished it must not have preceding 0
					{
						;
					}
					else
					{
						DFS(cur+1);
						if(match>=2)
						{
							return(0);
						}
					}
					numtop--;
					NumL-=num*bitnum;
				}
			}
		}
		else if(cur<=lenL+lenR)//cur point the right number
		{
			bit=cur-lenL-1;//the bit of right number
			for(i=1;i<=bit;i++)
			{
				bitnum*=10;
			}
			//prune the x+x=xx the sum number 's x is same as the left and right number 's
			if(IsReBit(cur,num))
			{
				NumR+=num*bitnum;
				numstack[numtop]=num;
				numtop++;
				if(num==0)
				{
					flag0=1;
				}
				else
				{
					flag0=0;
				}
				//prune the preceding 0
				if(cur==lenL+lenR&&flag0==1)//when the right number generate is finished it must not have preceding 0
				{
					;
				}
				else
				{
					DFS(cur+1);
					if(match>=2)
					{
						return(0);
					}
				}
				numtop--;
				NumR-=num*bitnum;
			}
			else
			{
				for(num=0;num<=9;num++)
				{
					NumR+=num*bitnum;
					numstack[numtop]=num;
					numtop++;
					if(num==0)
					{
						flag0=1;
					}
					else
					{
						flag0=0;
					}
					//prune the preceding 0
					if(cur==lenL+lenR&&flag0==1)//when the right number generate is finished it must not have preceding 0
					{
						;
					}
					else
					{
						DFS(cur+1);
						if(match>=2)
						{
							return(0);
						}
					}
					numtop--;
					NumR-=num*bitnum;
				}
			}
		}
		else//cur point the sum number
		{
			bit=cur-lenL-lenR-1;
			for(i=1;i<=bit;i++)
			{
				bitnum*=10;
			}
			if(IsReBit(cur,num))
			{
				NumS+=num*bitnum;
				numstack[numtop]=num;
				numtop++;
				if(num==0)
				{
					flag0=1;
				}
				else
				{
					flag0=0;
				}
				//prune the preceding 0
				if(cur==lenL+lenR+lenS&&flag0==1)//when the sum number generate is finished it must not have preceding 0
				{
					;
				}
				else
				{
					DFS(cur+1);
					if(match>=2)
					{
						return(0);
					}
				}
				numtop--;
				NumS-=num*bitnum;
			}
			else
			{
				for(num=0;num<=9;num++)
				{
					NumS+=num*bitnum;
					numstack[numtop]=num;
					numtop++;
					if(num==0)
					{
						flag0=1;
					}
					else
					{
						flag0=0;
					}
					//prune the preceding 0
					if(cur==lenL+lenR+lenS&&flag0==1)//when the sum number generate is finished it must not have preceding 0
					{
						;
					}
					else
					{
						DFS(cur+1);
						if(match>=2)
						{
							return(0);
						}
					}
					numtop--;
					NumS-=num*bitnum;
				}
			}
		}
	}
	return(0);
}
/*dfs the GStrL GStrR GStrS's number bit  to 0~9  judge the result*/
int Arabic()
{
	//abc+def==ghi?? dfs the string "abcdefghi" per bit can use 0~9  note that the 0's specificity, note the x+x=xx ,the sum number's x is same as the left number  and the right number.it is same so the x=1 it must be 1+1=11,when we determin the x it can't enume all other the number
	NumL=NumR=NumS=0;//arabic number to the normal number
	flag0=0;
	match=0;
	numtop=0;
	DFS(1);//the cur is the depth of the GStr exclude the '+'and'=' 's  length 1->a 2->b ... 9->i
	if(match==0)
	{
		printf("impossible");
	}
	else if(match==1)
	{
		printf("valid");
	}
	else
	{
		printf("ambiguous");
	}
	return(0);
}
/*for test*/
int test()
{
	return(0);
}

/*main process*/
int MainProc()
{
	while(scanf("%s",GStr)!=EOF&&GStr[0]!='#')
	{
		//predeal the GStr to the GStrL and GStrR and GStrS
		Predeal();
		//judge the Roman number is correct or incorrect
		Roman();
		printf(" ");
		//judge the Arabic is impossible or valid or ambiguous
		Arabic();
		printf("\n");
	}
	return(0);
}

int main(int argc, char const *argv[])
{
	/* code */
	MainProc();
	return 0;
}