THE 12TH LATVIAN OLYMPIAD IN INFORMATICS
3RD STAGE PROBLEMS

1. "An encrypted message for James Bond"

The famous agent 007 (James Bond) had a characteristic feature never expressed in literature. If he received an encrypted message containing a specific string (containing only digits), he became nervous, which in turn for some time significantly lowered his ability to work.

Luckily, all these strings were known by the leader of Her Queen Majesty encryption bureau Mr.X, who named these strings "dangerous". It is known that all of these strings contain no less than three and no more than nine digits. Not to excessively irritate the superagent, Mr.X suggested acting as follows – to find the dangerous string that starts leftmost in the encrypted message entitled for James Bond and delete the leftmost digit and the rightmost digit, thus shortening the total length of the encrypted message by two digits. If more than one dangerous string starts at the given position, then delete the digits in the shortest of the strings. Then repeat the action until there are no more dangerous strings in the remainder of the message.

Your task is to write a computer program that would apply Mr.X's suggested algorithm.

Input data

The first line of the input file SLIKTIE.DAT contains one natural number k (k£ 10000) - the number of dangerous strings. Each of the following lines of the file contains one dangerous string. The length of each dangerous string is no less than three and no more than nine digits. Each dangerous string is given only once.

The first line of the input file BONDS.DAT contains a string (digits only) without any separators – the starting content of the encrypted message. The length of the encrypted message is no less than 1 and no more than 250 digits.

Output data

The output file BONDS.REZ must contain only one line and that must contain one string (digits only) – the modified encrypted message.

Example
Input data (2 filesi)                     Output data                     Comment
(file SLIKTIE.DAT) (file BONDS.REZ) The modification was done
4                 325                             thusi: 3370250 ®
3702                                37250 ® 325
330
370
7250

(file BONDS.DAT)
3370250


2. "Crossing a river"

John, an inhabitant of Alaska, must cross a wide, non-freezing river on his way to the nearest city.

John acts in a very simple fashion - harnesses his dogs to his sleighs, ties a boat to the sleighs and starts his journey. When he reaches the river, John gets in the boat and transports the dogs to the other side of the river. During one of the times crossing the river John ties the sleigh to the boat, and thus John with all his dogs and the sleigh has successfully crossed the river. Nevertheless, it is not always so simple as it might seem - some dogs are hostile to each other and cannot be left on the same bank of the river when John is not present. On the other hand, the dogs that are not hostile to each other can be left together on either bank of the river without any concerns. Luckily, John knows, which dogs are hostile to each other.

It happens that John has five dogs with him - Hurricane, Bear, Wonder, Angry one, and Argot. Bear is hostile to Hurricane, Angry one, and Argot. Wonder is hostile to Hurricane and Angry one. Other dogs are not hostile to each other. Thus a three-seater boat is sufficient for John, i.e. during one time of crossing the river he can transport two dogs. In addition, the least number of times he must cross the river is 7 (each dog takes one seat in the boat, the sleigh needs no seats):
transports Bear and Wonder;‚transports Bear back;ƒtransports Argot and Bear;
„transports Bear and Wonder back across the river;…transports Angry one and Hurricane; †returns transporting no dogs;‡transports Bear and Wonder and continues his journey.

At no point during the journey two dogs hostile to each other were left on the same bank of the river when John was not present. If Argot and Hurricane were also hostile to each other, a three-seater boat would not be sufficient.

Your task is to write a program, which for a given number of dogs and the given relationships between the dogs computes the minimum possible number of seats in the boat that is sufficient to transport all the dogs across the river and finds a way of transporting the dogs with this boat. Additional points will be awarded if the number of times of crossing the river will be the smallest possible.

Input data

The first line of the UPE.DAT file contains one natural number N (1 £ N £ 10) - the number of dogs John has with him. The dogs are all numbered 1,2,3,…,N. The second line of the file contains an integer non-negative number K, which is the number of pairs of hostile dogs. The next K lines contain each one pair of hostile dogs in the form "a b", where a and b are the numbers of dogs (1 £ a, b £ N, a ¹ b). There is a space symbol between the numbers in the pair.

All the pairs of hostile dogs are given, each pair is mentioned exactly once. For a specific pair of dogs both of the following examples can be applied: “a b” and “b a”, but the file contains only one of these.

Output data

The first line of the UPE.REZ file must contain one natural number X - the least necessary number of seats in the boat, so that the dogs can be transported in the way expressed above. The second line of the file must contain one natural number Y- the number of times John must cross the river to transport all the dogs in the way mentioned above. The next Y lines must each represent one river crossing in correct order. The i+2-nd line of the file must represent the i-th time of crossing the river and is in the form:

a1 a2 a3 … aj 0

, where a1 a2 a3 … aj are the numbers of the dogs that during the i-th time of crossing the river must be transported, and the numbers are in ascending order. Each two numbers must be separated by a space symbol. Each line of the file contains 0, which must be separated from the last number by a space symbol. A crossing of the river with an empty boat must be represented by a line containing only the symbol 0.

Example
Input data (file UPE.DAT)     Output data (file UPE.REZ)
5                 3
5                 7
1 2               2 4 0
2 3               2 0
4 3               1 2 0
4 5               2 4 0
2 5               3 5 0
                  0
                  2 4 0


3. "Ghost palace"

The following rules are applied to a rectangle-shaped ghost palace, having NM rooms:

  1. a traveller can enter from the outside only the room with coordinates (1;1)
  2. it is only possible to exit the palace from the room with coordinates (N;M);
  3. there is a magical number written with chalk on the floor of each of the rooms - a natural number from 1 to 13;
  4. the traveller can imagine one of eight directions (in parallel to the walls of the palace or diagonally) and he is without any delay teleported in the imagined direction as many rooms as is the number written on the floor of the room. If that is not possible (the number of rooms in this direction is less than the number on the floor of the room, nothing happens, and the traveller must imagine another direction.
  5. it is not allowed to move two times in a row in the same direction.

For example, if the traveller was able to reach the room with coordinates (3;3) in a palace (having 5x4 rooms and the plan of which is seen in the picture), using one transportation it is possible to be moved to the rooms (1;1), (3;1), (1;3), (5;1), and (5;3). On the other hand, to reach the room (5;4) from the room (3;2), using exactly two transportations (the traveller can leave the palace only from this room), he cannot move the first time to (4;3) (as he would have to move the second time in the same direction, which is not allowed), but has to at first move to (2;1).

Your task is to write a program that for the given plan of the palace determines the minimal number of moves sufficient for the traveller to reach the room (N;M) from the room (1;1), according to all the rules applied to the palace.

Input data
The first line of the input file PILS.DAT contains two natural numbers N and M - the number of rooms in the plan in horizontal and vertical direction (1£N,M£100).
Each of the next M lines of the file contains N natural numbers - the number written on the floor of the corresponding room.
The i+1-st line of the file contains the information about the i-th row in the plan of the palace.
There is one space symbol between every two numbers in each line of the file.

Output data
Your program must output one natural number to the first line of the PILS.REZ file - the minimum sufficient number of moves .
If it is not possible to reach the room with coordinates (N;M), the first line of the text file PILS.REZ must contain one word NEVAR.

Example
Input data(file PILS.DAT)       Output data(file PILS.REZ)
5 4                 4
3 3 6 7 11
3 2 1 1 3
3 2 2 1 1
2 1 2 2 1


4. "Stones of Wisdom"
 
 

Archaeologist Shovel has for a number of years now been studying the stones of wisdom. Each stone of wisdom is a cube, each side of which contains an arrow that points either to an edge or to a vertex. Each stone of wisdom Shovel finds he photographs from three sides, obtaining three photographic images - views. For one stone in each view the vertex that is common to all the visible sides is different (nothing is known concerning the relative positioning of the vertexes). One set of such images is shown in picture 1.
1.zīmējums. Trīs viena akmeņa skati.
2.zīmējums. Bultu apzīmējumi.
To input information concerning each of the views of the stones of wisdom into a computer, Shovel has invented the following scheme:
Firstly, each of the possible arrows Shovel has represented with a different number, as seen in picture 2.
Secondly, for each of the views of a stone of wisdom Shovel uses the transformation seen in picture 3, where ai* represents the number corresponding to the arrow ai according to the coding from picture 2. Thus for each of the views a corresponding three-digit number is obtained - a coding of the view. The codings of the views seen in picture 1 are 833, 286, and 878.
Shovel has now decided to change to another stone of wisdom coding system to from each of the views obtain a spreading of the surface of the stone and encode it to a six-digit number ,using the arrow coding seen in picture 2. Of course, more than one coding may correspond to one and the same stone, for, for instance, the spreadings seen in picture 5 all correspond to the views seen picture 1 (in fact, these are only some of all the possible ones). The codings of these spreadings according to Shovel's system are: 436746, 181228, and 784218.

3.zīmējums. Skata trīsciparu kodējuma iegūšana.
4.zīmējums. Izklājuma forma.5.zīmējums. Izklājumu paraugi.

Unfortunately, transferring to the new laboratory, the order of the views in the colloection of stones of wisdom may be mixed, therefore, it could be that it will not be possible to form such a surface spreading form three views.

Your task is to write a program that determines whether the three given views of stones of wisdom all could correspond to one stone and if they could, finds one possible coding of the surface spreading.

Input data
The input text file AKMENS.DAT contains three lines. Each line contains one three-digit number - a coding of one of the views of a stone of wisdom.

Output data
If the given views could be the views of one and the same stone, then one six-digit number must be output to the text file AKMENS.REZ - one possible coding of the surface spreading of the stone of wisdom. If the given views cannot possibly correspond to one and the same stone, only the word NAV must be output to the first line of the AKMENS.REZ file.

Example
Input data (file AKMENS.DAT)      Output data (file AKMENS.REZ)
833                   181228
286
878



Home To the problem and test archive