Skip to content

Instantly share code, notes, and snippets.

@thameemk612 thameemk612/7
Created Oct 18, 2018

Embed
What would you like to do?
Manu needs money and decides to open his uncle’s locker. He knows that the passcode of the locker consists of n numbers, and every number is a 0 or 1. Manu has made m attempts to enter the code. After each attempt the system told him in how many position stand the right numbers. It is not said in which positions the wrong numbers stand. Manu has been so unlucky that he hasn’t entered the code where would be more than 5 correct numbers. Now Manu is completely bewildered: he thinks there’s a mistake in the system and it is self-contradictory. Calculate how many possible code variants are left that do not contradict the previous system responses.
Input The first input line contains two integers n and m which represent the number of numbers in the code and the number of attempts made by Manu. Then follow m lines, each containing space-separated si and ci which correspondingly indicate Manu’s attempt (a line containing n numbers which are 0 or 1) and the system’s response (an integer from 0 to 5 inclusively).
Output Print the single number which indicates how many possible code variants that do not contradict the m system responses are left.
Input Format
6 2 000000 2 010100 4
Constraints
(6 ≤ n ≤ 35, 1 ≤ m ≤ 10)
Output Format
6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.