2nd Balkan Olympiad in Informatics
Thessaloniki, Greece, 1-6 October 1994

Day 2 - Problem 1



Assume an nxn table (where n<=10) containing positive integer numbers 1 < x <="40."

  1. (30 points) Replace each number x with a number y, where y is the maximum number of prime numbers which sum to x, so that any prime number appears once in the sum with at most one and only one exception of a prime number which may appear twice. Have, also, in mind that 1 is not prime. For example:

    2=2 f(2)=1
    3=4 f(3)=1
    4=2+2 f(4)=2
    5=3+2 f(5)=2
    6=3+3 f(6)=2
    7=3+2+2 f(7)=3

    Give the resulting table in the output.

  2. (10 points) After each element x has been replaced with y, determine the maximal number of y elements which are connected horizontally, vertically or diagonally forming a concrete area, and give this y value. Also, determine, the smallest enclosing rectangle which can be defined by giving the coordinates (i.e. row and column) of the upper leftmost and lower rightmost corners of the enclosing rectangle.

  3. (25 points) In general, the area found in (ii) is not a square or even a rectangle. Determine the minimum number of non-overlapping squares of any size (e.g. 1x1, 2x2, 3x3, etc.) it consists of.

  4. (20 points) Try to maximize the area determined in (ii) with the minimum number of element swappings of the table produce in question (i). Give, also, the coordinates of the elements which are swapped. Show in the output the new form of the table obtained.

  5. (15 points) Determine the y element that appears most often in the table produced in question (i). In case of a tie (e.g. two or more y elements with the same value) choose the y element with the smallest value. Try to collect all its instances nearby (i.e. so that the are connected horizontally, vertically or diagonally) and give the minimum number of swappings performed. Give, also, the coordinates of the elements which are swapped. Illustrate the new form of the table obtained. Beware that the swappings should be applied on the table produced in question (i).



Example:
  • Input
    The first line consists of a single integer number denoting n, the length of the table side. Then, is successive lines the rows are given containing the integer numbers separated by one space, e.g.

    6
    19 19 12 12 12 19
    19 12 7 12 12 7
    2 4 7 7 12 19
    19 12 12 12 12 19
    19 19 19 19 5 19
    30 6 30 5 12 19

  • Output:
    1. After replacing x with y, the output should be as follows:
      5 5 4 4 4 5
      5 4 3 4 4 3
      1 2 3 3 4 5
      5 4 4 4 4 5
      5 5 5 5 2 5
      6 2 6 2 4 5
    2. The output should be given in three separate lines as follows:
      11
      4
      (1,2),(4,5)
      where the first line gives the maximal number of y connected elements, the second line contains the y value, and the third line contains the coordinates of the enclosing rectangle.
      HINT:you may avoid the parentheses and give the coordinates separated by commas. The same hint holds for the output of question (iv) and (v).
    3. The output consists of a single number:
      8
      which stands for the minimum number of non-overlapping square in the area of (ii).
    4. The output should be as follows:
      1
      (5,5),(6,5)
      5 5 4 4 4 5
      5 4 3 4 4 3
      1 2 3 3 4 5
      5 4 4 4 4 5
      5 5 5 5 4 5
      6 2 6 2 2 5
      where the first line gives the minimum number of swappings, and the second line gives the coordinates of the swapped element(s). The next n lines contain the new form of the table.
    5. The output should be as follows:
      5
      2
      (1,2),(3,1)
      (1,6),(5,5)
      5 1 4 4 4 2
      5 4 3 4 4 3
      5 2 3 3 4 5
      5 4 4 4 4 5
      5 5 5 5 5 5
      6 2 6 2 4 5
      where the first line stands for the most often appearing element, the second line for the minimum number of swappings, the next lines give the coordinates of the two swappings. Finally, the last n lines illustrate the new form of the table .
Attention:
Your program will begin with a question: "Do you wish to solve part (i) ?"
If the answer is YES the the program will start assuming an input file with the name INPUT1.TXT. Otherwise, part (ii) will start assuming an input file under the name INPUT2.TXT.