首页 > ACM题库 > HDU-杭电 > HDU 2931-Digit Puzzle[解题报告]HOJ
2014
02-24

HDU 2931-Digit Puzzle[解题报告]HOJ

Digit Puzzle

问题描述 :

If you hide some digits in an integer equation, you create a digit puzzle. The figure below shows two valid digit puzzles.Hidden digits are represented by squares, and other digits are shown. The numbers involved in this problem are all positive integers, written in decimal forms without leading zeros.

If a digit puzzle has a unique solution, we call it a good puzzle. Both puzzles shown above are good puzzles. The solution to the first puzzle is 7*12=84, while the solution to the second one is 11*11=121. You are already given some digit puzzles, but some of them are not good. Your task is to convert these puzzles into good ones. You can change any wildcard character (i.e. hidden digits) into a real digit, any real digit to a wildcard character, or
a real digit to another real digit, but you cannot insert or remove any character at any place. The number of changed characters should be minimized. In this problem, the puzzle is always in the form "a x b = c", and "a x b" and "b x a" should be considered different if a is not equal to b. It is allowed that all digits of both a and b are shown (e.g 12 x 34 = ****), though that puzzle is actually a simple multiplication problem. Write a program to make good puzzles.

输入:

The input contains several test cases. Each test case contains three non-empty strings, x, y, z, having at most 2, 2 and 4 characters respectively. Each character is a digit or a wildcard ‘*’, x will not begin with a zero character. The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. Each test case contains three non-empty strings, x, y, z, having at most 2, 2 and 4 characters respectively. Each character is a digit or a wildcard ‘*’, x will not begin with a zero character. The last test case is followed by a single zero, which should not be processed.

样例输入:

7 ** 8*
** ** ***
0

样例输出:

Case 1: 7 ** 8*
Case 2: ** ** 1*1

#include<cstdio>
#include<cstring>

int num[3],tot,n,f;
char s[3][100],ans[3][100];

int check()
{
	char str[100];
	int a=0,b=0,c;
	for(int i=0;i<num[0];i++)
		a=a*10+s[0][i]-'0';
	for(int i=0;i<num[1];i++)
		b=b*10+s[1][i]-'0';
	c=a*b;
	for(int i=num[2]-1;i>=0;i--)
	{
		str[i]='0'+c%10;
		c/=10;
	}
	if(c>0||str[0]=='0')
		return 0;
	for(int i=0;i<num[2];i++)
		if(s[2][i]!=str[i]&&s[2][i]!='*')
			return 0;
	return 1;
}

void dfs(int a,int b)
{
	if(b>=num[a])
	{
		b=0;
		a++;
	}
	if(a==2)
	{
		if(check())
			tot++;
		return;
	}
	if(s[a][b]!='*')
		dfs(a,b+1);
	else
	{
		for(int i=0;i<10;i++)
		{
			if(b==0&&i==0)
				continue;
			s[a][b]='0'+i;
			dfs(a,b+1);
			if(tot>1)
			{
				s[a][b]='*';
				return;
			}
		}
		s[a][b]='*';
	}
}

void search(int a,int b,int c)
{
	if(b>=num[a])
	{
		b=0;
		a++;
	}
	if(c==n)
	{
		tot=0;
		dfs(0,0);
		if(tot==1)
		{
			f=1;
			for(int i=0;i<3;i++)
				strcpy(ans[i],s[i]);
		}
		return;
	}
	if(a>=3)
		return;
	char ch=s[a][b],tc;
	for(int i=0;i<=10;i++)
	{
		if(i==1&&b==0)
			continue;
		if(!i)
			tc='*';
		else
			tc='0'+i-1;
		if(tc==s[a][b])
			search(a,b+1,c);
		else
		{
			s[a][b]=tc;
			search(a,b+1,c+1);
		}
		if(f)
		{
			s[a][b]=ch;
			return;
		}
		s[a][b]=ch;
	}
}

void work()
{
	int m=0;
	for(int i=0;i<3;i++)
		m+=num[i];
	for(n=1;n<=m;n++)
	{
		f=0;;
		search(0,0,0);
		if(f)
			return;
	}
}

int main()
{
	int cas=1;
	memset(s,0,sizeof(s));
	while(scanf("%s",s[0])&&s[0][0]!='0')
	{
		scanf("%s%s",s[1],s[2]);
		for(int i=0;i<3;i++)
			num[i]=strlen(s[i]);
		tot=0;
		dfs(0,0);
		printf("Case %d: ",cas++);
		if(tot==1)
			printf("%s %s %s\n",s[0],s[1],s[2]);
		else
		{
			work();
			printf("%s %s %s\n",ans[0],ans[1],ans[2]);
		}
		memset(s,0,sizeof(s));
	}
	return 0;
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }