XM35. CCNumber
描述
CC最近对一种整数比较感兴趣，我们暂且把这种整数称为C Number, C Number是指一个整数 {C0, C1 … Cn-1} (C0 > 0 , n >= 3)， 存在一个Cm（0<m<n-1）满足以下条件:输入描述
第一行为数字N(N<=1000),后面有N行测试用例输出描述
对于第N行的测试用例，输出“Case N: S”, S为最大的score，如果区间内没有CC Number的话 S为0。示例1
输入:
4 12121 12121 120010 120010 121121 121121 1211121 1211121
输出:
Case 1: 0 Case 2: 0 Case 3: 8 Case 4: 0
C++14 解法, 执行用时: 14ms, 内存消耗: 492KB, 提交时间: 2020-07-29
#include <string>
#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
/*
阶段划分
1 表示第一序列的起始 后必须接着一个升序
2 已经有过升序，可选继续升或降
3 只降了一次 可选继续降 或 自选一个起点进入下一轮起点阶段(要借一位)
4 继续降(如果后续位数过多) 或 下一轮起点阶段
5 第二轮的起点 必须升
6 第二轮升序 可选升/降
7 第二轮降序 降
*/
const int num_digit = 10;//数字位数
const int max_bit = 20;//整数最大位数
const int max_size = max_bit+1;
vector<vector<vector<int>> > T(8,vector<vector<int>>(num_digit,vector<int>(max_size,-1)));//T[k][i][num] 阶段k 当末尾为i时 使用num个数字填充的最大Score -1表示无法填充
//vector<vector<vector<string>> > T_s(8,vector<vector<string>>(num_digit,vector<string>(max_size,"")));
void traverse(int t){
int i,k;
unsigned seed = time(0);
srand(seed);
for(int stage = 7;stage>=t;stage-- ){
cout<<"stage"<<stage<<" testing:"<<endl;
for(int j=0;j<5;j++){
i = rand()%10;
k = rand()%max_bit+1;
//cout<<"[i : "<<i<<",num : "<<k<<",score : "<<T[stage][i][k]<<"] "<< T_s[stage][i][k] <<endl;
}
cout<<endl;
}
}
void preprocessing(int stage){
if(stage==7){
//阶段7 只允许降
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
if(k>i){
break;
}else{
//string su="";
if(k==1) {
T[7][i][k]=i-k;
//su+=to_string(i-k);
}
// i-1,i-2,...,0相加
else {
T[7][i][k]=T[7][i][k-1]+i-k;
//su+=T_s[7][i][k-1]+to_string(i-k);
}
//T_s[7][i][k] = su;
}
//if(T[7][i][k]!=-1) cout<<T[7][i][k]<<" ";
}
//cout<<endl;
}
//PR(T[7]);
//PR(T_s[7]);
}
if(stage==6){
//阶段6 可选升/降
for(int i=2;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//只能降
if(k==1){
if(i!=0){
T[6][i][k]=i-k;
//T_s[6][i][k]=to_string(i-k);
}
continue;
}
//string su="";
int ans = -1;
int sum = 0;//升序带来的score
//尝试先升 在可以升的选择中 选择最大值
//尝试升 升到9是1步 升到8是两步(8,9)
//string su_prefix = "";
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;
sum+=j;
//su_prefix = to_string(j)+su_prefix;
int t = T[7][9][k-(9-j+1)];//升后最后一定是9
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_prefix+T_s[7][9][k-(9-j+1)];
}
}
//或者直接降
if(ans<T[7][i][k]){
ans = T[7][i][k];
//su = T_s[7][i][k];
}
T[6][i][k] = ans;
//T_s[6][i][k] = su;
}
}
}
if(stage==5){
//节点5 必须升
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su="";
int ans = -1;
int sum = 0;
//string su_prefix = "";
//升到几 需得尝试
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;//
sum+=j;
//su_prefix = to_string(j)+su_prefix;
int t = T[6][9][k-(9-j+1)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_prefix+T_s[6][9][k-(9-j+1)];
}
}
if(k!=1 and ans==-1) break;
T[5][i][k] = ans;
//T_s[5][i][k] = su;
}
}
}
if(stage==4){
//阶段4 可选降 或是下一轮 或自选一起点进入下一轮
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_des_prefix = "";
//降到几 需得尝试
for(int j=i-1;j>=0;j--){
if(k<=(i-j)) break;
sum+=j;
//su_des_prefix += to_string(j);
int t = T[4][j][k-(i-j)];//又点纠结是降还是进入下一轮
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_des_prefix+T_s[4][j][k-(i-j)];
}
}
//或以当前节点为首 进入下一轮
if(i!=0){
if(T[5][i][k]!=-1 and ans<T[5][i][k]){
ans = T[5][i][k];
//su = T_s[5][i][k];
}
}
//自选下一个位的值 序列首不能是0
for(int j=1;j<=9;j++){
if(k==1) break;
if(T[5][j][k-1]==-1) continue;
if(ans<j+T[5][j][k-1]){
ans = j+T[5][j][k-1];
}
}
T[4][i][k] = ans;
//T_s[4][i][k] = su;
}
}
}
if(stage==3){
//阶段3 只降了一次 可选继续降 或 自选一个起点进入下一轮起点阶段(要借一位)
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_des_prefix = "";
//降到几 需得尝试
for(int j=i-1;j>=0;j--){
if(k<(i-j+3)) break;
sum+=j;
//su_des_prefix += to_string(j);
int t = T[4][j][k-(i-j)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_des_prefix+T_s[4][j][k-(i-j)];
}
}
//自选下一个位的值 序列首不能是0
for(int j=1;j<=9;j++){
if(k==1) break;
if(T[5][j][k-1]==-1) continue;
if(ans<j+T[5][j][k-1]){
ans = j+T[5][j][k-1];
//su = to_string(j) + T_s[5][j][k-1];
}
}
T[3][i][k] = ans;
//T_s[3][i][k] = su;
}
}
}
if(stage==2){
//阶段2 已经有过升序，可选继续升或降
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_des_prefix = "";
//降到几 需得尝试
for(int j=i-1;j>=0;j--){
if(k<(i-j+3)) break; //TODO 3是下一序列的起码3个
sum+=j;
//su_des_prefix += to_string(j);
int t = T[3][j][k-(i-j)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_des_prefix+T_s[3][j][k-(i-j)];
}
}
sum = 0;
//string su_as_prefix = "";
//升到几 需得尝试
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;
sum+=j;
//su_as_prefix = to_string(j)+su_as_prefix;
int t = T[3][9][k-(9-j+1)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+T[3][9][k-(9-j+1)];
//su = su_as_prefix+T_s[3][9][k-(9-j+1)];
}
}
T[2][i][k] = ans;
//T_s[2][i][k] = su;
}
}
}
if(stage==1){
//1 表示第一序列的起始 后必须接着一个升序
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_as_prefix = "";
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;
sum+=j;
//su_as_prefix = to_string(j)+su_as_prefix;
int t = T[2][9][k-(9-j+1)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+T[2][9][k-(9-j+1)];
//su = su_as_prefix+T_s[2][9][k-(9-j+1)];
}
}
if(i==1 and k==5){
//cout<<T[2][9][4]<<endl;
}
T[1][i][k] = ans;
//T_s[1][i][k] = su;
}
}
}
}
//-1表示不可能
int cal_stage(string s){
int n = s.length();
int stage = 1;
int i = 0;
while(i<n and s[i]=='0') i++;
if(i==n-1) return stage;//
if(i<n-1 and s[i]>=s[i+1]) return -1;//没有增
stage=2;//1只要有增就进入下一个阶段 1->2 遇到一次升序
while(i<n-1 and s[i]<s[i+1]) i++;//升序
//升序过后，i为第一个极高点
//循环结束后需要判定是因为到了末尾还是因为遭遇了 降或者平
if(i==n-1) return stage;//末尾 返回阶段2
if(s[i]==s[i+1]) return -1;//遇到平
int j = i;
while(i<n-1 and s[i]>s[i+1]) i++;//降序
//只降了一次
if(i-j==1){
//降一次 变为阶段3 65 此时最后一个5不能作为下一轮起点
stage=3;
if(i==n-1) return stage;
j = i+1;
stage = 5;
}else{
stage=4;
if(i==n-1) return stage;//如果结束 以阶段4返回
//否则转为5,此时i或i+1 都可能是下一轮起点
stage=5;
//如果i是0 或者 两者相等 则i+1必然是起点
if(s[i]=='0' or s[i]==s[i+1]){
j=i+1;
}else j=i;//否则i就是起点
}
if(j==n-1) return stage;
i=j;
//第二序列开启
//1232198 "6789121"
if(s[i]=='0' or s[i]>=s[i+1]) return -1;//首为0 或降、平序
stage = 6;
while(i<n-1 and s[i]<s[i+1]) i++;//第二序列 升序
if(i==n-1) return stage;//末尾 返回阶段6
if(s[i]==s[i+1]) return -1;//遇到平
//遇到减 转为阶段6
stage = 7;
while(i<n-1 and s[i]>s[i+1]) i++;
if(i==n-1) return stage;//到末尾一直是减 返回阶段7
//再度遭遇平或升
return -1;
}
int score;
//此时A,B前[0-k]位相同 后面A全为0 B全为9
void count(string A,string B,int k,int prefix_value){
int n = A.length();
int i=0;
while(i<n and A[i]=='0') i++;
//判定公共前缀的状态
string prefix = A.substr(i,(k-i)+1);
int stage = cal_stage(prefix);
int v = A[k]-'0';
if(stage==-1) return;
if(T[stage][v][n-k-1]==-1);
int now = prefix_value+T[stage][v][n-k-1];
if(now>score){
score = now;
//cout<<score<<" "<<prefix+T_s[stage][v][n-k-1]<<endl;
}
}
//计算[A,B]中包含CCNumber的整数的最大Score
void cal(string A,string B,int k,int prefix_score){
int n = A.length();
int i=0;
while(i<n and i<k and (A[i]=='0' and B[i]=='0')){
k--;
i++;
n--;
}
if(i!=0){
A = A.substr(i);
B = B.substr(i);
}
if(n<6) return ;
if(A==B){
if(n>=6 and cal_stage(A)==7){
int sum = 0;
for(auto c:A){
sum+=c-'0';
}
if(sum>score) score = sum;
}
return ;
}
int v = A[k]-'0';
//如果公共前缀的数字之和 加上令k及其以后全部为9 加起来的结果也不如现在的score 放弃搜索
//if(prefix_score+T[0][v][n-k-1]<=score)return ;
string prefix = "";
int stage = -1;
if(k!=0){
prefix = A.substr(0,k);
stage = cal_stage(prefix);
if(stage==-1) {
return;
}
if(prefix_score+T[stage][A[k-1]-'0'][n-k]<=score){
//PR(stage,A[k-1]-'0',n-k);
//PR(prefix_score,k,T[stage][A[k-1]-'0'][n-k],score,"??",A,B);
return ;
}
}
//到了最后可以计算了
if(k==n-1) return ; //TODO 直接遍历也行;
//如果B后缀9的个数达到(n-k)个,
//从第k位开始判定
if(A[k]==B[k]){
/*
if(stage==1 or stage==5){
if(A[k-1]>=v) return;
}*/
cal(A,B,k+1,prefix_score+A[k]-'0');
return ;
}
string na(B),nb(A);
for(int i=k+1;i<n;i++){
na[i]='0';
nb[i]='9';
}
//PR(na,B,A,nb);
if(B[k]-A[k]>1){
string ma(A),mb(B);
for(int i=k+1;i<n;i++){
ma[i]='0';
mb[i]='9';
}
for(int mk=A[k]+1;mk<=B[k]-1;mk++){
ma[k]=mk;mb[k]=mk;
//PR(ma,mb);
//它可以计算了
count(ma,mb,k,prefix_score+mk-'0');
}
}
/*
if(stage==1 or stage==5){
if(A[k-1]>=v) return;
if(na[k-1]>=v) return;
if(nb[k-1]>=v) return;
if(B[k-1]>=v) return;
}
if(stage==7){
if(A[k-1]<=v) return;
if(na[k-1]<=v) return;
if(nb[k-1]<=v) return;
if(B[k-1]<=v) return;
}
*/
cal(na,B,k+1,prefix_score+B[k]-'0');
cal(A,nb,k+1,prefix_score+A[k]-'0');
}
int main(){
//freopen("temp.in","r",stdin);
int N;
cin>>N;
for(int i=7;i>=1;i--){
preprocessing(i);
}
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
for(int t=7;t>=1;t--){
T[0][i][k]=max(T[t][i][k],T[0][i][k]);
}
}
}
for(int k=1;k<=N;k++){
string A,B;
cin>>A>>B;
score = 0;
//将A补0，填充到与B同长
int an = A.length(),bn = B.length();
for(int i=an;i<bn;i++){A = "0"+A;}
cal(A,B,0,0);
//PR(NUM);
cout<<"Case "<<k<<": "<<score<<endl;
}
return 0;
}
C++ 解法, 执行用时: 15ms, 内存消耗: 380KB, 提交时间: 2020-10-29
#include <string>
#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
/*
阶段划分
1 表示第一序列的起始 后必须接着一个升序
2 已经有过升序，可选继续升或降
3 只降了一次 可选继续降 或 自选一个起点进入下一轮起点阶段(要借一位)
4 继续降(如果后续位数过多) 或 下一轮起点阶段
5 第二轮的起点 必须升
6 第二轮升序 可选升/降
7 第二轮降序 降
*/
const int num_digit = 10;//数字位数
const int max_bit = 20;//整数最大位数
const int max_size = max_bit+1;
vector<vector<vector<int>> > T(8,vector<vector<int>>(num_digit,vector<int>(max_size,-1)));//T[k][i][num] 阶段k 当末尾为i时 使用num个数字填充的最大Score -1表示无法填充
//vector<vector<vector<string>> > T_s(8,vector<vector<string>>(num_digit,vector<string>(max_size,"")));
void traverse(int t){
int i,k;
unsigned seed = time(0);
srand(seed);
for(int stage = 7;stage>=t;stage-- ){
cout<<"stage"<<stage<<" testing:"<<endl;
for(int j=0;j<5;j++){
i = rand()%10;
k = rand()%max_bit+1;
//cout<<"[i : "<<i<<",num : "<<k<<",score : "<<T[stage][i][k]<<"] "<< T_s[stage][i][k] <<endl;
}
cout<<endl;
}
}
void preprocessing(int stage){
if(stage==7){
//阶段7 只允许降
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
if(k>i){
break;
}else{
//string su="";
if(k==1) {
T[7][i][k]=i-k;
//su+=to_string(i-k);
}
// i-1,i-2,...,0相加
else {
T[7][i][k]=T[7][i][k-1]+i-k;
//su+=T_s[7][i][k-1]+to_string(i-k);
}
//T_s[7][i][k] = su;
}
//if(T[7][i][k]!=-1) cout<<T[7][i][k]<<" ";
}
//cout<<endl;
}
//PR(T[7]);
//PR(T_s[7]);
}
if(stage==6){
//阶段6 可选升/降
for(int i=2;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//只能降
if(k==1){
if(i!=0){
T[6][i][k]=i-k;
//T_s[6][i][k]=to_string(i-k);
}
continue;
}
//string su="";
int ans = -1;
int sum = 0;//升序带来的score
//尝试先升 在可以升的选择中 选择最大值
//尝试升 升到9是1步 升到8是两步(8,9)
//string su_prefix = "";
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;
sum+=j;
//su_prefix = to_string(j)+su_prefix;
int t = T[7][9][k-(9-j+1)];//升后最后一定是9
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_prefix+T_s[7][9][k-(9-j+1)];
}
}
//或者直接降
if(ans<T[7][i][k]){
ans = T[7][i][k];
//su = T_s[7][i][k];
}
T[6][i][k] = ans;
//T_s[6][i][k] = su;
}
}
}
if(stage==5){
//节点5 必须升
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su="";
int ans = -1;
int sum = 0;
//string su_prefix = "";
//升到几 需得尝试
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;//
sum+=j;
//su_prefix = to_string(j)+su_prefix;
int t = T[6][9][k-(9-j+1)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_prefix+T_s[6][9][k-(9-j+1)];
}
}
if(k!=1 and ans==-1) break;
T[5][i][k] = ans;
//T_s[5][i][k] = su;
}
}
}
if(stage==4){
//阶段4 可选降 或是下一轮 或自选一起点进入下一轮
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_des_prefix = "";
//降到几 需得尝试
for(int j=i-1;j>=0;j--){
if(k<=(i-j)) break;
sum+=j;
//su_des_prefix += to_string(j);
int t = T[4][j][k-(i-j)];//又点纠结是降还是进入下一轮
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_des_prefix+T_s[4][j][k-(i-j)];
}
}
//或以当前节点为首 进入下一轮
if(i!=0){
if(T[5][i][k]!=-1 and ans<T[5][i][k]){
ans = T[5][i][k];
//su = T_s[5][i][k];
}
}
//自选下一个位的值 序列首不能是0
for(int j=1;j<=9;j++){
if(k==1) break;
if(T[5][j][k-1]==-1) continue;
if(ans<j+T[5][j][k-1]){
ans = j+T[5][j][k-1];
}
}
T[4][i][k] = ans;
//T_s[4][i][k] = su;
}
}
}
if(stage==3){
//阶段3 只降了一次 可选继续降 或 自选一个起点进入下一轮起点阶段(要借一位)
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_des_prefix = "";
//降到几 需得尝试
for(int j=i-1;j>=0;j--){
if(k<(i-j+3)) break;
sum+=j;
//su_des_prefix += to_string(j);
int t = T[4][j][k-(i-j)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_des_prefix+T_s[4][j][k-(i-j)];
}
}
//自选下一个位的值 序列首不能是0
for(int j=1;j<=9;j++){
if(k==1) break;
if(T[5][j][k-1]==-1) continue;
if(ans<j+T[5][j][k-1]){
ans = j+T[5][j][k-1];
//su = to_string(j) + T_s[5][j][k-1];
}
}
T[3][i][k] = ans;
//T_s[3][i][k] = su;
}
}
}
if(stage==2){
//阶段2 已经有过升序，可选继续升或降
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_des_prefix = "";
//降到几 需得尝试
for(int j=i-1;j>=0;j--){
if(k<(i-j+3)) break; //TODO 3是下一序列的起码3个
sum+=j;
//su_des_prefix += to_string(j);
int t = T[3][j][k-(i-j)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+t;
//su = su_des_prefix+T_s[3][j][k-(i-j)];
}
}
sum = 0;
//string su_as_prefix = "";
//升到几 需得尝试
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;
sum+=j;
//su_as_prefix = to_string(j)+su_as_prefix;
int t = T[3][9][k-(9-j+1)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+T[3][9][k-(9-j+1)];
//su = su_as_prefix+T_s[3][9][k-(9-j+1)];
}
}
T[2][i][k] = ans;
//T_s[2][i][k] = su;
}
}
}
if(stage==1){
//1 表示第一序列的起始 后必须接着一个升序
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
//string su = "";
int ans = -1;
int sum = 0;
//string su_as_prefix = "";
for(int j=9;j>=i+1;j--){
if(k<=(9-j+1)) break;
sum+=j;
//su_as_prefix = to_string(j)+su_as_prefix;
int t = T[2][9][k-(9-j+1)];
if(t==-1) continue;
if(ans<sum+t){
ans = sum+T[2][9][k-(9-j+1)];
//su = su_as_prefix+T_s[2][9][k-(9-j+1)];
}
}
if(i==1 and k==5){
//cout<<T[2][9][4]<<endl;
}
T[1][i][k] = ans;
//T_s[1][i][k] = su;
}
}
}
}
//-1表示不可能
int cal_stage(string s){
int n = s.length();
int stage = 1;
int i = 0;
while(i<n and s[i]=='0') i++;
if(i==n-1) return stage;//
if(i<n-1 and s[i]>=s[i+1]) return -1;//没有增
stage=2;//1只要有增就进入下一个阶段 1->2 遇到一次升序
while(i<n-1 and s[i]<s[i+1]) i++;//升序
//升序过后，i为第一个极高点
//循环结束后需要判定是因为到了末尾还是因为遭遇了 降或者平
if(i==n-1) return stage;//末尾 返回阶段2
if(s[i]==s[i+1]) return -1;//遇到平
int j = i;
while(i<n-1 and s[i]>s[i+1]) i++;//降序
//只降了一次
if(i-j==1){
//降一次 变为阶段3 65 此时最后一个5不能作为下一轮起点
stage=3;
if(i==n-1) return stage;
j = i+1;
stage = 5;
}else{
stage=4;
if(i==n-1) return stage;//如果结束 以阶段4返回
//否则转为5,此时i或i+1 都可能是下一轮起点
stage=5;
//如果i是0 或者 两者相等 则i+1必然是起点
if(s[i]=='0' or s[i]==s[i+1]){
j=i+1;
}else j=i;//否则i就是起点
}
if(j==n-1) return stage;
i=j;
//第二序列开启
//1232198 "6789121"
if(s[i]=='0' or s[i]>=s[i+1]) return -1;//首为0 或降、平序
stage = 6;
while(i<n-1 and s[i]<s[i+1]) i++;//第二序列 升序
if(i==n-1) return stage;//末尾 返回阶段6
if(s[i]==s[i+1]) return -1;//遇到平
//遇到减 转为阶段6
stage = 7;
while(i<n-1 and s[i]>s[i+1]) i++;
if(i==n-1) return stage;//到末尾一直是减 返回阶段7
//再度遭遇平或升
return -1;
}
int score;
//此时A,B前[0-k]位相同 后面A全为0 B全为9
void count(string A,string B,int k,int prefix_value){
int n = A.length();
int i=0;
while(i<n and A[i]=='0') i++;
//判定公共前缀的状态
string prefix = A.substr(i,(k-i)+1);
int stage = cal_stage(prefix);
int v = A[k]-'0';
if(stage==-1) return;
if(T[stage][v][n-k-1]==-1);
int now = prefix_value+T[stage][v][n-k-1];
if(now>score){
score = now;
//cout<<score<<" "<<prefix+T_s[stage][v][n-k-1]<<endl;
}
}
//计算[A,B]中包含CCNumber的整数的最大Score
void cal(string A,string B,int k,int prefix_score){
int n = A.length();
int i=0;
while(i<n and i<k and (A[i]=='0' and B[i]=='0')){
k--;
i++;
n--;
}
if(i!=0){
A = A.substr(i);
B = B.substr(i);
}
if(n<6) return ;
if(A==B){
if(n>=6 and cal_stage(A)==7){
int sum = 0;
for(auto c:A){
sum+=c-'0';
}
if(sum>score) score = sum;
}
return ;
}
int v = A[k]-'0';
//如果公共前缀的数字之和 加上令k及其以后全部为9 加起来的结果也不如现在的score 放弃搜索
//if(prefix_score+T[0][v][n-k-1]<=score)return ;
string prefix = "";
int stage = -1;
if(k!=0){
prefix = A.substr(0,k);
stage = cal_stage(prefix);
if(stage==-1) {
return;
}
if(prefix_score+T[stage][A[k-1]-'0'][n-k]<=score){
//PR(stage,A[k-1]-'0',n-k);
//PR(prefix_score,k,T[stage][A[k-1]-'0'][n-k],score,"??",A,B);
return ;
}
}
//到了最后可以计算了
if(k==n-1) return ; //TODO 直接遍历也行;
//如果B后缀9的个数达到(n-k)个,
//从第k位开始判定
if(A[k]==B[k]){
/*
if(stage==1 or stage==5){
if(A[k-1]>=v) return;
}*/
cal(A,B,k+1,prefix_score+A[k]-'0');
return ;
}
string na(B),nb(A);
for(int i=k+1;i<n;i++){
na[i]='0';
nb[i]='9';
}
//PR(na,B,A,nb);
if(B[k]-A[k]>1){
string ma(A),mb(B);
for(int i=k+1;i<n;i++){
ma[i]='0';
mb[i]='9';
}
for(int mk=A[k]+1;mk<=B[k]-1;mk++){
ma[k]=mk;mb[k]=mk;
//PR(ma,mb);
//它可以计算了
count(ma,mb,k,prefix_score+mk-'0');
}
}
/*
if(stage==1 or stage==5){
if(A[k-1]>=v) return;
if(na[k-1]>=v) return;
if(nb[k-1]>=v) return;
if(B[k-1]>=v) return;
}
if(stage==7){
if(A[k-1]<=v) return;
if(na[k-1]<=v) return;
if(nb[k-1]<=v) return;
if(B[k-1]<=v) return;
}
*/
cal(na,B,k+1,prefix_score+B[k]-'0');
cal(A,nb,k+1,prefix_score+A[k]-'0');
}
int main(){
//freopen("temp.in","r",stdin);
int N;
cin>>N;
for(int i=7;i>=1;i--){
preprocessing(i);
}
for(int i=0;i<=9;i++){
for(int k=1;k<=max_bit;k++){
for(int t=7;t>=1;t--){
T[0][i][k]=max(T[t][i][k],T[0][i][k]);
}
}
}
for(int k=1;k<=N;k++){
string A,B;
cin>>A>>B;
score = 0;
//将A补0，填充到与B同长
int an = A.length(),bn = B.length();
for(int i=an;i<bn;i++){A = "0"+A;}
cal(A,B,0,0);
//PR(NUM);
cout<<"Case "<<k<<": "<<score<<endl;
}
return 0;
}