Reductive elimination

Catalog

One , The rules of the game

Two , Definition of terms

3、 ... and , Greedy strategy

Four , Violence strategy

---

One , The rules of the game

In fact, the essence of this game is , There are some boxes , There are several balls of various colors in each box , Every election 2 A box , Take out the balls of the same color among them , Finally, you can take all of them .

Two , Definition of terms

The right state ： After a series of operations, the state that can be completely eliminated .

3、 ... and , Greedy strategy

（1） Greedy strategy one , Take the largest number each time , Whether there must be a number that can be mutually reduced with this number , So that the mutual covenant is still in the correct state ？

Is the answer , We are the first 7 Guan can easily find such an example ,4 6 6 3 3

  

  This example does not violate , because 6 You can talk to 4 Mutual covenant , Then it's still in the right state .

But the inspiration from this example is , among 2 The power of 4 2 2 1 1, We found that the largest number in the two sets of data is different , This allows you to design cross use cases ：

60, 150, 10, 9

In this case , Must be 9 And other numbers should be mutually reduced first , So the greedy strategy is not tenable .

（2） Greedy strategy two , Each time you get the most prime factor （ Repeated weighing ） Number of numbers , Whether there must be a number that can be mutually reduced with this number , So that the mutual covenant is still in the correct state ？

Repeated weighing means , such as 12 Yes 3 A quality factor , Namely 2 2 3

Four , Violence strategy

If the data is weak , Take whatever you like 2 The number can be reduced to each other , That is to say, it is OK to keep disorderly .

The first 26 Close the test , Just remember the approximate grid position without looking at the numbers , Just close your eyes and go crazy 18 Seconds to complete .

Because the data is too watery , So I stopped playing .