题解：UVA11723 Numbering Roads

Lonely_Peak · 2025-03-24 18:50:17 · 题解

题目大意

简述

在一个国家中，街道没有名字，而是用数字和字母后缀来命名。数字是分配给街道的整数，后缀是单个字母（A 到 Z）。数字应该是唯一的，但由于分配的整数数量（N）可能少于街道数量（R），因此需要通过添加后缀来确保街道名称的唯一性。

给定街道数量（R）和分配的整数数量（N），计算在所有可能的命名方案中，所需的最小后缀数量（D）。如果无法满足命名需求（即即使使用所有可能的后缀也无法分配唯一名称），则输出 impossible。

输入

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

输出

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

题目分析

这道题对算法的要求并不高，找到分配规律即可。

如果每个街道可以分配一个唯一的数字（即 N \geq R ），则不需要后缀，直接使用数字即可。如果 N<R，则需要为某些数字添加后缀以确保名称唯一。每个数字最多可以分配 27 个名称（数字本身和 26 个后缀，如 1, 1A, 1B, ..., 1Z）。

那么，如果 N \geq R，则不需要后缀，直接输出 0。如果 N < R 且 N \times 27 < R ，则即使使用所有可能的数字和后缀组合也无法满足需求，输出 impossible（因为每个数字最多支持 27 个名称）。

所以，对于编码，我们只需要几个 if 来判断它是否满足要求即可。

注意：输出时每一行需要输出样例编号，格式为 Case N: Ans。

参考代码

#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;
}

~ 完结撒花 ~