足球锦标赛

简介

题目来源:「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛

ECNU 足球锦标赛采用了最传统的计分牌来计分。每进一个球,计分员给对应的队要翻牌,使得计分板上显示的数加一。

如上图所示,计分板上的每一位都按顺序挂了 $0$ 到 $9$ 这 $10$ 个牌子,所以可以表示 $000$ 至 $999$。当其中一个队的得分从 $010$ 变成 $011$ 时,计分员只要将最后一位的最前面的牌子向后翻即可,共需翻动一块牌子;当得分从 $019$ 变成 $020$ 是,由于 $9$ 后面已经没有牌子了,所以计分员要将 $0$ 到 $9$ 全部翻到前面,并将倒数第二位的牌子 $1$ 翻到后面,所以共需翻动 $10$ 块牌子。

现场的计分牌和图中所示还是存在差异的,现场的计分牌会很大,很重,所以翻每块牌子都要消耗 $1$ 点体力。

你是计分员,现在比赛还剩下最后十分钟。现在有一个预言家告诉你在这十分钟里,双方得分共计多少;但他没有告诉你双方得分各是多少。所以你想要知道你要花费的体力值最多是多少。

Input

第一行给出数据组数 $T$ $(1≤T≤1 000)$。接下来对于每组数据有两行:

第一行是两个三位数 $A,B$ $(0≤A,B≤999)$(含前导 0),形如 $001$,$013$,$123$,表示双方现在的得分。

第二行是一个整数 $K$ $(0≤K≤min\lbrace 999−A,999−B\rbrace$,表示双方在最后十分钟的得分之和。

Output

对于每组数据,输出 Case x: y。其中x是从 $1$ 开始的测试数据编号y是一个整数,表示花费体力最多是多少。

Examples

  • input
1
2
3
4
5
2
009 009
2
001 003
2
  • output
1
2
Case 1: 20
Case 2: 2

Note

样例 1 解释:有三种情况。

甲方(前者)得 2 分,乙方(后者)得 0 分;甲方要翻 10+1=11 次。
甲方和乙方各得 1 分,共要翻 10+10=20 次。
乙方得 2 分,同样翻 11 次。
所以最多要翻 20 次。

思路

  • 枚举双方分别得分,然后模拟翻牌过程计算一下就好了。

  • 注意每一个目标所需要的体力要一次性计算之后记录一下,重复计算可能会超时。
    (官方题解是这么写的……大概可以打个表预处理一下,但是似乎直接做也水过了orz)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int solve(int ta, int tb)
{
int ans;
int a[3], b[3];
a[0] = ta % 10;
a[1] = ta / 10 % 10;
a[2] = ta / 100;
b[0] = tb % 10;
b[1] = tb / 10 % 10;
b[2] = tb / 100;
ans = a[0] - b[0] + 19 * (a[1] - b[1]) + 199 * (a[2] - b[2]);
return ans;
}

int main()
{
int numa, numb;
int t;
int kase=0;
cin >> t;
while (t--)
{
cin >> numa >> numb;
int ans = 0;
int n;
cin >> n;
for (int i = 0; i <= n; i++)
ans = max(ans, solve(numa + i, numa) + solve(numb + n - i, numb));
cout <<"Case "<<++kase<<": "<< ans << endl;
}
return 0;
}
捐助作者
0%