#CF467B. Fedor 和新游戏
Fedor 和新游戏
CF467B Fedor and New Game
题目描述
在你帮 George 和 Alex 搬进宿舍之后,他们去帮他们的朋友 Fedor 玩一款新的电脑游戏《Call of Soldiers 3》。
游戏总共有 个玩家,以及 种士兵类型。玩家编号为 到 ,士兵类型编号为 到 。每个玩家都有一支军队,第 个玩家的军队可以用一个非负整数 描述:若 的二进制表示中第 位为 ,则第 个玩家的军队中拥有编号为 的士兵类型。
Fedor 是第 个玩家。他认为,如果两名玩家的军队至多有 种士兵类型不同(也就是说,两个数的二进制表示至多有 位不同),那么这两名玩家就可以成为朋友。请你帮助 Fedor 计算有多少名玩家可以成为他的朋友。
输入格式
第一行输入三个整数 $n,m,k \left(1 \leqq k \leqq n \leqq 20;\ 1 \leqq m \leqq 1000\right)$ 代表士兵类型数量、除 Fedor 外的玩家数量,以及成为朋友所允许的不同士兵类型数量的上限。
此后 行,第 行输入一个整数 代表第 个玩家的军队。最后一行为 Fedor 的军队。
输出格式
在一行上输出一个整数,代表可以成为 Fedor 朋友的玩家人数。
测试样例
7 3 1
8
5
111
17
0
样例 1 解释
Fedor 的军队为 ,其二进制表示为 。其余三名玩家的军队分别为 、、,它们与 的二进制表示分别有 位不同,都超过了 ,因此没有玩家可以成为 Fedor 的朋友,答案为 。
3 3 3
1
2
3
4
3
样例 2 解释
Fedor 的军队为 ,其二进制表示为 。其余三名玩家的军队分别为 、、,它们与 的二进制表示分别有 位不同,都不超过 ,因此三名玩家都可以成为 Fedor 的朋友,答案为 。