This just won't work

[Kalcor]

First of all, here is the question:

The game has (m + 1) players and n types of soldiers in total. Players «Call of Soldiers 3» are numbered form 1 to (m + 1). Types of soldiers are numbered from 0 to n - 1. Each player has an army. Army of the i-th player can be described by non-negative integer xi. Consider binary representation of xi: if the j-th bit of number xi equal to one, then the army of the i-th player has soldiers of the j-th type.

Fedor is the (m + 1)-th player of the game. He assume that two players can become friends if their armies differ in at most k types of soldiers (in other words, binary representations of the corresponding numbers differ in at most k bits). Help Fedor and count how many players can become his friends.

Input
The first line contains three integers n, m, k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000).

The i-th of the next (m + 1) lines contains a single integer xi (1 ≤ xi ≤ 2n - 1), that describes the i-th player's army. We remind you that Fedor is the (m + 1)-th player.

Output
Print a single integer — the number of Fedor's potential friends.

Examples

input
7 3 1
8
5
111
17

output
0

input
3 3 3
1
2
3
4

output
3

I seriously tried so much with this problem, the code seems to work fine until there is a duplicate in the input it just messes up, but MAYBE there is something I don't understand in the problem but here is what's driving me crazy, first here is the code:

#include <bits/stdc++.h>


#define fl(n)    for(int i = 0; i < n; i++)

#define Max(a,b) ( (a) > (b) ? (a) : (b))
#define Min(a,b) ( (a) < (b) ? (a) : (b))

#define u    unsigned
#define ll   long long
#define nl   endl
#define pb push_back
#define mp make_pair


#define EPS  1e-9
#define INF  1e9
#define init -1e9


using namespace std;

long dtob(long n) {
    if(n!=0){

        return n%2+(10*dtob(n/2));
   }else{
        return 0;
   }
}

bool check(ll n, ll x, ll k){
int bits = (n ^ x);
int count = 0;

//bits = dtob(bits);
while(bits){
    count += bits & 1;
    bits >>= 1;
}
if(count <= k && count != 0) return true;

return false;
}

//int bins[1048575+1];
int main()
{
    int n,m,k;
    cin >> n >> m >> k;

    int a[m+1];
    for(int i = 0; i < m+1; i++)
    cin >> a[i];

    int fedor = a[m];

    int count = 0;
    for(int i = 0; i < m+1; i++)
    {
        if(check(a[i], fedor, k))
        {
            //cout << a[i] << " ";
            count++;
        }
    }
    cout << count;

    return 0;
}

Now what's driving me crazy is that if I change the following 2 lines in the code, the code works

if(count <= k && count != 0) return true; //line 41
for(int i = 0; i < m+1; i++) //line 59 

to:

if(count <= k) return true;
//and
for(int i = 0; i < m; i++)

Now what drives me crazy is that, doing this RUINS what the question asked for if I am not mistaken!!

He assume that two players can become friends if their armies differ in at most k types of soldiers (in other words, binary representations of the corresponding numbers differ in at most k bits).

Using what I changed above just totally makes this statement irrelevant AND for some weird reason the code gets accepted by the system.. can someone tell me if there is something I am missing or if it's an error in typing the question from their side?

[keskiverto]

The loop. If you compare Fedor against Fedor, difference is 0 and you get one friend, even if there are no other players (such a narcissist). That was not in the question. The question is about the other m players. Hence the i < m is the logical condition.


The if. Two armies can have identical composition. 0 bit difference. 0 is "at most k". Your && count != 0 says that they cannot be friends.


Let me guess, you had the i < m+1 in the loop, always got one too many friends, and decided to counter that in the check.


Other notes:
* Your code includes <bits/stdc++.h> for no obvious reason (but doesn't include <iostream>).

* Avoid preprocessor macros. C had to use them, but C++ has type aliases, constants, etc.

* Line 56 is not standard C++. The size of a static array must be known by the compiler during compilation. The value of 'm' is known at that time. Every run of the program can have different m. Use std::vector instead. It is dynamic.

[Kalcor]

@keskiverto

Wait so you're saying it's ok to have no difference in bits at all ? and that would satisfy the "at most k bits" condition? I thought it means they had to differ lol.. is that why the question says this part:

Types of soldiers are numbered from 0 to n - 1.

So the diff in representation of the bits output can be 0 and that would count as type 0 ?

But then

Consider binary representation of xi: if the j-th bit of number xi equal to one, then the army of the i-th player has soldiers of the j-th type.

If fedor is number 10 and there is another number 10 in the list take this list for example

4 7 4
9
10
5
12
4
12
7
10

Fedor is number 10 and there is another 10 in the list, and 10 ^ 10 is 0 and that means there is no "set bits" , so why do we consider him a friend? (the answer of this list is 7, so it includes the 10)

if the j-th bit of number xi equal to one

There is no 1's in this case :/

[keskiverto]

          A B C D E
berserks  x x   x
swordmen  x   x x
pikemen       x   x
archers   x   x x
knights     x     x

two players can become friends if their armies differ in at most k types of soldiers

Lets use k=2. Which of the players B, C and D can become friends of player A?

A has swordmen and archers, but B does not. That is two differences. Furthermore, B has knights, but A has not. Three differences in total.

A has berserks but C does not. C has pikemen but A does not. Differ in two types.

The armies of A and D differ in no type of soldiers.

The E's army differs in every type from A. Five differences.


Who could you befriend, A?