問題
背景
注意力分散的比格布里奇伯爵经常写错电话号码,因此经常遭到大学事务局的责备。被责备多次后,他终于认识到问题所在,并调查了自己写错的规律,结果发现他非常容易将相邻的 2 两个数字互换着写。当他犯下这个错误时,为了让他能够立即发现,我们为他设计了一个可以轻松计算的检验码。
課題
10 设计一个针对 N 位整数的校验数字。也就是说,满足下列 2 条件的、10 输入 N 位整数并 0 以上 100 输出小于 M 的整数的函数。注意,输入的整数为 0 大于等于 A,10^9 小于 B 的整数时,需要加上前导零。10 视为位数。
- 对相同的输入总是得到相同的输出。
- 相邻 2 当数字不同时,如果将其交换后得到的整数作为输入,将得到与原来不同的输出。
配点
200
入力
输入按以下格式给出。
T a_1 : a_T
1 行中附加校验位的整数数量 T 。 继续 T 行中需附加校验位的整数 a_i 是 在 1 逐行给出。
制約
- 1 ≦ T ≦ 10^5
- a_i 是 您也可以写 0 以上 10^{10} 小于的整数,10 为成为位数而加上了前导零。
- a 元素可能重复,即,i ≠ j 是 i, j 反对 a_i = a_j 注意它可能成为。
出力
输出对应于输入中给定的每个整数的校验位。
採点方式
对于这个问题 8 提供了 个测试用例,每个 25 以满分评分。
每个测试用例中 T 的值如下。
- T = 30, 100, 300, 1000, 3000, 10000, 30000, 100000
各测试用例的判定输出如下确定。
- 如果所附的校验位与题目中示的两个条件矛盾 - WA
- 如果所附的校验位与题目中示的两个条件不矛盾 - AC
- 此时的得分为输出中包含的校验位种类数 k , min(25, max(8 - k, 0)^2) 。
各测试用例独立评分。特别地,即使对相同的整数值在不同测试用例中附加了不同的校验位,也不会立即判定为 WA。
入力例1
6 0000000011 0000000012 0000000013 0000000021 0000000031 0000000011
出力例1
0 0 0 1 1 0