KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 15 May 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley