当前位置：首页 > news >正文

UVa 613 Numbers That Count

news 2026/6/29 1:24:59

题目描述

给定一个非负整数nnn，定义其“库存”（inventory\texttt{inventory}inventory）为如下操作的结果：统计nnn的十进制表示中每个数字（000到999）出现的次数，然后按数字从小到大的顺序，将每个出现次数和对应的数字依次拼接成一个新的整数。例如，555314155531415553141中数字111出现222次，333出现111次，444出现111次，555出现333次，因此其库存为211314352113143521131435。若某个数字未出现，则不写入库存。注意，库存中的每个“计数”可能不止一位（如100000000000100000000000100000000000有121212个000，库存为120111201112011）。

一个数称为“自库存数”（self-inventorying\texttt{self-inventorying}self-inventorying），如果它等于自己的库存。若经过jjj次迭代后首次出现自库存数，则称该数“经过jjj步后自库存”。若迭代序列进入一个长度k≥2k \ge 2k≥2的循环，则称该数“进入长度为kkk的库存循环”。若经过151515次迭代后仍未出现上述三种情况，则判定为“无法在151515次迭代内分类”。

本题要求对每个输入的非负整数（最多808080位）进行判断，输出相应的分类信息。

输入格式

输入包含若干个非负整数，每行一个，每个整数最多808080位，没有前导零。输入以一行-1结束。

输出格式

对于每个输入整数nnn，输出以下五种消息之一：

n is self-inventorying
n is self-inventorying after j steps
n enters an inventory loop of length k
n is self-inventorying after 15 steps（若第151515次迭代后恰好为自库存数）
n can not be classified after 15 iterations

其中jjj和kkk为相应的正整数。

样例

输入

22 31123314 314213241519 21221314 111222234459 -1

输出

22 is self-inventorying 31123314 is self-inventorying 314213241519 enters an inventory loop of length 2 21221314 is self-inventorying after 2 steps 111222234459 enters an inventory loop of length 2

题目分析

本题的核心是模拟库存迭代过程，并检测序列中出现的固定点或循环。由于每次迭代后的数字长度不会超过原数字长度的两倍（因为每个出现数字对应一个计数，计数最多为原长度，拼接后长度约为2×102 \times 102×10，对于808080位的输入，迭代结果长度最多160160160位，但实际更小），状态空间有限，迭代151515次足以判断循环或自库存。参考代码中，循环检测使用map<string,int>\texttt{map<string,int>}map<string,int>记录每个字符串首次出现的步骤编号，一旦某个字符串重复出现，即可根据重复出现的位置判断是自库存、经过若干步自库存，还是进入长度大于111的循环。

需要特别注意两种边界情况：

若重复出现的字符串就是起始字符串（start == 0），且循环长度为111，则为自库存数。
若重复出现的字符串不是起始串（start > 0），且循环长度为111，则说明从第start步开始进入自库存数，应输出“经过start步后自库存”。
若循环长度>1> 1>1，则输出进入循环。

若迭代151515次后未出现重复，还需检查第151515次迭代后的字符串是否为自库存数（即与下一步相同），否则输出无法分类。

解题思路

实现库存函数getNext(string &number)：
- 使用map<char, int>统计number中每个字符（数字）的出现次数。
- 遍历map（按键自动升序），对于每个键值对(digit, count)，先将count转为字符串，再追加digit字符，拼接得到下一个字符串。
主循环处理每个输入：
- 读入一个字符串number（可能较大，用string存储）。
- 用map<string, int> cache记录每个出现的字符串及其首次出现的步骤编号（从000开始）。
- 循环iii从111到151515：
  - 计算next = getNext(number)。
  - 若next已在cache中，则根据start = cache[next]和loop = i - start判断：
    - 若loop > 1：输出进入长度loop的循环。
    - 若start == 0：输出自库存数。
    - 否则：输出经过start步后自库存。
    - 标记为已确定，跳出循环。
  - 否则，将next记录为第i步出现，并将number更新为next。
- 若循环结束时仍未确定：
  - 计算next = getNext(number)（即第161616次迭代）。
  - 若number == next，则输出“经过151515步后自库存”。
  - 否则输出“无法在151515次迭代内分类”。
输出格式：按题目要求精确输出消息，注意空格和标点。

复杂度分析

每次库存操作需遍历字符串并统计字符出现次数，时间复杂度O(L)O(L)O(L)，其中LLL为当前字符串长度，最多约160160160。
迭代次数固定为151515，因此每个输入的处理时间为常数。
空间复杂度O(15×L)O(15 \times L)O(15×L)，用于存储历史字符串。

代码实现

// Numbers That Count// UVa ID: 613// Verdict: Accepted// Submission Date: 2016-08-31// UVa Run Time: 0.020s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;stringgetNext(string&number){map<char,int>digits;for(intj=0;j<number.length();j++)digits[number[j]]++;string next;for(autodigit:digits){next+=to_string(digit.second);next+=digit.first;}returnnext;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string number;while(cin>>number,number!="-1"){cout<<number<<' ';booldeterminated=false;map<string,int>cache={{number,0}};for(inti=1;i<=15;i++){string next=getNext(number);if(cache.find(next)==cache.end())cache[next]=i;else{determinated=true;intstart=cache[next],loop=i-cache[next];if(loop>1)cout<<"enters an inventory loop of length "<<loop<<'\n';elseif(start==0)cout<<"is self-inventorying\n";elsecout<<"is self-inventorying after "<<start<<" steps\n";break;}number=next;}if(!determinated){string next=getNext(number);if(number==next)cout<<"is self-inventorying after 15 steps\n";elsecout<<"can not be classified after 15 iterations\n";}}return0;}