Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Cow Imposters
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1927Accepted: 514


FJ no longer uses the barbaric custom of branding to mark the cows that he owns. Instead, he creates a binary code of B (1 <= B <= 16) bits for each cow and embosses it onto a metal strip that is fastened to each cow's ear.

The cows have taken in a stray and wish to create an ID strip for it. Unknown to FJ, they have created a machine that can make a new ID strip by combining two existing ID strips using the XOR operation (ID strips are not consumed by this machine, and the same ID strip can be used for both inputs).

The cows wish to create a specific ID strip for the stray or at least get as close to a desired ID as possible -- with the smallest possible number of bits differing between the goal ID strip and the best possible new ID strip.

Given a set of E (1 <= E <= 100) existing ID strips, the goal ID strip, and a large number of blank ID strips to hold intermediate results, calculate the closest possible ID strip that can be created from the existing ID strips.

If more than one ID is closest, choose the one that can be created in the fewest steps. If there is still a tie, choose the `smallest' ID (i.e., if you sorted all the IDs, the one that is first).


* Line 1: Two space-separated integers: B and E.

* Line 2: The goal ID string, represented as a string of B 0's and 1's (with no spaces).

* Lines 3..E+2: Each line contains an existing ID string, represented as a string of B 0's and 1's (with no spaces).


* Line 1: A single integer that is the minimum number of steps required to create the best possible ID strip.

* Line 2: A single line with the best possible ID strip that can be created from the E existing ID strips

Sample Input

5 3

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator