Home
18th NOI
Committee
Eligibility
Rules & Regulations
Programme
Coding Environment
Instructions (PDF)
About NOI
About NOI
Acknowledgment
About IOI
Competition
Problem Sets
Results
Support
Contacts

 


Tasks Archive : 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 05 (Prelim) | 04 | 03 | 02 | 01 | 00 | 99 | 98

NOI 2004 TASKS

 
Overview (Word format)
Task Statements: [ pfd | postscript ]
Overview
  Executable file Input file Output file
Task 1: GRAY GRAY.EXE GRAY.IN GRAY.OUT
Task 2: LAMP LAMP.EXE LAMP.IN LAMP.OUT
Task 3: DOMINO DOMINO.EXE DOMINO.IN DOMINO.OUT
Task 4: TRAIN TRAIN.EXE TRAIN.IN TRAIN.OUT
Task 5: SMALL SMALL.EXE SMALL.IN SMALL.OUT
Task 6: RNA RNA.EXE RNA.IN RNA.OUT

Notes:
  1. Each task will be tested on 5 data sets.
  2. The maximum execution time for every task is 5 seconds.
  3. Each data set is worth 20 points.
  4. Either zero mark or full mark (20 points) is awarded to your answer to each data set. There is no partial credit.
  5. The task statements are contained on 14 pages following this overview page.
  6. In the event of tie breaking, a bigger-numbered task is favoured over a smaller-numbered one.

Task 1: GRAY
A binary number is a number in base 2, where the individual digits, or bits, have weights in powers of two. For example, the decimal number 23 is written as 10111 in binary because:

(1 × 24) + (0 × 23) + (1 × 22) + (1 × 21) + (1 × 20) = (1 × 16) + (1 × 4) + (1 × 2) + (1 × 1) = 23.

A Gray code sequence consists of a sequence of binary values, in which each value differs from its immediate predecessor by only a single bit. The following example shows a standard Gray code sequence of 3-bit binary numbers.

Binary sequence 000 001 010 011 100 101 110 111
Standard Gray code sequence 000 001 011 010 110 111 101 100

A very simple algorithm is available to convert a binary number into its equicalent standard Gray code value. For example, to convert binary value 011, we start by copying the first bit:

011
v  
0  

To obtain the second bit, we add the first and second bits of the given binary number, to get the sum 0 + 1 = 1:

0+11
  v 
0 1 

To obtain the third bit, we add teh second and third bits of the given binary number, to get the sum 1 + 1 = 10 (in binary), but we discard the carry bit so we just take the rightmost bit 0 of the sum:

01+1
   v
01 0

Hence our answer is 010.

In general, except the first bit, the k-th bit of the standard Gray code is obtained by adding the (k-1)-th bit and the k-th bit of the given binary number and discarding the carry. The discard-carry addition operation can be described completely as:

 0      0      1      1
+0     +1     +0     +1

    
    
    
 0      1      1      0

    
    
    

As another example, the 5-bit binary number 10101 is converted to its equivalent standard Gray code value 11111 by applying the above algorithm. The table below shows a few more examples.

Binary value Equivalent standard Gray code value
01110 01001
111111 100000
1001001 1101101
000111000 000100100

You are to write a program to convert an n-bit binary value into its equivalent n-bit standard Gray code value, where 1 ≤ n ≤ 20.

Input
The input file GRAY.IN consists of two lines, each line containing one integer.
  1. The first line contains the integer n, the number of bits, where 1 ≤ n ≤ 20.
  2. The second line contains a bit-string of length n representing the n-bit binary number.
Output
The output file GRAY.OUT contains a bit-string of length n representing the standard Gray code equivalent of the given n-bit binary number.

Input/Output Example
For the first example given above, the input and output files contain:

Sample Input
                3
                011 
Sample Output
                010 

Task #1 Input files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]
Task #1 Output files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]

Task 2: LAMP
A building has a long corridor and L ceiling lamps labeled 1, 2, 3, ..., L. Each lamp has an individual switch that can turn the lamp on or off. The building manager hires G security guards (no two guards have the same name), whose job at night is to patrol the corridor and turn the lamps on and off. Each guard is assigned a subset of lamps. During one patrol round, a guard will walk along the corridor, and toggle the lamps assigned to him/her (that is, if a lamp is on, switch it off; if the lamp is off, switch it on). After a guard toggles each lamp assigned to him/her exactly once, the guard will take a break until his/her next patrol round. A guard may have more than one patrol round in one night. The order of patrol for the guards is dictated by a duty roster.

All lamps are off before the guards begin their patrol rounds, and there is only one guard on patrol at any time.

The assignment of lamps to a guard is specified by two positive integers, a0 and d. The subset of lamps the guard will toggle is

{a0, a0 + d, a0 + 2d, ..., a0 + kd}


where k is the largest integer such that a0 + kdL.

Given the lamp assignment for each guard and the duty roster, find out how many lamps are on after all the guards have finished all of their patrol rounds.

Example
Suppose we have 10 lamps, two security guards (Edi and Lou), and three patrol rounds. Edi's lamp assignment is (a0, d) = (1, 4) and Lou's lamp assignment is (a0, d) = (2, 3). The order of patrol is Edi, Lou, Edi.

After the first patrol round by Edi, lamps 1, 5, and 9 will be on. During the second patrol round, Lou toggles lamps 2, 5, and 8. Therefore, after the second patrol round, lamps 1, 2, 8, and 9 are on but lamp 5 has been turned off. On the third patrol round, Edi patrols again, and toggles lamps 1, 5, and 9. Consequently, after all the patrol rounds specified in the duty roster, the lamps that are on are 2, 5, and 8.

The number of lamps that are still on after the guards finish their patrol rounds is therefore 3.

Input
The first line in the input file LAMP.IN consists of three positive integers, separated with a blank character. The first number L ≤ 1000 is the number of lamps. The second number G ≤ 10 is the number of security guards, and the third number R ≤ 50 is the total number of patrol rounds. The next G lines contain the names and lamp assignments of the guards. Each of these G lines consists of the name (exactly 3 English letters), a0 and d, (a0N) separated with a blank character. The subsequent R lines specify the duty roster. Each line contains the name of a guard (guaranteed to have lamp assignment). The order of the guards appearing in the duty roster dictates the order of their patrol.

Output
The output file LAMP.OUT contains one integer which is the number of lamps that are on after all guards finish all of their patrol rounds.

Input/Output Example
For the above example, the input and output files contain:

Sample Input
                10 2 3
                Edi 1 4
                Lou 2 3
                Edi
                Lou
                Edi 
Sample Output
                3 

Task #2 Input files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]
Task #2 Output files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]

Task 3: DOMINO
You are given a set of 2n dominos, where n < 1000 is an integer. The dominos have width 1 and length 2. It is possible to arrange these dominos in such a way that they form a 4 × n rectangle. For instance, in Figure 1, we have arranged 12 dominos to form a 4 × 6 rectangle.

Figure 1: Example with n = 6.

In fact, where n > 1, there are several ways of arranging dominos to form a 4 × n rectangle. For instance, in Figure 2, you can see the 5 different ways of forming a 4 × 2 rectangle:

Figure 2: The 5 different ways of forming a 4 × 2 rectangle.

We denote by Rn the number of different ways of forming a 4 × n rectangle with 2n dominos. For instance, R2 = 5, as you can see in Figure 2. As Rn can be quite large, even for small values of n, you are only asked to compute the last three digits of Rn. Your program should output the value of the last three digits of Rn without leading zeros. For instance, R17 = 26915305, so when n = 17, your program should output 305 (the last three digits). Another example, R2 = 5 (or 005), so when n = 2, your program should output 5. Should the last three digits be zeros for some Rn, your program should simply output 0.

Input
The file DOMINO.IN contains the integer n. Remember that n < 1000.

Output
You should write an integer giving the value of the last three digits of Rn without leading zeros in the output file DOMINO.OUT. (Note that the output value is simply the value Rn mod 1000; that is, the remainder of Rn divided by 1000.)

Input/Output Examples
For the example R2 = 5, the input and output files contain

Sample input 1
                2 
Sample output 1
                5 
For the example R17 = 26915305, the input and output files contain

Sample input 2
                17 
Sample output 2
                305 

Task #3 Input files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]
Task #3 Output files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]

Task 4: TRAIN
Consider the following configuration of train tracks.


Tracks I, II, and III may hold train cars that can move in one go between Track I and Track III, and between Track II and Track III, but not between Track I and Track II. Cars cannot pass each other on a track in one go. Cars can move together in one go. In the situation depicted above, the cars G and A can move together in one go from Tack III to Track I, after which the sequence of cars on Track I is B, F, F, G, A. However, the car A cannot move alone in one go from Track III to Track I (because to do so it has to pass car G but this is not allowed). Each track is long enough to hold all cars.

Initially, a sequence of cars is on Track I, and Tracks II and III are empty. The goal is to move cars between Tracks I and III and between Tracks II and III, such that a desired sequence of cars, and no other cars, resides on Track II. The question to be answered by your program is: What is the smallest number of movements that achieves the desired sequence of cars, and no other cars, on Track II? Note that when two or more adjacent cars move together in one go, it counts as one single movement.

Example
Let us say initially, the cars A, B, C, D and E are on Track I in the order ABCDE. This means that the car A is furthest to the left, and car E is furthest to the right and closest to Track III. Let us say at the end, we want the sequence DBC on Track II. We can achieve this with four movements. First, we move the cars D and E together from Track I to Track III, then we move car D from Track III to Track II, then we move the cars B and C together from Track I to Track III, and finally, we move the cars B and C together from Track III to Track II. Figure 3 shows teh sequence of movements. The answer therefore is the number 4.

Figure 3: Movements for example.

Input
The input file TRAIN.IN consists of three lines. The first line contains two integers, separated with a blank character. The first integer i represents the initial number of cars on Track I, and the second number j represents the number of desired cars on Track II. The second line contains i capital letters, representing the initial sequence of cars on Track I. The third line contains j capital letters representing the desired sequence of cars on Track II.

You may assume that all letters in the second line are distinct, that all letters in the third line are distinct, and that every letter in the third line occurs in the second line, and that 0 < j < 7, 0 < i < 7.

Output
The output file TRAIN.OUT contains an integer, representing the minimal number of movements to achieve the desired sequence of cars in Track II.

Input/Output Example
For the above example, the input and output files contain:

Sample Input
                5 3
                ABCDE
                DBC 
Sample Output
                4 

Task #4 Input files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]
Task #4 Output files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]


Task 5: SMALL
An n-bit shift register is a memory for holding n bits; its contents can be modified in only two possible ways: the contents are left shifted by one position and the rightmost bit is given a 0 or a 1. We call such a modification a "move". For example, when the contents of a 4-bit shift register are 0001, after one move the contents can become either 0010 (if the rightmost bit is given a 0) or 0011 (if the rightmost bit is given a 1). Consider an n-bit shift register whose contents are initially all zeroes. We need to construct a sequence of moves such that after each move the contents of the shift register are unique, that is, different from all its past contents. Since an n-bit shift register has 2n possible contents, the longest such sequence can be of length 2n. It is known that for an n-bit shift register, there are always one or more such sequences of length 2n. For example, when n=3, there are two such sequences of length 23=8:

A = 000 001 010 101 011 111 110 100
B = 000 001 011 111 110 101 010 100

LNR (Longest Non-Repeating) Sequences
Given a positive integer n, consider any sequence which satisfies the following properties:
  1. each element of the sequence is a bit-string of length n,
  2. there are 2n elements in the sequence,
  3. there is no repetition in the sequence,
  4. all the n bits of the first element are zero,
  5. any element in the sequence (apart from the first element) is derived from its previous element via a move described above.
We call any such sequence a Longest-Non-Repeating or LNR sequence. Given a positive integer n, the set of all LNR sequences (each of which satisfies the above five properties) is denoted as S(n).

The Smallest LNR Sequence
Any LNR Sequence s e S (n) can be associated with a value denoted as value(s) in the following way: we concatenate the 2n bit-strings in s to form a single bit-string. The value of this bit-string, considered as a binary number, is value(s). Thus, for the LNR sequence

A = 000 001 010 101 011 111 110 100

in our example above, we have

value(A) = 000001010101011111110100

We can now define the smallest LNR sequence ssmall(n) as the LNR sequence s in S(n) which yields the smallest value(s).

Example
For n=3, the set of all LNR sequences is given by

S(3) = {A, B}

where A and B are the sequences discussed earlier. Note that

value(A) < value(B),

so

ssmall(3) = A.

The positions of the bit-strings

000, 001, 010, 101, 011, 111, 110, 100

in A are respectively

1, 2, 3, 4, 5, 6, 7, 8.

What you need to do
Given a positive integer n ≤ 10 and bit-string s of length n, your program should compute ssmall(n) and output the position of s in ssmall(n). That is, your program should output 1 if s is the first element of ssmall(n), output 2 if s is the second element of ssmall(n), etc.

Input
The input file SMALL.IN consists of two lines. The first line contains a positive integer n ≤ 10. The second line contains a bit-string s of length n.

Output
The output file SMALL.OUT contains a single positive integer giving the position of s in ssmall(n).

Input/Output Example
In the above example, ssmall(3) is the sequence A and bit-string 111 is the 6-th element of A. Consequently, we have the following sample input and output.

Sample Input
                3
                111 
Sample Output
                6 
Hint
Do not try to construct all LNR sequences and then find the smallest LNR sequence. You can find the smallest LNR sequence by preferring left-shift moves where a "0" is shifted in (over those moves where a "1" is shifted in).

Task #5 Input files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]
Task #5 Output files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]


Task 6: RNA
RNA is an important molecule in our body. The structure of an RNA molecule can be described by a pair (S, P) where
  1. S = s1 s2 ... sn and P = p1 p2 ... pn for some positive integer n ≤ 450.
  2. Each element si of S is one of the letters A, C, G, U.
  3. Each element pi of P is an asterisk, a left parenthesis, or a right parenthesis.
  4. Furthermore, the sequence P is a sequence of balanced parentheses. This means, after ignoring the asterisks (if any), each left parenthesis can be matched by a unique succeeding right parenthesis and each right parentheses can be matched by a unique preceding left parenthesis.
For example, below shows two RNA structures: A1 = (S1, P1) (on the left) and A2 = (S2, P2) (on the right).

ACCCGAACUU               AAUAUCCCGAAU
((**)*(*))               *(**)(**)*()

Given two RNA structures A = (S,P) and A' = (S',P'), A' is called a substructure of A if there exist integer ij such that S' = si ... sj and P' = pi ... pj. (Note that the parentheses of P' should be balanced since A' = (S',P') is an RNA structure.) For example, A3 = (S3, P3) which is

CCCG
(**)

is a substructure of A1, but A4 = (S4, P4) which is

ACCCGAACU
((**)*(*)

is not a substructure of A1 because P4 is not a sequence of balanced parentheses.

For two RNA structures X and Y, if Z is a substructure of both of them, Z is called a common substructure of X and Y, A longest common substructure is a common substructure with maximum length among all common substructures.

For example, for the above A1 and A2, their longest common substructure has length 5 and is

CCCGA
(**)*

Note that the following example is not a common substructure of A1 and A2, because the parentheses are not balanced.

CCCGAA
(**)*(

In this task, given two RNA structures of length at most 450, you are required to report the length of a longest common substructure.

Input
The input file RNA.IN consists of 4 lines. The first two lines are the RNA sequence (first line) and the parenthesis sequence (second line) for the first RNA. The last two lines are the RNA sequence (third line) and the parenthesis sequence (fourth line) for the second RNA. Remember the length of each sequence is at most 450.

Output
The output file RNA.OUT contains a single integer which represents the length of a longest common substructure.

Input/Output Example
For the above example, the input and output files contain

Sample Input
                ACCCGAACUU
                ((**)*(*))
                AAUAUCCCGAAU
                *(**)(**)*() 
Sample Output
                5 

Task #6 Input files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]
Task #6 Output files: [ Set #1 | Set #2 | Set #3 | Set #4 | Set #5 ]

Design by Techsailor Group