HBC24730msc的无向图,二分,分治[USACO 2010 Mar B]MasterMind题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

Jessie was learning about programming contests at Bessie's knee."Oh yes," Bessie nodded sagely. "Here's a classic.". MasterMind is a classic two player game. One of the players is the 'codemaker'; she picks a four digit secret number S (1000

Jessie was learning about programming contests at Bessie's knee. "Do they play games?" she asked. "Oh yes," Bessie nodded sagely. "Here's a classic." MasterMind is a classic two player game. One of the players is the 'codemaker'; she picks a four digit secret number S (1000 <= S <= 9999). The other player is the 'codebreaker' who repeatedly guesses four digit numbers until she solves the code. The codemaker provides feedback that comprises two integers for each codebreaker guess G_i G i ​ (1000 <= G_i G i ​ <= 9999). For each codebreaker guess, the codemaker's feedback comprises two integers: * The first integer C_i C i ​ (0 <= C_i C i ​ <= 4) specifies how many of the guess's digits are correct and in their correct location in the secret number * The second integer W_i W i ​ (0 <= W_i W i ​ <= 4- C_i C i ​ ) specifies how many of the remaining digits (i.e., those not described by C_i C i ​ ) are correct but in the wrong location. For example, suppose codemaker's secret number is 2351. If codebreaker guesses 1350, the codemaker provides the feedback "2 1", since 3 and 5 are in correct locations in the number, and 1 is in the wrong location. As another example, if the secret number is 11223 (in a five-digit version of mastermind) and the guess is 12322, then the feedback would be "2 2". Below is a sample game where the secret number is 2351: Correct digits in correct location | Correct digits in wrong location Guess | | 3157 1 2 1350 2 1 6120 0 2 2381 3 0 2351 4 0 For this task, you are given N (1 <= N <= 100) guesses with their feedback in the middle of a game. You are asked to output the smallest four digit number which can be a candidate for codemaker's secret code (i.e., which satisfies all the constraints). If there are no such numbers, output "NONE" (without the quotes).

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC24730msc的无向图 二分 分治[USACO 2010 Mar B]MasterMind题解