专栏文章

题解：UVA11723 Numbering Roads

LLonely_Peak七月雪
UVA11723题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miptl05q
此快照首次捕获于
2025/12/03 17:43
3 个月前
此快照最后确认于
2025/12/03 17:43
3 个月前
查看原文

题目大意

简述

在一个国家中，街道没有名字，而是用数字和字母后缀来命名。数字是分配给街道的整数，后缀是单个字母（AA 到 ZZ）。数字应该是唯一的，但由于分配的整数数量（NN）可能少于街道数量（RR），因此需要通过添加后缀来确保街道名称的唯一性。
给定街道数量（RR）和分配的整数数量（NN），计算在所有可能的命名方案中，所需的最小后缀数量（DD）。如果无法满足命名需求（即即使使用所有可能的后缀也无法分配唯一名称），则输出 impossible。

输入

多组测试数据，每组包含两个整数 RR 和 NN（0<N0 < N，R<10001R < 10001）。

输出

对于每组数据，输出用例编号和最小后缀数量 DD，若无法实现则输出 impossible。

题目分析

这道题对算法的要求并不高，找到分配规律即可。
如果每个街道可以分配一个唯一的数字（即 N≥RN \geq R），则不需要后缀，直接使用数字即可。如果 N<RN<R，则需要为某些数字添加后缀以确保名称唯一。每个数字最多可以分配 2727 个名称（数字本身和 2626 个后缀，如 1,1A,1B,...,1Z1, 1A, 1B, ..., 1Z）。
那么，如果 N≥RN \geq R，则不需要后缀，直接输出 0。如果 N<RN < R 且 N×27<RN \times 27 < R，则即使使用所有可能的数字和后缀组合也无法满足需求，输出 impossible（因为每个数字最多支持 2727 个名称）。
所以，对于编码，我们只需要几个 if 来判断它是否满足要求即可。
注意：输出时每一行需要输出样例编号，格式为 Case N: Ans。

参考代码

CPP
#include<bits/stdc++.h>
#define int long long
#define fast_running ios::sync_with_stdio(false),std::cin.tie(0)
using namespace std;

signed main() {
	fast_running;
	int r, n, num = 0;
	while (cin >> r >> n) {
		if (r == 0 && n == 0) break;
		cout << "Case " << ++num << ": ";   //输出样例编号
		if (r > n * 27) cout << "impossible\n"; //即使使用所有可能的数字和后缀组合也无法满足需求，输出 impossible
		else if (r <= n) cout << "0\n";  //不需要后缀，直接使用数字即可
		else {
			if (r % n == 0) cout << r / n - 1 << '\n';
			else cout << r / n << '\n';
		}
	}
	return 0;
}
~ 完结撒花 ~

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...