没有合适的资源?快使用搜索试试~ 我知道了~
第九十四题 UVa12107 Digit Puzzle
0 下载量 188 浏览量
2021-01-20
12:06:10
上传
评论
收藏 52KB PDF 举报
温馨提示
试读
2页
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 ze
资源详情
资源评论
资源推荐
第九十四题第九十四题 UVa12107 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.
Fig 1. two good digit puzzles
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 × b = c”, and “a × b” and “b × 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 × 34 = *), though that puzzle is actually a simple multiplication problem. Write a program to
make good puzzles.
Input
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.
Output
For each test case, print the case number and the converted puzzle. If more than one optimal solution
is found, the lexicographically first one should be printed (remember that “” is before “0”). There is
always a solution.
Sample Input
7 ** 8
0
Sample Output
Case 1: 7 ** 8*
Case 2: ** ** 1*1
题目大意是给你三个待定的字符串。形如7 * 8 。要求变换空格或者数字似的前一个字符串X后一个字符串=最后一个字符串有
唯一解,且变换次数最少,多解时输出字典序最小的答案。规定空格的字典序小于数字。星号指代空格。
【题目分析】
迭代加深搜索,虽然是迭代加深搜索基础题,但是我真的啥也不会了,唉,第九十四道题目了,赶紧做完一百道,然后好
好休息几天,好好养好身体,剩下的等回学校在学吧(其实现在的我看淡了,成绩有的话呢固然好,没啥成绩也不必太过自
卑,好好生活比什么都强,简简单单的生活能过好就不容易),现在的我真的明白了,身体好才是第一位的。你们也要注视身
体,能不熬夜的就不要熬夜。
还有一点要说的,迭代加深搜索是个好东西,有时间的话就吃透他还有一点要说的,迭代加深搜索是个好东西,有时间的话就吃透他
#include
#include
#include
using namespace std;
char s[3][6];
char str[11] = {'*','0','1','2','3','4','5','6','7','8','9'};//*指代空格
int len[3],Maxdep;
int check_result() {
char chstr[10],ss[10];
int t0 = 0,t1 = 0,t2;
for(int i=0; i<len[0]; i++) t0 = t0 * 10 + s[0][i] - '0';
for(int i=0; i<len[1]; i++) t1 = t1 * 10 + s[1][i] - '0';
t2 = t0 * t1;
for(int i=0; i<len[2]; i++) {
chstr[len[2] - i - 1] = t2 % 10 + '0';
t2 /= 10;
}
if(t2 != 0 || chstr[0] == '0') return 0;
for(int i=0; i<len[2]; i++)
if(chstr[i] != s[2][i] && s[2][i] != '*') return 0;
return 1;
}
int check(int a,int b) {
weixin_38663151
- 粉丝: 3
- 资源: 897
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0