UVa 433 Bank (Not Quite O.C.R.)

寂静山林

136人浏览 · 2026-06-09 09:23:42

寂静山林 · 2026-06-09 09:23:42 发布

题目描述

题目要求根据七段数码管的 $ASCII\texttt{ASCII}$ 表示还原银行账号。每个账号由 $9$ 位数字组成，且满足校验和公式：
$(d_1 + 2 \times d_2 + 3 \times d_3 + \dots + 9 \times d_9) \bmod 11 = 0$
其中 $d_9$ 是最左边的数字， $d_1$ 是最右边的数字（即数字从右向左编号）。输入为扫描后的图像，可能包含缺失的线段（即某些本该亮的线段缺失），但不会包含多余的线段。假设：

若输入直接表示一个有效账号，则其为原始账号；
否则，最多有一位数字存在缺失线段（即只有一个数字被损坏）。

需要输出还原后的 $9$ 位数字，若无解输出 failure，若多解输出 ambiguous。

输入格式

第一行一个整数 $N$ ，表示测试用例的数量。每个测试用例由 $3$ 行组成，每行 $27$ 个字符，表示 $9$ 个数字的七段显示（每个数字占 $\times 3$ 的网格）。字符为 |、_ 或空格。

输出格式

对于每个测试用例，输出一行：若唯一确定则输出 $9$ 位数字，若无解则输出 failure，若多解则输出 ambiguous。

样例

输入

4
   _  _  _  _  _  _  _  _ 
|_||_||_||_||_||_||_||_||_|
  |  |  |  |  |  |  |  |  |

   _  _  _  _  _  _  _  _ 
|_||_||_||_||_||_||_||_||_|
  |  |  |  |  |  |  |  |  |

   _  _  _  _  _  _  _  _ 
|_||_||_||_||_||_||_||_||_|
  |  |  |  |  |  |  |  |  |

   _  _  _  _  _  _  _  _ 
|_||_||_||_||_||_||_||_||_|
  |  |  |  |  |  |  |  |  |

输出

123456789
ambiguous
failure
878888888

题目分析

本题的核心是将七段数码管的 $ASCII\texttt{ASCII}$ 表示转换为二进制编码，然后根据编码匹配数字，并处理可能的损坏情况。

七段编码

每个数字在 $\times 3$ 网格中显示，共 $9$ 个位置（ $3$ 行 $×3\times 3$ 列）。将每个位置是否有笔画映射为二进制位（ $1$ 表示有笔画， $0$ 表示无）。标准数字的编码如下（按行主序排列，参考代码中的 digits 数组）：

数字	编码
$0$	$010101111$
$1$	$000001001$
$2$	$010011110$
$3$	$010011011$
$4$	$000111001$
$5$	$010110011$
$6$	$010110111$
$7$	$010001001$
$8$	$010111111$
$9$	$010111011$

损坏处理

由于损坏只能导致线段缺失（即 $1$ 变为 $0$ ），不能产生多余线段。因此，对于一个损坏的数字，其编码必须是某个标准数字编码的子集（按位与等于原编码）。参考代码中预先生成了每个数字所有可能的损坏编码（通过递归清除位得到），存入 garbledNumbers。

校验和

校验和公式从右向左计算。设 $d_1$ 是最右边（个位）的数字， $d_9$ 是最左边的数字。计算 $11=0\sum_{i=1}^{9} i \times d_i \bmod 11 = 0$ 。

算法步骤

对于每个测试用例：

读取 $3$ 行，每行 $27$ 个字符。将空格视为 $0$ ，非空格视为 $1$ ，得到每个数字的 $9$ 位二进制编码。
尝试将每个数字的编码与标准编码匹配：
- 若匹配成功，记录该数字。
- 若匹配失败，记录该位置为损坏（garbledIndex），并记录损坏后的编码值。
若存在损坏位置：
- 遍历 $0$ 到 $9$ 的所有数字，检查该数字的损坏编码集合是否包含当前损坏编码。若是，则将该位置替换为该数字，并检查校验和。
- 统计满足校验和的数字个数。若唯一解则输出，若多解则输出 ambiguous，若无解则输出 failure。
若无损坏位置：
- 直接检查校验和。若成立，则输出该数字串。
- 若不成立，则需要考虑可能有一位数字被损坏（但扫描时未缺失任何线段？题目保证最多一位损坏，但此情况意味着虽然编码完整，但实际数字可能被误识别）。此时需要尝试将每一位数字替换为其他可能的数字（根据预先生成的候选列表 candidates），检查校验和，统计解的数量。

候选列表说明

参考代码中的 candidates 数组定义了每个数字可能被误识别为的其他数字。例如，"034789" 表示数字 $0$ 可能被误认为 $0$ 、 $3$ 、 $4$ 、 $7$ 、 $8$ 、 $9$ 等。这实际上是所有与当前数字的编码相差不超过一个损坏（即 $1$ 变 $0$ ）的数字集合。

复杂度分析

每个测试用例只需检查最多 $\times 10$ 种可能性，完全可接受。

代码实现

// Bank (Not Quite O.C.R.)
// UVa ID: 433
// Verdict: Accepted
// Submission Date: 2016-07-19
// UVa Run Time: 0.000s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

vector<string> digits = {
    "010101111", "000001001", "010011110", "010011011", "000111001",
    "010110011", "010110111", "010001001", "010111111", "010111011"
};

vector<set<int>> garbledNumbers(10);
void backtrack(int indexer, int number)
{
    for (int i = 1, mask = 1; i <= 9; i++, mask <<= 1)
        if ((number & mask) > 0)
        {
            int next_number = number ^ mask;
            garbledNumbers[indexer].insert(next_number);
            backtrack(indexer, next_number);
        }
}

bool checksum(vector<int> &accountDigits)
{
    int sum = 0;
    for (int i = 9; i >= 1; i--)
        sum += i * accountDigits[9 - i];
    return (sum % 11) == 0;
}

void display(vector<int> answer, int countOfSolutions)
{
    if (countOfSolutions >= 2)
        cout << "ambiguous\n";
    else if (countOfSolutions == 0)
        cout << "failure\n";
    else
    {
        for (auto digit : answer)
            cout << digit;
        cout << '\n';
    }
}

int main(int argc, char *argv[])
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    map<int, int> numbers;
    for (int i = 0; i <= 9; i++)
    {
        bitset<9> converter(digits[i]);
        int value = (int)converter.to_ulong();
        numbers[value] = i;
        backtrack(i, value);
    }

    string line; getline(cin, line); int cases = stoi(line);

    for (int i = 1; i <= cases; i++)
    {
        // read the segment presentation of digit
        vector<string> account(3);
        for (int j = 0; j < 3; j++)
        {
            getline(cin, line);
            string segments;
            for (int k = 0; k < line.length() && k < 27; k++)
                segments += (line[k] == ' ' ? '0' : '1');
            while (segments.length() < 27) segments += '0';
            account[j] = segments;
        }

        // find if garbled number exist or not
        vector<int> accountDigits;

        int garbledIndex = -1, garbledValue;
        for (int j = 0; j < 9; j++)
        {
            string digitText;
            for (int k = 0; k < 3; k++) digitText += account[k].substr(j * 3, 3);

            bitset<9> binary(digitText);
            int value = (int)binary.to_ulong();

            if (numbers.find(value) != numbers.end())
                accountDigits.push_back(numbers[value]);
            else
            {
                accountDigits.push_back(-1);
                garbledIndex = j;
                garbledValue = value;
            }
        }

        // one digit is garbled
        int countOfSolutions = 0;
        vector<int> answer(accountDigits);

        if (garbledIndex != -1)
        {
            for (int j = 0; j <= 9; j++)
                if (garbledNumbers[j].find(garbledValue) != garbledNumbers[j].end())
                {
                    accountDigits[garbledIndex] = j;
                    if (checksum(accountDigits))
                    {
                        answer.assign(accountDigits.begin(), accountDigits.end());
                        countOfSolutions++;
                    }
                    if (countOfSolutions >= 2) break;
                }
                
            display(answer, countOfSolutions);
            continue;
        }

        // check the account is valid or not
        if (checksum(accountDigits))
        {
            display(answer, 1);
            continue;
        }

        // find others solutions
        vector<string> candidates = {"8", "034789", "8", "89", "89", "689", "8", "0389", "8", "8"};
        vector<int> backup(accountDigits);
        countOfSolutions = 0;

        for (int j = 0; j < 9; j++)
        {
            for (auto ascii : candidates[backup[j]])
            {
                accountDigits[j] = ascii - '0';
                if (checksum(accountDigits))
                {
                    answer.assign(accountDigits.begin(), accountDigits.end());
                    countOfSolutions++;
                }

                if (countOfSolutions >= 2)
                    goto skip;
            }
            accountDigits.assign(backup.begin(), backup.end());
        }

        skip:
        display(answer, countOfSolutions);
    }

    return 0;
}

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

混合储能永磁同步电机驱动系统仿真模型机理与特性（Simulink仿真实现）

混合储能永磁同步电机驱动系统仿真模型机理与特性解析。

AtomGit开源社区

【创新未发表】基于杜鹃优化算法的分时电价需求响应与综合能源系统双层调度模型（Matlab代码实现）

在 “双碳” 发展战略全面推进的背景下，风电、光伏等清洁能源规模化并网应用已成为能源转型的主流趋势。综合能源系统作为整合多种能源品类、实现多设备协同运行的新型能源载体，能够充分发挥多能互补、梯级利用的优势，有效承接高比例可再生能源接入。但风光能源固有的间歇性、随机性与反调峰特性，使得系统源荷双侧波动加剧，电网负荷峰谷差值不断扩大，弃风、弃光现象频发，不仅增加了系统调度运行压力，也制约了清洁能源的高