P13193 [GCJ 2016 #1B] Close Match

题目描述

你正在观看体育史上最重要的一场比赛:Oceania Coders 队对阵 Eurasia Jammers 队,比赛场地为 Centrifugal Bumble-Puppy 世界总决赛。不幸的是,由于你因期待而彻夜难眠,比赛期间你竟然睡着了! 现在计分牌上显示着双方的得分,可能带有一个或多个前导零(因为计分牌会显示固定位数的数字)。当你熟睡时,计分牌的一些灯泡被猛烈的球击坏了,因此一方或双方的得分中有一位或多位数字没有显示出来。 你觉得比分接近的比赛最精彩,所以你希望能够想象出一个比分尽可能接近的场景。你能否用某种方式填补所有缺失的数字,使得两队分数的绝对差值最小?如果有多种方案可以达到最小绝对差值,请选择 Coders 队得分最小的方案;如果在 Coders 队得分也相同的情况下仍有多种方案,则选择 Jammers 队得分最小的方案。

输入格式

输入的第一行包含一个整数 $\mathbf{T}$,表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例包含一行,包含两个非空字符串 $\mathbf{C}$ 和 $\mathbf{J}$,长度相同,仅由十进制数字和问号组成,分别表示你看到的 Coders 队和 Jammers 队的分数。每组测试用例中至少有一个问号。

输出格式

对于每组测试用例,输出一行 `Case #x: c j`,其中 $x$ 为测试用例编号(从 1 开始),$c$ 是将 $\mathbf{C}$ 中所有问号替换为数字后的结果,$j$ 是将 $\mathbf{J}$ 中所有问号替换为数字后的结果,使得 $c$ 和 $j$ 所表示的整数的绝对差值最小。如果有多个解的绝对差值相同,选择 $c$ 最小的解;如果 $c$ 也相同,则选择 $j$ 最小的解。

说明/提示

**样例解释** 在样例第 4 组中,注意答案不能是 15 10;该方案虽然绝对差值最小,但 Coders 队得分不是最小的。也不能是 05 10;该方案虽然绝对差值和 Coders 队得分都最小,但 Jammers 队得分不是最小的。 **限制条件** - $1 \leqslant \mathbf{T} \leqslant 200$。 - $\mathbf{C}$ 和 $\mathbf{J}$ 长度相同。 **小数据集(测试集 1 - 可见)** - $1 \leqslant \mathbf{C}$ 和 $\mathbf{J}$ 的长度 $\leqslant 3$。 **大数据集(测试集 2 - 隐藏)** - $1 \leqslant \mathbf{C}$ 和 $\mathbf{J}$ 的长度 $\leqslant 18$。 翻译由 GPT4.1 完成。