Összes eset átnézése

Kiinduló gondolat

Néha az a legjobb, ha egy feladatot a lehető legegyszerűbb, legprimitívebb stratégiával oldunk meg, mert ezt a legkönnyebb leprogramozni. Az összes eset vizsgálata ilyen egyszerű stratégia. Programozási versenyeken nem fontos a leggyorsabb megoldást megtalálnunk, elég egy olyat, ami a megadott időkorláton belül lefut.

Az 'összese eset átnézése' módszert nevezhetjük 'nyers erő' (brute-force) módszerbek is. Mindig ez legyen az első, amit megfontolsz: ha működik, felesleges komplikáltabb algortimust tervezni. A 'nyers erő' algoritmust egyszerű lekódolni és ami még fontosabb, egyszerű a hibakeresés (debug) is. Egy gyorsan elkészített 'nyers erő' megoldás után több idő marad a nehezebb feladatokra.

Ha egy probléma megoldásához csak néhány millió eset átnézése szükséges, akkor azokat nyugodtan nézzük végig egy egyszerű ciklussal, és minden esetről döntsük egyesével: megoldást találtunk-e vagy nem.

Vigyázat!

Nem mindig nyilvánvaló, hogy az összes eset átnézése a nyerő módszer.

Feladat: Party Lamps [IOI 98]

Van N lámpa és 4 kapcsoló. Az első minden lámpát átvált, a második a páros sorszámúakat, a harmadik a páratlan sorszámúakat, a negyedik pedig az 1, 4, 7, 10, ... sorszámúakat.

Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps (e.g., lamp 7 is off), output all the possible states the lamps could be in.

Naively, for each button press, you have to try 4 possibilities, for a total of 410000 (about 106020 ), which means there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about 100004 (about 1016 ), still too big to completely search (but certainly closer by a factor of over 106000 ).

However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only 24 = 16 possibilities, surely a number of iterations solvable within the time limit.

Feladat 3: The Clocks [IOI 94]

A group of nine clocks inhabits a 3 x 3 grid; each is set to 12:00, 3:00, 6:00, or 9:00. Your goal is to manipulate them all to read 12:00. Unfortunately, the only way you can manipulate the clocks is by one of nine different types of move, each one of which rotates a certain subset of the clocks 90 degrees clockwise.

Find the shortest sequence of moves which returns all the clocks to 12:00.

The ``obvious'' thing to do is a recursive solution, which checks to see if there is a solution of 1 move, 2 moves, etc. until it finds a solution. This would take 9k time, where k is the number of moves. Since k might be fairly large, this is not going to run with reasonable time constraints.

Note that the order of the moves does not matter. This reduces the time down to k9 , which isn't enough of an improvement.

However, since doing each move 4 times is the same as doing it no times, you know that no move will be done more than 3 times. Thus, there are only 49 possibilities, which is only 262,144, which, given the rule of thumb for run-time of more than 10,000,000 operations in a second, should work in time. The brute-force solution, given this insight, is perfectly adequate.

Példák

Tehénfejés [USACO 1996 Competition Round]

Given a cow milking schedule (Farmer A milks from time 300 to time 1000, Farmer B from 700 to 1200, etc.), calculate

The longest time interval in which at least one cow was being milked
The longest time interval in which no cow is being milked

Perfect Cows & Perfect Cow Cousins [USACO 1995 Final Round]

A perfect number is one in which the sum of the proper divisors add up to the number. For example, 28 = 1 + 2 + 4 + 7 + 14. A perfect pair is a pair of numbers such that the sum of the proper divisor of each one adds up to the other. There are, of course, longer perfect sets, such that the sum of the divisors of the first add up to the second, the second's divisors to the third, etc., until the sum of the last's proper divisors add up to the first number.

Each cow in Farmer John's ranch is assigned a serial number. from 1 to 32000. A perfect cow is one which has a perfect number as its serial. A group of cows is a set of perfect cow cousins if their serial numbers form a perfect set. Find all perfect cows and perfect cow cousins.