当前位置: 首页 > >

顺丰科技2017笔试 小C负责设计一种新的益智数字游戏

发布时间:

小C负责设计一种新的益智游戏。游戏分A、B两方,规则如下:
1.A方在一个纸片上写一个不超过6位的数值N,同时给出一个目标数M;
2.B方对写有数值N的纸片进行分割,分割成的每个纸片上有一个数,所有纸片上数的和不能大于目标数M,但需要尽可能与M接*。
3.若N与M相同,则不进行分割。
4.若无论如何分割,所得的碎纸片上数之和都大于目标数M,则表示错误。
5.若有多种不同的分割方式可以得到相同的最优结果。则拒绝分割。
游戏开发之前,小A计划先编写一个模拟程序。给定两个数,第一个是目标数M,第二个是写在纸片上的数N,输出分割的方式。


输入:
输入包括多组数据,每一组数据为一行,包括两个正整数M和N,保证两个数都不会以0开头,而且两个数最多只包含6个数字。
输入的最后一行包括由空格分隔两个0,表示输入的结束。


输出:
对每组输入数据,给出相应的输出。可能有三种不同的输出结果:
sum part1 part2 …
rejected
error
上述结果表示如下:
sum为碎纸片上数之和,即:sum = part1+part2+…。part j为碎纸片上数,顺序与待碎纸片上原始数中数字出现的次序一致。
若无论如何分割,所得碎纸片上数的和都大于目标数,则输出”error”。
若有多种不同的分割方式可得到相同的最优结果,则输出”rejected”。


样例输入
50 12346
376 144139
9274378 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0


样例输出
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected


使用回溯法
代码如下:


#include
#include
using namespace std;

vector Split(int n)
{
vector res;
while(n)
{
int tmp = n % 10;
res.insert(res.begin(),tmp);
n /= 10;
}
return res;
}

void Proc(int M, vector &N, int index, vector &split, int &max_sum, vector &res,bool &isRejected)
{
if (index >= N.size())
{
int sum = 0;
for (int i=0; i sum += split[i];
if (sum > M) return;
if (sum < max_sum) return;
if (sum == max_sum)
{
isRejected = true;
return;
}
isRejected = false;
res.clear();
max_sum = sum;
for (int i=0; i res.push_back(split[i]);
return;
}
for (int l=1; l<=N.size()-index; l++)
{
int temp = 0;
for (int i=0; i temp = temp * 10 + N[index+i];
split.push_back(temp);
Proc(M,N,index+l,split,max_sum,res,isRejected);
split.pop_back();
}
}

int main()
{
vector M,N;
int m,n;
while (1)
{
cin>>m>>n;
if (m == 0 && n == 0) break;
M.push_back(m);
N.push_back(n);
}
for (int i=0; i {
vector split = Split(N[i]);
vector splitTemp;
vector res;
int max_sum = 0;
bool isRejected = false;
Proc(M[i],split,0,splitTemp,max_sum,res,isRejected);
if (isRejected)
{
cout<<"rejected"< }
else if (max_sum == 0)
{
cout<<"error"< }
else
{
cout< for (int j=0; j cout< cout< }
}

return 0;
}



友情链接: