codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

467B.md (1640B)


      1 Source: https://codeforces.com/problemset/problem/467/B
      2 
      3 B. Fedor and New Game
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 After you had helped George and Alex to move in the dorm, they went to help their friend Fedor play a new computer game «Call of Soldiers 3».
     22 
     23 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 *x**i*. Consider binary representation of *x**i*: if the *j*-th bit of number *x**i* equal to one, then the army of the *i*-th player has soldiers of the *j*-th type.
     24 
     25 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.
     26 
     27 Input
     28 
     29 The first line contains three integers *n*, *m*, *k* (1 ≤ *k* ≤ *n* ≤ 20; 1 ≤ *m* ≤ 1000).
     30 
     31 The *i*-th of the next (*m* + 1) lines contains a single integer *x**i* (1 ≤ *x**i* ≤ 2*n* - 1), that describes the *i*-th player's army. We remind you that Fedor is the (*m* + 1)-th player.
     32 
     33 Output
     34 
     35 Print a single integer — the number of Fedor's potential friends.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 7 3 1  
     43 8  
     44 5  
     45 111  
     46 17
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 0
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 3 3 3  
     59 1  
     60 2  
     61 3  
     62 4
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 3
     69 ```