← 返回题目列表

AtCoder · utpc2014_f

F. 校验位

中文机器翻译题面 查看原题

問題

背景

注意力分散的比格布里奇伯爵经常写错电话号码,因此经常遭到大学事务局的责备。被责备多次后,他终于认识到问题所在,并调查了自己写错的规律,结果发现他非常容易将相邻的 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