Problem I. 216. (May 2009)
I. 216. In our March issue we have played the game MasterMind. A friend of us claims that he uses the following simple algorithm to play: he always chooses the first item from the lexicographically ordered list of possible guesses. To find out whether he indeed follows this strategy, write your program that gives the necessary number of steps in the proper order for each secret sequence.
Your program reads one line from the standard input, containing the secret sequence (without spaces). The output should be written to the standard output in n+1 lines, where n denotes the number of steps necessary to solve the puzzle.
For example, if the secret code is ``DADA'', then your output should be the following:
The source code of your program (i216.pas, i216.cpp, ...) and a short documentation (i216.txt, i216.pdf, ...) should be submitted, also specifying the name of the developer environment to use for compiling.
(10 pont)
Deadline expired on June 15, 2009.
Sorry, the solution is available only in Hungarian. Google translation
A feladat nem volt nehéz, ennek ellenére sajnos nagyon kevés megoldás érkezett.
A könnyű megoldáshoz vezető lényeges felismerés az, hogy az elrejtett és a tippelt sorozatok az értékelés szempontjából felcserélhetők. Ebből az következik, hogy egy tippre kapott válasz alapján csak azok a sorozatokat lehetségesek, amelyek a tippel összevetve ugyanezt a választ eredményezik, a többi figyelmen kívül hagyható.
A feladat megoldása során a legcélravezetőbb volt elkészíteni a lehetséges tippek lexikografikus sorrendjét, a lehetségesek közül az elsőt tippelni, majd a válasz alapján (az iménti felismerést felhasználva) a nem lehetségeseket kihúzni. A tippelést addig kell ismételni, amíg a lehetségesek listája nem szűkül egyetlen elemre.
A helyes megoldást adók közül Szabó 928 Attila munkáját közöljük. i216sza.zip
Statistics:
4 students sent a solution. 10 points: Balla Attila, Englert Péter, Szabó 928 Attila. 0 point: 1 student.
Problems in Information Technology of KöMaL, May 2009