Task P-II-1

A triangular network consists of equilateral triangles with unit-length side. Let us modify the coordinate system a little bit: the x-coordinate is oriented the same way as we are used from the cartesian coordinates, but the angle between the x- and y-axes is 60 degrees. For instance, the verteces of the equilateral triangle based in the origin have the coordinates (0, 0), (1, 0), (0, 1). Now assume there is a polygon whose verteces 1) lie in the verteces of this network, 2) are mutually different, and 3) every two neighboring verteces of this polygon have distance of unit-length. The polygon can be described in the program input as follows: the first line contains the number of verteces N, the following N lines contain the coordinates of the polygon verteces in the order along the circumference of the polygon. Your task is to write a program that can compute the area of a polygon in unit triangles.
Note: Try to minimize the space and time complexity of the algorithm. You can assume that the input is correct.

Task P-II-2

N is a prime, for instance 991. An array P with N integer elements (indexed from 0) contains M different positive integers (M < N). Unoccupied elements of the array are initialized with zeros. The elements are stored in the array in such a way that it is possible to use the function search to determine the location of any element X (the function returns the location of X in the array P, if X is present in the array, otherwise it returns value -1):

function search(X:integer):integer;
var i:integer;
begin
  i := (X div 10 + X mod 10) mod N;
  while P[i] > X do
    i := (i + 7) mod N;
  if P[i] = X then search := i
  else vyhladaj := -1;
end;

int search(int X) 
{
  int i;
  i = (X / 10 + X % 10) % N;
  while (P[i] > X) i = (i + 7) % N;
  if (P[i] == X) return(i);
  else return(-1);
}

  a)   Describe how the elements should be stored in the array P, so that one could use the function search to search for any of them.
  b)   Write the most efficient procedure insert, which can be used to insert an element X to the array P so that the function search can still be used for searching (assume that before inserting of the element X, the array P had this property and did not contain the element X).

Task P-II-3

Consider a plotting device, which can draw various pictures. However, their descriptions must follow a special format - presented as a character string with the following restrictions:

• the string is a sequence of parameters, which is always enclosed in '[' and ']' brackets;
• a parameter can either be a number or a sequence of parameters;
• a sequence of parameters has even length, where parameters at odd locations must be numbers.

• if the sequence is empty, nothing will be drawn
• if it is not empty, the first parameter (P₁) is a number and the second parameter (P₂) is either a number or a sequence of parameters:
  • if P₂ is a number, the drawing pen will move forward in its current drawing direction a distance of length P₁, and then it will change its drawing direction by P₂ degrees to the right (clockwise);
  • if P₂ is a sequence, the drawing pen will interpret the P₂ sequence P₁-times.

Some older plotting devices have unsynchronized control circuits. Thus it happens from time to time that instead of drawing a line of length P they draw a line of length P + 1. For this reason, the pen often stops at a location, which is different from the final location that could be exepcted from the input sequence. Your task is to construct and prove an algorithm, which for a given input sequence (a character string) determines the maximum distance of the place where the pen terminates from its expected final location.

Task P-II-4

Construct a D0L system (or prove that it is not possible), with the following grow fucntions:

  a)   f(n) = nⁿ
  b)   f(n) = n²2ⁿ

D0L systems

An alphabet is an arbitrary finite non-empty set. The elements of this set are symbols. The finite sequence of symbols of some alphabet is a word. We will use for the symbols the early letters of the English alphabet (a, b, c, ...) , while for the words we will use the late letters (u, v, w, ...) and the capital letters (B, G, D, ...). The word length is the number of symbols it contains, and it is written as |w|. Chaining of two words v = a₁a₂...a_n and u = b₁b₂...b_m produces a word u*v = a₁a₂...a_nb₁b₂...b_m. The set of all words, which can be formed from the symbols of alphabet B is written as B*. This set contains also an empty word, i.e. the word of a zero-length represented by @. A rule over the alphabet B is an ordered pair (a, v), where a is from B and v is from B*. The rule is written in a form a -> v. A deterministic Lindermayer system without interactions (D0L system) is an ordered tripple (B, P, w), where

• B is an alphabet,
• P is a set of rules, which contains exactly one rule for each symbol a of alphabet B in a form a -> u,
• w is a word called an axiom.

1. w₁ = w
2. if w_i = a₁a₂...a_n, then w_i+1 = u₁ * u₂ * ... * u_n, where a_j -> u_j is in P for j = 1, 2, ... n.

Example

• {a, b} is an alphabet containing two symbols a and b
• The length of the word aabab is 5.
• By chaining the words ab and aab we obtain the word ab * aab = abaab.
• We can form an infinite number of words over this alphabet: @, a, b, aa, ab, bb, aaa, ...
• An example of a rule is a -> aa.
• An example of a D0L system is ({a, b}, {a -> aa, b-> ab}, ab).
• A sequence produced by this system is ab, aaab, aaaaaaab, aaaaaaaaaaaaaaab, ... (if the word contains several equal consecutive symbols, we can write this subsequence as the symbol followed by the number of repetitions, in this case the sequence can be written as: ab, a3b, a7b, a15b, ....
• The grow function of this D0L system is f(n) = 2ⁿ.