题面
题目描述
比赛中记分牌上的得分数,由标有数字 ~ 的 类卡片组合而成,例如得分 由两张标有 的卡片和一张标有 的卡片组合而成。
然而,在一场比赛前,粗心的记分员只拿了包含 在内的 类卡片(假定每类卡片数目无限)。为了不延误比赛,记分员决定用这 类卡片表示比赛分数,表示规则为:按从小到大的顺序,用第 个能以这 类卡片表示的十进制数代表得分 i,其中 。例如,若所带卡片只有 四类,则可组合成的十进制数从小到大分别为 ,依次分别对应于得分 。
当这 类卡片所组合成数字的位数很多时,记分员自己也不知道到底现在分数是多少,请你编写程序帮助他/她计算准确的得分。其次,比赛还有一个关键得分 ,记分员还想知道得分为 时记分牌上的数字会是多少。
输入格式
第一行为正整数 ,表示目前可用数字卡片的种类数。
第二行为 个各不相同的一位阿拉伯数字,以空格分隔,且其中肯定包含 。表示 种可用的卡片。
第三行为记分牌上的一个非负整数 ,其所有数位均取自第二行给定的 个数字,且最高位非 。
第四行为一个非负整数 ,你需要输出对应记分牌上的数字。
输出格式
两行,第一行为十进制非负整数,对应于 所表示的十进制得分。
第二行为一个非负整数,表示了分数为 时对应的记分牌上的数字,保证此项输出不超过 。
输入输出样例
输入样例 #1
4
0 4 2 7
27
7
输出样例 # 1
7 27
样例说明 #1
所给卡片从小到大排列为 ,对应得分为 。
所以记分牌数字 对应得分为 ,得分 对应记分牌数字为 。
数据规模与约定
对于 的数据, ;
对于 的数据, , ;
对于 的数据, , 。
思路
观察样例可知,卡片的排列可以看作是 进制与 进制间的转换。
故可以使用 std::map
来实现从记分牌与 进制数之间的转换。
将读入的卡片先排序,然后建立映射:
sort(a, a + m);
for (int i = 0; i < m; i++) {
m1[i] = a[i];
m2[a[i]] = i;
}
此处 m1
是从 进制到 「记分牌进制」 的转换, m2
是从 「记分牌进制」 到 进制的转换。
先将读入的 转为 进制数:
reverse(x.begin(), x.end());
for (int i = 0; i < x.size(); i++) {
mx.push_back(m2[x[i] - '0'] + '0');
}
再将这个 进制数转为 进制数:
reverse(mx.begin(), mx.end());
for (int i = 0; i < mx.size(); i++) {
ans1 += (mx[i] - '0') * pow(m, i);
}
综合起来,就是下面这样:
reverse(x.begin(), x.end());
for (int i = 0; i < x.size(); i++) {
ans1 += m2[x[i] - '0'] * pow(m, i);
}
之后输出 ans1
即可。
同样地,对 的处理就是一个逆向过程。
先将读入的 转换为 进制数,再将这个 进制数转换为 「记分牌进制」 数,合并以后就是这样:
while (s) {
ans2.push_back(m1[s % m] + '0');
s /= m;
}
之后输出 ans2
即可。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, s, a[15], ans1 = 0;
string x, ans2;
map<int, int> m1, m2;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> a[i];
}
sort(a, a + m);
for (int i = 0; i < m; i++) {
m1[i] = a[i];
m2[a[i]] = i;
}
cin >> x >> s;
reverse(x.begin(), x.end());
for (int i = 0; i < x.size(); i++) {
ans1 += m2[x[i] - '0'] * pow(m, i);
}
while (s) {
ans2.push_back(m1[s % m] + '0');
s /= m;
}
reverse(ans2.begin(), ans2.end());
cout << ans1 << endl
<< ans2 << endl;
return 0;
}