\input{algdata.tex} \specialsection*{Problems for BOI 2000} \newpage %***************** LATVIA ************************ \specialsection*{Stickers (LATVIA)} Charles is auto races fan and he decided to make his own model's collection. In shop it is possible to buy models in closed and covered boxes. In each box there are one model parts and set of stickers with images of digits. In every box the set of stickers is the same. Charles decided to label models by consecutive integers starting from $1$. For example, to label the $2070$-th model four stickers are necessary: one sticker with ''$2$'', two with ''$0$'' and one with ''$7$''. Charles complete every model in the following way: he opens new box, builds a model and labels it using sticker(s). He can use stickers from current and previously opened boxes, but it is not allowed to open additional new box to get at missing stickers. Write a program which for given set of stickers counts how much models Charles can label in the described way. \fe{Input data: } In the only line of text file \verb|STICKERS.IN| ten one digit integers $$ i_0,i_1,i_2,i_3,i_4,i_5,i_6,i_7,i_8,i_9 $$ are given, where $i_j$ is a number of stickers with digit $j, (0\leq j\leq 9)$ in the set. Each two neighbour digits are separated by one space symbol. \fe{Output data: } The only line of text file \verb|STICKERS.OUT| should contain one integer -- number of labeled models. \fe{Examples: } Input data (file \verb|STICKERS.IN|) \verb|1 1 1 1 1 1 1 1 1 1| Output data (file \verb|STICKERS.OUT|) \verb|199990| Input data (file \verb|STICKERS.IN|) \verb|1 2 2 1 1 1 1 1 1 1| Output data (file \verb|STICKERS.OUT|) \verb|371599992| \newpage %**************************** FINLAND **************************** \specialsection*{Honeycomb problem (Finland)} \ku{Figure \ref{honeycomb-fig}} shows a honeycomb of numbers (side length of the honeycomb is $3$). A route starts from some node in the uppermost row and ends to some node in the lowest row. From a node, the route can continue only diagonally down to the left or diagonally down to the right. When creating a route through the honeycomb, you are allowed to make {\em at most} one swap of two numbers on {\em at most} one horizontal row of the honeycomb. (Swapping essentially means that in one chosen row you are allowed to place the greatest number of that row to any position on the same row.) Your task is to write a program that calculates the highest sum of numbers on any route using the ability of swapping two numbers on a chosen row. \begin{figure}[h] \begin{center} \includegraphics[width=5cm]{fin.eps} \caption{\small{\textit{A honeycomb of side length $3$.}}} \label{honeycomb-fig} \end{center} \end{figure} Restrictions: \begin{itemize} \item The {\em numbers} in the nodes are integers between $0$ and $99$. \item The {\em side length} of the honeycomb is an integer between $1$ and $99$. \end{itemize} \fe{Input data: } The side length of the honeycomb is in the first row of the file {\tt INPUT.TXT}. If the side length is $n$, the honeycomb consists of $2n-1$ rows. Numbers on the rows of the honeycomb are on the following $2n-1$ rows as follows: \begin{verbatim} 3 1 2 3 3 2 2 1 4 2 8 0 3 5 3 1 2 3 1 4 \end{verbatim} \fe{Output data: } The highest sum is written as an integer in the file {\tt OUTPUT.TXT}. In the example of Figure \ref{honeycomb-fig}: \begin{verbatim} 22 \end{verbatim} In the Figure \ref{honeycomb-fig} the correct solution ($3+2+8+5+4=22$) is marked with emphasized numbers and arcs. Notice that number '$5$' on the $4\,$th row (from the top) is swapped to the $3\,$rd position (from the left) on that row. \newpage %*************************** Lithuania ******************** \specialsection*{Electronical plate (Lithuania)} A square grid is carved on the top of a square plate. The place where two gridlines cross is called a node. There are $n\times n$ nodes in the grid. \begin{figure}[h] \begin{center} \includegraphics[height=5cm]{lit.eps} %***\caption{\small{\textit{The problem (left) and the solution (right)}}} \label{lit-fig} \caption{\small{\textit{The problem (center) and the solution (right)}}} \label{lit-fig} \end{center} \end{figure} Some nodes contain pins. The task is to connect those pins to the nodes on the boundary of the plate using electronic circuits. A circuit can be laid out only on the grid (e.g. it can't be laid out slantwise). Any two circuits can't have a common point, therefore any two circuits can't be laid out on the same gridline, nor on the same node. A circuit can't be laid out on the boundary grid (the circuit must be finished as soon as it reaches boundary) nor on a node, containing another pin. %***An example of an electronic plate containing pins is given in \ku{figure 2, left}. Black dots in the An example of an electronic plate containing pins is given in \ku{figure 2, center}. Black dots in the picture represent pins. Problem. Write a program to connect as many pins as possible to the nodes on the boundary. The pins which are already on the boundary satisfy the requirements and there is no need to make any circuits for them. If there exists more that one solution find any of them. \fe{Input data: } Input data are given in the text file \verb|ELEKT.IN|. The first line of this file contains an integer $n (3 \leq n \leq 15)$. Each of the following $n$ lines consists of n digits separated by one space. The digits can be $1$ or $0$. One ($1$) means a pin, zero ($0$) - a node without a pin in the appropriate place of the grid. The nodes are numbered from $1$ to $n\times n$ first from left to right and then from %***the top to bottom. The number of the node the contact is on is the identifier of the contact. the top to bottom. The number of the node the pin is on is the identifier of the pin. \fe{Output data: } Output the results to the text file \verb|ELEKT.OUT|. Write $k$ - the maximum number of pins connected to the boundary using electronic circuits - in the first line of the file. A circuit connecting an appropriate pin to the boundary should be described in each of %***the following k lines. First comes the identifier of the contact, then the sequence of the following k lines. First comes the identifier of the pin, then the sequence of letters, describing the directions of the circuit: $E$ - to the East, $W$ - to the West, $N$ - to the North, $S$ - to the South. One space should be left between the identifier and the sequence of letters, and no spaces should be left between the letters in the sequence. %***The results should be presented in the increasing order of contact identifiers. The results should be presented in the increasing order of pin identifiers. \fe{Examples: } \begin{verbatim} INPUT DATA OUTPUT DATA 6 6 0 0 0 1 1 1 11 E 0 0 0 0 1 0 16 NWN 0 0 0 1 1 1 17 SE 0 0 0 0 0 0 27 S 0 0 1 1 1 1 28 NWWSS 0 0 0 1 0 1 29 S \end{verbatim} \newpage %******************** Estonia **************** \specialsection*{Mutexes (Estonia)} Modern programming languages allow writing programs that consist of several threads of execution. This is as if several programs are running in parallel in the same address space, accessing the same variables. Often the threads need to be synchronized with each other. For instance, one thread may need to wait for another to complete some computation and store the result into some variable. The simplest tool for thread synchronization is \ku{mutex}. A mutex is a special object that can be in \ku{locked} or \ku{unlocked} state. A locked mutex is always owned by exactly one thread. There are two operations that a thread can apply to a mutex: LOCK and UNLOCK. If a thread applies LOCK to a mutex that is currently unlocked, the mutex becomes locked and the thread acquires ownership of the mutex. If a thread tries to apply LOCK to a mutex that is already locked by some other thread, the thread is blocked until the mutex is unlocked. If a thread applies UNLOCK to a mutex owned by the thread, the mutex becomes unlocked. If there were other threads waiting to LOCK the mutex, one of them is granted ownership of the mutex. If there were several threads waiting, one is selected arbitrarily. There are two common kinds of problems in multithreaded programs: deadlocks and race conditions. A deadlock occurs when two or more threads are waiting for each other to release a mutex and none of them can continue. A deadlock occurs also when a thread is waiting for a mutex that was locked by another thread that has terminated without releasing the mutex. A race condition occurs when two or more threads are accessing the same variable simultaneously. If one thread is writing a variable while another is reading it, the reading thread may receive an arbitrary value: the result does not even have to be either the old or the new value of the variable. If two or more threads are writing the same variable simultaneously, the result is also undefined: the variable may receive an arbitrary value. However, any number of threads can read a variable simultaneously wi \fe{Task: } You are provided descriptions of some threads and your task is to decide whether deadlocks and race conditions can occur. Each of the threads is a sequence of instructions of the following form: \begin{verbatim} LOCK UNLOCK = = =+ =- \end{verbatim} You may assume the following about the commands: \begin{itemize} \item names of \ku{mutexes} are uppercase letters $A\ldots Z$ \item names of \ku{variables} are lowercase letters $a\ldots z$; \item all \ku{integers} are in range $0\ldots255$ \item no thread attempts to lock a mutex it already owns \item no thread attempts to unlock a mutex it does not own \end{itemize} \fe{Input data: } The first line of input file \verb|MUTEXES.IN| contains the number of threads $M, (1 \leq M \leq 5)$ and is followed by $M$ blocks describing each thread. The first line of a block describing thread i contains the number of instructions in this thread $N_i, (1\leq N_i \leq 30)$ and is followed by $N_i$ lines with instructions. Instructions do not contain extraneous whitespace. Each thread contains at most $10$ instructions operating on mutexes, the rest are assignments. \fe{Output data: } The first line of output file \verb|MUTEXES.OUT| must contain two numbers: $D$ and $R$. $D$ must be $1$ if deadlocks are possible, or $0$ if not. Similarly, $R$ must be $1$ if race conditions are possible, or $0$ if not. If deadlocks are possible, the second line must describe a state of program in which a deadlock occurs. If there are several states with a deadlock, output any of them. In this case we are looking for complete deadlock, in which none of the threads can continue execution -- a thread must be either terminated or blocked by a mutex. If deadlocks are not possible, the line must be empty. The third line must contain description of a program state with a race condition if race condition can occur, or be empty if race condition is not possible. If there are several race conditions, output any of them. State of program is described by specifying the zero-based index of current instruction for each thread in the order in which the threads are presented in input file. For a terminated thread, output $-1$ as the index. The indexes must be on a single line and separated by spaces. \fe{Sample: } \begin{verbatim} MUTEXES.IN MUTEXES.OUT 2 0 1 5 a=5 1 3 b=a LOCK X c=a+b UNLOCK X 4 LOCK X c=2 UNLOCK X b=3 \end{verbatim} \newpage %****************** POLAND **************** \specialsection*{Division expression (Poland)} Division expression is an arithmetic expression of the form $$ x_1/x_2/x_2/.../x_k $$ where $x_i$ is a positive integer, for $i,(1\leq i \leq k)$ Division expression is evaluated from the left to the right. For instance the value of the expression $$ 1/2/1/2 $$ is $1/4$. One can put parentheses into expression in order to change its value. For example the value of the expression $$ (1/2)/(1/2) $$ is $1$. We are given a division expression $E$. Is it possible to put some parentheses into $E$ to get an expression $E'$ whose value is an integer number. \fe{Task: } Write a program that for each data set from a sequence of several data sets: \begin{itemize} \item reads an expression $E$ from the text file \verb|DIV.IN| \item verifies whether it is possible to put some parentheses in $E$ to get a new expression $E'$ whose value is an integer number, \item writes the result to the text file \verb|DIV.OUT| \end{itemize} \fe{Input data: } The first line of the file \verb|DIV.IN| contains one positive integer $d, (d\leq 5)$ not larger than $5$. This is the number of data sets. The data sets follow. The first line of each data set contain an integer $n, (2\leq n \leq 10000)$. This is the number of integers in the expression. Each of the following $n$ lines contains exactly one positive integer not greater than $1\,000\,000\,000$. The $i\,$th number is the $i\,$th integer in the expression. \fe{Output data: } For each $i,(1\leq i \leq d)$ your program should write to the $i\,$th line of the output file \verb|DIV.OUT| one word \verb|YES|, if the $i\,$th input expression can be transformed into an expression whose value is an integer number, and the word \verb|NO| in the other case. \fe{Example: } For the input file \verb|DIV.IN|: \begin{verbatim} 2 4 1 2 1 2 3 1 2 3 \end{verbatim} the correct result is the output file: \begin{verbatim} YES NO \end{verbatim} \newpage %******************** SWEDEN ************************** \specialsection*{Time Zones (Sweden)} \fe{Task: } You're a businessman that has people all over the world. During one day you get \ku{exactly} one message from \ku{each} time zone. The messages come with a time. Unfortunately due to a millennium bug their local time is given without anything that identifies their time zone. Your task is to identify from which time zones the messages originated. In this task the number of hours in one day varies between $5 \ldots 60$. The number of time zones is always the same as the number of hours and each time zone has a time displacement which is an integral number of hours. You are receiving the calls in GMT, that is in time zone $0$ without time displacement. Your are also receiving one call from your own time zone. All the time zones (except your own) lies to the west of you. That is, to get the time in your time zone you should add an integral number of hours to the local time in the other time zone. For example, if the local time in time zone $2$ is $03$:$15$ it is $05$:$15$ in your zone (GMT). No two messages arrive at the same minute. And all between $0$:$00$-$23$:$59$ (in the case of a $24$-hour day). \fe{Input data: } The first contains the number of time zones, $n, 5\leq n \leq 60$, which also is the number of hours in one day and the number of messages you received. The following $n$ rows contains a time given as \verb|hhmm| ($2$ digits hours and $2$ digits minutes where hours is between $0$ and $n-1$ and minutes between $0$ and $59$). The rows are ordered in chronological order, i.e. the first call that arrived is on the first row. There is one unique solution in all given test examples. \fe{Output data: } One row containing $n$ numbers from $0$ to $n-1$ identifying in which time zones the $n$ calls originated. The first number corresponds to the first time given in the input etc. \fe{Example: } \verb|INPUT.DAT|: \begin{verbatim} 5 0017 0250 0400 0201 0002 \end{verbatim} \verb|OUTPUT.DAT|: \begin{verbatim} 3 1 0 2 4 \end{verbatim} Note that call $3$ must come from time-zone $0$ or it would have arrived at a time later than $4$:$59$ which is the last minute in the $5$-hour days in this example. \end{document}