#P3374. [Usaco2004 Mar]Special Serial Numbers 特殊编号

    ID: 2564 传统题 1000ms 512MiB 尝试: 23 已通过: 11 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划数位 DP记忆化搜索枚举与搜索可行性剪枝构造与建模序列构造CF1700Orange

[Usaco2004 Mar]Special Serial Numbers 特殊编号

[USACO 2004 Mar] Special Serial Numbers 特殊编号

题目描述

每头新出生的奶牛会获得一个 NN 位的正整数编号,编号随着出生顺序递增。

如果某个数字在编号中出现的次数严格超过编号位数的一半,这就是一个特殊编号。例如,2352223522 是特殊编号,因为 22 出现了三次;1234212342 不是特殊编号。

普通奶牛会找出生时间比自己晚的特殊奶牛中最年长的一头。给定一头奶牛的编号:如果它已经是特殊编号,就输出它本身;否则输出大于它的最小 NN 位特殊编号。

输入格式

从标准输入读入一行一个正整数,表示给定的编号。

输出格式

向标准输出输出一行一个整数,表示按上述规则选出的编号。

1234
1311

样例解释

13111311 中的 11 出现三次,超过四位的一半;11991199 的 11 和 99 都恰好出现两次,所以 11991199 不是特殊编号。

数据范围与约定

编号位数 NN 满足 1≤N≤1001\le N\le 100。