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

Problem I. 127. (March 2006)

I. 127. A school secretary has to make all the monthly lunch tickets for the students. In every month she gets a sample ticket, then she makes photocopies of it and cuts the copies out.

She puts the tickets already completed and the sample ticket side by side so that she can photocopy them more effectively. She makes some copies this way, then cuts the tickets out of the recent sheets. Now she places these new ones and the old ones side by side again, and repeats the procedure. (We may assume that the copy machine can copy an unlimited number of tickets at one go.) However, both the copying and the cutting process take some time, being independent of the number of tickets copied or cut out.

Prepare your program to help the secretary make the required number of tickets as fast as possible. Your program asks for the following pieces of information: the required number of tickets (including the sample ticket) and the time for photocopying and cutting one sheet. Then the program should compute the minimal time for the completion of the tickets, and also, give the necessary steps encoded by the letters P (photocopying) and C (cutting-out).

The required number of tickets is at most 1000. The secretary is very economical, she makes exactly the required number of tickets and no more.

Example (messages of the computer are in italics):

Number of tickets:  64
Copying time:       1
Cutting time:       8
Total time:         30
Steps: PPPPPPPCPPPPPPPC

The source code of the program (i127.pas, i127.cpp, ...) is to be submitted.

(10 pont)

Deadline expired on April 18, 2006.


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

Megoldás. Induljunk ki abból, hogy a titkárnő mindig a szükséges számú ebédjegyet készíti el, soha se többet, illetve hogy egyszerre az összes eddig elkészült ebédjegyet fénymásolja. Vizsgáljuk meg, mi történik néhány fénymásolás alkalmával: n db kezdeti ebédjegyből k fénymásolás után (k+1)n ebédjegy lesz. Mivel kezdetben 1 db minta-ebédjegye volt a titkárnőnek, így N, az ebédjegyek száma, a fénymásolások valamilyen szorzatával lesz egyenlő: N=1.(k1+1).(k2+1).....(ki+1). Másképpen, két kivágás közötti fénymásolások száma +1 az N osztója kell, hogy legyen, illetve ezek szorzatának nyilván N-et kell adnia.

Ezek közül a szorzatok közül az (egyik) minimális idejűt kell meghatározni. Számítsuk ki egy ilyen fénymásolás-sorozat idejét. Jelöljük a fénymásolás idejét Tf-el, a kivágás idejét Tk-val, továbbá a kivágások közötti fénymásolások számát ki-vel, a kivágások számát pedig n-Nel. A fénymásolás ideje így: T=Tk.n+Tf.(k1+k2+...+kn).

Egy lehetséges algoritmus ennek a sorozatnak a meghatározására, hogy végignézzük N összes lehetséges szorzótényezős felbontását, és kiválasztjuk a legkisebb idejűt. Az összes lehetséges felbontást egy backtrack szerű algoritmussal nézhetjük végig, mindig ügyelve arra, hogy a szorzan N maradjon.

Erre látható egy Pascal nyelven írt megoldás. Az esetek végignézését egy rekurzív függvény végzi. Ez megkeresi a paraméterként megadott szám összes osztóját, az aktuálisat eltárolja egy tömbben, majd elosztja a paramétert az aktuális osztóval. Ha a hányados nagyobb 1-nél, akkor a függvény rekurzívan meghívja magát a hányados paraméterrel. Ha 1, akkor visszatér a függvény. Minden lépésben kiszámolja a tömbben lévő számok által reprezentált másolás-folyamat idejét, a legkisebb ilyet pedig eltárolja.

Letölthető Pascal program: i127.pas

Engedy István


Statistics:

13 students sent a solution.
10 points:Balambér Dávid, Czigler András, Györök Péter, Kiss Dániel Miklós, Ozsvárt László, Vincze János.
9 points:Kovács 129 Péter, Szoldatics András, Véges Márton.
4 points:3 students.
0 point:1 student.

Problems in Information Technology of KöMaL, March 2006