题目

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 5 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 T, which indicates the number of test cases.

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

Limits
1≤T≤105
5≤length of string≤20

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

题解

在一串数中 按顺序 插入 + - * / 使结果最大

由于运算顺序,可知 - 后面越小越好,因此应该让 + 左右的一端尽可能大(位数越多越大)

大概是这样一个思路,不过会有一些特例,于是用随机数强行 O(n⁴) 模拟,测试数据
然后就能发现规律:
/ 后有可能是 2 位数(除完是0,然后促使 - 后是 0 ),也可能是 1 位数
- * 后都是 1 位数
+ 左右一边是 1 位,剩下的位数在另一边

然后,就是比较四个情况的大小即可
如果只有5个数要单独直接输出！！！

不是很难,但是很容易卡进去的题

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <vector>
#include <list>
#include <map>
#include <functional>

using namespace std;

const int maxn = 25;

int kase = 1;
char s[maxn];

long long toInt(const char *s,int u,int v) {
    long long t = 0;
    for(int i = u;i <= v;i++) {
        t *= 10;
        t += s[i] - '0';
    }
    return t;
}

int vs_main() {
    cin.tie(0);
    cin.sync_with_stdio(false);


    int T;
    cin >> T;
    while(T--) {
        cin >> s;

        long long ans = 0;
        int n = strlen(s);
        if(n == 5) {
            ans = toInt(s,0,0) + toInt(s,1,1) - toInt(s,2,2) * toInt(s,3,3) / toInt(s,4,4);
        } else {
            long long a = toInt(s,0,n - 5) + toInt(s,n - 4,n - 4) - toInt(s,n - 3,n - 3)*toInt(s,n - 2,n - 2) / toInt(s,n - 1,n - 1);
            long long b = toInt(s,0,0) + toInt(s,1,n - 4) - toInt(s,n - 3,n - 3)*toInt(s,n - 2,n - 2) / toInt(s,n - 1,n - 1);
            long long c = toInt(s,0,n - 6) + toInt(s,n - 5,n - 5) - toInt(s,n - 4,n - 4)*toInt(s,n - 3,n - 3) / toInt(s,n - 2,n - 1);
            long long d = toInt(s,0,0) + toInt(s,1,n - 5) - toInt(s,n - 4,n - 4)*toInt(s,n - 3,n - 3) / toInt(s,n - 2,n - 1);
            ans = max(max(a,b),max(c,d));
        }

        cout << "Case #" << kase++ << ": " << ans << endl;
    }
    return 0;
}