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

Problem I. 185. (April 2008)

I. 185. Horses are tied up along a long line when they are fed. Various provender is placed into the feeder, because horses like different fodders. Tethers are a bit loose such that every horse can change places with a neighbouring horse but not with second and farther ones.

Your program should give all possible orders of the horses and list their names as well. The input file (as the first command line parameter to your program) contains the number of horses and their names. The name of the output file is given as the second command line parameter.

The first line of the input file is the number of horses (1\leN\le100), the following N lines then contain the name of each horse as standing tied up along the feeder. The first line of the output text file should contain the number of possible orders of the horses, then the actual arrangements of the horses in each line of the file should follow. (In the example, ``Példa'' means ``Example'', ``be.txt'' means input.txt, while ``ki.txt'' is output.txt.)

The source code of your program (i185.pas, i185.cpp, ...) together with a short documentation (i185.txt, i185.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use.

(10 pont)

Deadline expired on May 15, 2008.


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

A legtöbb versenyző észrevette, hogy a lehetséges sorrendek száma a Fibonacci számsorozat alapján határozható meg. A feladat megoldása visszavezethető egy speciális permutáció összes lehetséges sorrendjének előállítására. A speciális megkötés azt jelenti, hogy az eredeti sorozat egy eleme se cserélhet helyet 1-nél nagyobb távolságú másik elemmel. Ezt a szabályt figyelembe véve a legtöbb versenyző rekurzív cseremódszerrel állította elő a sorokat. Másik "klasszikus" módszer a feladat megoldására, a visszalépéses kereséssel történő előállítás. ( lovak.dpr)


Statistics:

7 students sent a solution.
10 points:Adrián Patrik, Földes Imre, Horváth 135 Loránd, Szoldatics András, Véges Márton.
6 points:1 student.
4 points:1 student.

Problems in Information Technology of KöMaL, April 2008