Four Operations

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 151    Accepted Submission(s): 61
 

Problem Description

Little Ruins is a studious boy, recently he learned the four operations!

Now he want to use four operations to generate a number, he takes a string which only contains digits '1' - '9', and split it into  intervals and add the four operations'+', '-', '*' and '/' in order, then calculate the result(/ used as integer division).

Now please help him to get the largest result.

Input

First line contains an integer , which indicates the number of test cases.

Every test contains one line with a string only contains digits '1'-'9'.

Limits
 

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.

Sample Input

1 12345

Sample Output

Case #1: 1

题意：给你一个字符串s，将字符串按顺序分成5组数字，在他们中间加入"+ - * /"进行运算，输出最大的结果。

思路：假设把s分成5个数a1,a2,a3,a4,a5，答案就是使a1+a2-a3*a4/a5的结果尽可能大。

那么有两种办法使结果尽可能大：

1.使a1+a2的值尽可能大

2.使a3*a4/a5的值尽可能小

对于1，有两种情况，a1=前n-1位数字，a2=第n个数字；或者a1=第1个数字，a2=2到n位数字。

对于2，,a3和a4可以取个位数字，使乘积最小，而个位数字的最大乘积是9*9=81，当a1+a2的值较小时对结果影响较大，所以可以让a5取字符串最后两位数字使得a3*a4/a5结果较小。

所以a5的取值就是后两位数字或是最后一位数字。

综上，通过枚举最大的结果即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

ll a[25];

ll getnum(int l,int r)
{
	ll i,sum=0;
	for(i=l;i<=r;i++)
		sum=sum*10+a[i];
	return sum;
}

int main()
{
	int t,len,i,Case=1;
	string s;
	cin>>t;
	while(t--)
	{
		cin>>s;
		len=s.length();
		for(i=0;i<len;i++)
			a[i]=s[i]-'0';
		ll ans=a[0]+getnum(1,len-4)-a[len-3]*a[len-2]/a[len-1];          
		ans=max(ans,getnum(0,len-5)+a[len-4]-a[len-3]*a[len-2]/a[len-1]);
		if(len>5)
		{
			int d=a[len-2]*10+a[len-1];
			ans=max(ans,a[0]+getnum(1,len-5)-a[len-4]*a[len-3]/d);
			ans=max(ans,getnum(0,len-6)+a[len-5]-a[len-4]*a[len-3]/d);
		}
		cout<<"Case #"<<Case++<<": "<<ans<<endl;
	}
	return 0;
}