KöMaL Problems in Informatics, April 2007
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on May 15, 2007.
I. 157. Regular readers of this Journal may remember our great detective, Watson from Problem I. 134. Those bad guys begin to sense that their business is endangered, so from now they encrypt their messages. Watson wants to prevent further robberies, therefore he should be able to decrypt their messages and encrypt his own ones. Encrypted messages contain only numbers separated by semicolons. Watson also knows that every message is signed by one of the wrongdoers. For example, the sequence
119; 25; 125; 69; 80; 118; 67; 147; 43; 21; 109; 29; 88; 128; 130; 72; 58; 156;
belongs to Hack Er. However, signatures are polymorphic, so
112; 32; 36; 158; 63; 135; 97; 117; 44; 20; 51; 87; 58; 158; 49; 153; 83; 131;
is also Hack Er's signature.
Your task is to find out how the gangster's encryption scheme works, then write a program to help Watson decode existing and encode new messages. Your program has three parameters, the first is either ``de'' or ``en'' (meaning decoding or encoding), the second parameter is the name of the file to read, while the third parameter is the name of the converted message file, as in the following example: i157 de secret.txt plaintext.txt.
The source code of your program (i157.pas, i157.cpp, ) should be submitted.
I. 158. The central star system of the Galactic Republic dispatches envoys to all other systems throughout the Galaxy to personally deliver the new flag of the Republic. Members of the Senate first thought that the fastest way to send all the flags out is to use separate spaceships to every star system. This way the outermost system gets their flag last. We will refer to this as original strategy.
The Senate later realized that envoys arriving to a system may proceed to other star systems as well. Moreover, it is also possible for several envoys to travel in the same ship together to a particular system, then, after the delivery, every envoy proceeds to different systems. (Every system has a sufficient number of ships, each capable of carrying an arbitrary number of envoys. All these ships have the same speed.) We will call this as modified strategy.
The Senate decided to organize the delivery in this latter way. However, it is required that the time needed to deliver the last flag should be no more than the corresponding time according to the original strategy.
You should compare the total length of route of the ships if they follow the original or the modified strategy.
Positions of the star systems in the Galaxy are given in the usual Cartesian coordinates. Each line of the input text file contains the X, Y and Z real coordinates of a system, separated by a space. The first line of the file corresponds to the central system. Your program reads the name of the input file from the command line, then uses the standard output to display the total length of route of the ships following the original, then the modified strategy, finally, the difference between these numbers.
The source code of your program (i158.pas, i158.cpp, ) together with a short documentation (i158.txt, i158.pdf, ) should be submitted.
I. 159. A lumber yard sells wooden boards of fixed length, but their cross-section can be freely determined by the customers. The yard cuts the appropriate boards out of trunks of different diameter. Due to the manufacturing technology they cut only right prism shaped, parallel boards of the same size out of a given trunk. The figure shows a possible arrangement.
You should prepare an Excel sheet that chooses between three cutting sizes so that the waste of wood is minimal when the boards are manufactured. Your file should contain two sheets, the first specifying the three possible cutting sizes, e.g. 10 cm×20 cm, 15 cm×15 cm and 12 cm×17 cm, further, the diameter of the trunk, e.g. 87 cm. Your answer should also appear here, giving which cutting size is optimal to that diameter. Auxiliary computations should be performed on the second sheet.
We will take into account the user-friendliness of your sheets (e.g. cell protection) too. (If cell protection is applied, there is no need to specify a password.)
The worksheet with your solution (i159.xls, ) should be submitted.
Problems with sign 'S'
Deadline expired on May 15, 2007.
S. 26. A treasure hunting company combines ancient maps with the latest technology to uncover buried valuables. Their many years of experience shows that treasures are buried in karst mountains with hard rocks and caves. Caves are sphere shaped, possible overlapping holes of different sizes. If they enter or dig into a cave, they can proceed digging from any other point of the cave, this way hard underground work can be reduced.
Write your program to determine the starting point on the surface such that the length of digging to reach the treasure is minimal, taking into account the possible shortcuts through the caves. You should also give this optimal length.
The position of the treasure and location of the caves are read from the standard input. The first line of the input contains the number of caves N (0N1000) and the elevation of the horizontal surface Yf relative to the sea level. The second line of the file contains the Xk, Yk, Zk coordinates of the treasure, while the following N lines the Xi, Yi, Zi, Ri coordinates of the caves. (Here the first three numbers represent the center of the cave, and Ri is the radius of the ith cave. We can suppose that all caves are completely under ground level.)
The program should display the results on the standard output in one line. This line should contain four decimal fractions (with at least two digits of accuracy) describing the X, Y, Z starting coordinates of the tunnel and the minimal distance L to dig.
The source code of your program (S26.pas, S26.cpp, ) is to be submitted.
Upload your solutions above