Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 63. (May 2011)

S. 63. A greatly simplified description of a macromolecule (such as proteins) can consist of a sequence of attracting parts (here denoted by V's) and neutral parts (denoted by K's), such as KVVKVVVKVVKV.

The attracting parts getting close to one another can be responsible for forming the three-dimensional structure of the molecule. For the sake of simplicity, molecules in the present exercise are supposed to be only two-dimensional, but they can be rolled up. Molecules are described by using strings of K's or V's: the V-parts are likely to be found in the inner part of the molecule, while the K-parts are outside.

The example (``Példa két lehetséges szerkezetre'') shows two possible configurations: the rolling up is seen together with the connections between the V-V parts. A molecule has better stability properties if it has more V-V connections. The first example has only 6 of these, but the second example contains 9.

Prepare your program s63 to determine the most stable configuration of a given macromolecule.

The structure of the macromolecule is read from a file. The only command line argument to your program is the name of this input file. The only line of the input file consists of letters V and K (at most 20). The output should be displayed on the screen: the planar shape of the molecule consisting of the maximal number of V-V connections, the number of such connections and the (repeated) input structure of the molecule. It is sufficient to display one solution if there is more than one.

The sample input (``Példa a bemenetre'') and sample output (Kimenet) is displayed below. ``Szomszédszám'' means the number of V-V connections, and ``A molekula'' is the original data.

The source code (s63.pas, s63.cpp, ...) together with a short documentation (s63.txt, s63.pdf, ...) - also describing which developer environment to use for compiling, further a brief description of your solution - should be submitted in a compressed file s63.zip without the .exe or any other auxiliary files generated by the compiler.

(10 pont)

Deadline expired on June 10, 2011.


Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról

Négy megoldás érkezett, de a beküldöttek jól sikerültek.

Mintamegoldás

Borsos Zalán 12. osztályos tanuló (Marosvásárhely, Bolyai Farkas Elméleti Líceum) munkája alapján.

Az algoritmus a visszalépéses keresés segítségével a molekula összes lehetséges térszerkezetét generálja, majd ezek közül kiválasztja azt, amelyik a legtöbb kapcsolatot tartalmazza. A futási időt lényegesen javító észrevétel az, hogy a molekula első két alkotóelemének helyzetét tekinthetjük rögzítettnek, hiszen az így kapott szerkezetekből az összes többi forgatással megkapható, és a kapcsolatok száma nem változik. A komplexitás: exponenciális. A program kódja: s63.cpp

Tesztállományok: 1.txt, 2.txt, 3.txt, 4.txt és 5.txt.


Statistics:

4 students sent a solution.
10 points:Borsos 607 Zalán, Szabó 928 Attila.
9 points:Fekete 976 János, Nagy 111 Miklós.

Problems in Information Technology of KöMaL, May 2011