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 2001 TASKS

Overview (Word format)
Task Statements (Word format) | (Postscript)

Overview
  Executable file Input file Output file
Task 1: MAX MAX.EXE MAX.IN MAX.OUT
Task 2: KANSAS KANSAS.EXE KANSAS.IN KANSAS.OUT
Task 3: CARS CARS.EXE CARS.IN CARS.OUT
Task 4: ZEROS ZEROS.EXE ZEROS.IN ZEROS.OUT
Task 5: RANK RANK.EXE RANK.IN RANK.OUT
Task 6: FAX FAX.EXE FAX.IN FAX.OUT
Task 7: CUBE CUBE.EXE CUBE.IN CUBE.OUT

Notes:
  1. Each task will be tested on 5 data sets.
  2. Each data set worths 20 points.
  3. Either zero mark or full mark (20 points) is awarded to your answer to each data set. There is no partial credit.
  4. The maximum execution time for each run is 5 seconds.
  5. The task statements are contained on 11 pages following this overview page.

Task 1: MAX
Description. In a sequence of integers, the number of times an integer occurs is called the frequency of the integer. Given a sequence of integers, find the highest frequency.

Input. The input file MAX.IN consists of several lines. The first line contains a single integer N (1 <= N <= 10000) denoting the number of integers in the sequence. Each of the subsequent N lines contains an integer n (1 <= n <= 1000) in the sequence.

Output. The output file MAX.OUT contains an integer that is the highest frequency of the sequence.

Example 1. The input file
                12
                1
                2
                5
                6
                3
                7
                11
                345
                754
                2
                5
                2 
gives the 12-integer sequence 1, 2, 5, 6, 3, 7, 11, 345, 754, 2, 5, 2. Integer 2 occurs 3 times and no other integer occurs more than twice. So 3 is the highest frequency and thus the output file contains the number
                3 
Example 2. The input file
                7
                2
                4
                6
                7
                7
                2
                4 
gives the 7-integer sequence 2, 4, 6, 7, 7, 2, 4. Integers 2, 4, 7 each occurs 2 times but integer 6 occurs once. So 2 is the highest frequency and thus the output file contains the number
                2 

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: KANSAS
Description. The road map of Kansas, USA, is a grid where there are straight roads North-South and straight roads East-West each 1 mile apart. A truck driver gets instructions in the following form. Drive for two hours north at 45 miles per hour, then for 5 hours west at 65 miles per hour, etc. The driver will have to take a break of 1 hour after 5 hours of continuous driving. The aim is to compute, after how many breaks the driver for the first time passes through or finally returns to the place where she started from.

Example 1. Drive for two hours south at 30 miles per hour, then for four hours west at 40 miles per hour, then for three hours north at 20 miles per hour, then for six hours east at 60 miles per hour, then for five hours north at 30 miles per hour, and then for six hours south at 60 miles per hour.

When following these instructions, the driver will be passing through where she started from after taking two breaks.

Example 2. Drive for one hour south at 30 miles per hour, then for two hours west at 40 miles per hour, then for one hour north at 30 miles per hour, then for one hour east at 79 miles per hour, and then for five hours north at 30 miles per hour.

When following these instructions, the driver will neither pass through nor be back where she started from.

Example 3. Drive for four hours west at 60 miles per hour, then drive for eight hours north at 80 miles per hour, then drive for four hours east at 60 miles per hour, then drive for eight hours south at 100 miles per hour, then drive for ten hours east at 20 miles per hour.

When following these instructions, the driver will pass through where she started from after taking 4 breaks.

Input. The input file KANSAS.IN consists of several lines. The first line contains an integer (<= 1000) which is the number of instructions, followed by one line for each instruction, indicating the direction, the number of hours h (1 <= h <= 200) and the speed s (1 <= s <= 200) in miles per hour in this order. The geographical directions are indicated by the position of the small hand on an analog clock; 12 stands for north, 6 for south, 9 for west, and 3 for east.

Thus the input files for the examples will look as follows.

Example 1.
                6
                6 2 30
                9 4 40
                12 3 20
                3 6 60
                12 5 30
                6 6 60 
Example 2.
                5
                6 1 30
                9 2 40
                12 1 30
                3 1 79
                12 5 30 
Example 3.
                5
                9 4 60
                12 8 80
                3 4 60
                6 8 100
                3 10 20 

Output. The output file KANSAS.OUT contains an integer which is the number of breaks taken before the driver for the first time passes through or finally returns to the place where she started from. If the driver does not reach or pass through the place where she started from after following all instructions, the output file should contain the number -1.

Thus the output files for the examples are as follows.

Example 1.
                2 
Example 2.
                -1 
Example 3.
                4 

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: CARS
Description. On a straight single-lane road, there are n cars parked with a space of d meters wide separating every two adjacent cars. The cars will start to move successively in the same direction as follows.

At the beginning, the first car moves at a speed of v meters per second, while the other cars are standing still. After every 5 seconds from the beginning, every car checks the distance to the car in front or behind, and adapts its speed, if necessary.

The first car adapts as follows. If there is less than 80 meters space to the car behind it, it immediately increases its speed by 5 meters per second; if there is more than 100 meters space to the car behind it, it immediately decreases its speed by 5 meters per second; and otherwise it keeps its speed.

All the other cars adapt as follows. If there is less than 80 meters space to the car in front, it immediately decreases its speed by 5 meters per second; if there is more than 100 meters space to the car in front, it immediately increases its speed by 5 meters per second; and otherwise it keeps its speed.

Against the laws of physics, any change of speed takes immediate effect. If a car stands still and needs to decrease speed, it will remain standing still; the cars never go backwards. A collision occurs, if the space between two cars becomes 0 or less.

The goal is to find out, if a collision has occurred after t 5-second-intervals, and if not, how far the first car will have traveled.

Note that the length of the cars is irrelevant.

Example 1. There are n = 5 cars. The first car starts with v = 10 meters per second, there are d = 80 meters between adjacent cars and there are t = 3 5-second-intervals. First period: The first car will travel 10*5 = 50 meters in the first period, while all other cars stand still in this period. Second period: At the beginning of the second period, the first car decelerates to a speed of 5 meters per second, because there is now 130 meters space to the car behind, and thus travels 5 * 5 = 25 meters in the second period. At the beginning of the second period, the second car accelerates to a speed of 5 meters per second, because there is 130 meters space to the car in front, and thus travels 5 * 5 = 25 meters in the second period. At the beginning of the second period, all other cars remain standing, because there still are 80 meters space to the car in front. Third period: At the beginning of the third period, the first car decelerates to a speed of 0 meters per second, because there is again 130 meters space to the car behind, and thus travels 0 * 5 = 0 meter in the third period.
Answer: The first car will have traveled 50 + 25 + 0 = 75 meters after the first three periods.

Example 2. There are n = 2 cars. The first car starts with v = 60 meters per second, there are d = 100 meters between adjacent cars and there are t = 14 5-second-intervals.
Answer: A collision occurs.

Example 3. There are n = 20 cars. The first car starts with v = 5 meters per second, there are d = 5 meters between adjacent cars and there are t = 100 5-second-intervals.
Answer: The first car will have traveled 2550 meters.

Input. The input file CARS.IN consists of a line containing the four integers n, v, d, and t in this order, and 1 <= n, v, d, t <= 1000.

Thus the input files for the examples will look as follows.

Example 1.
                5 10 80 3
Example 2.
                2 60 100 14
Example 3.
                20 5 5 100

Output. The output file CARS.OUT contains the number of meters traveled by the first car if there is no collision. If there is a collision, the output file should contain -1.

Thus the output files for the examples will look as follows.

Example 1.
                75
Example 2.
                -1
Example 3.
                2550

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: ZEROS
Description. The factorial of a positive integer n, written as n!, is the product of the first n positive integers. That is,
n! = 1 × 2 × … × n
Given a positive integer n, find the number of zeros in the decimal representation of n!. Of course, leading zeros should not be counted. (Note that decimal representation means base ten representation.)

Example 1. There are 7 zeros in the decimal representation of 20!.
20! = 1 × 2 × … × 19 × 20 = 2432902008176640000

Example 2. There are 2 zeros in the decimal representation of 7!.
7! = 1 × 2 × 3 × 4 × 5 × 6 × 7 = 5040

Example 3. There is 0 zero in the decimal representation of 4!.
4! = 1 × 2 × 3 × 4 = 24


Input and Output. The input file ZEROS.IN contains a single positive integer n < 100. The output file ZEROS.OUT contains a single integer giving the number of zeros in the decimal representation of n!.

For Example 1, the input file is
                20
and the output file is
                7

For Example 2, the input file is
                7
and the output file is
                2

For Example 3, the input file is
                4
and the output file is
                0

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: RANK
Description. In a tournament of N players and K games, each game involves 2 players. A player may play any number of games, but in each game his opponent must be a different person. A player needs not play with everybody (it is even possible, though strange, that a player does not play any game at all!). In a game, there is no draw – a player either wins or losses.

After all the games have been played, the players are ranked. There are a few situations where ranking is not possible, but here we are interested only in one particular situation where more than 2 players are involved in a ‘cyclic’ order. One example is as follows: player A beats player B, player B beats player C, and player C in turns beats player A. In this case, the relative ranking of these 3 players cannot be determined.

Note that a player may be involved in more than one cyclic ordering; when this happens, the player should be counted only once.

(Since we are only interested in players involved in cyclic ordering, those players whose ranking cannot be determined due to other reasons — for instance, a player who did not play any game at all — should not be considered here. See the examples.)

You are given a list of games and their results, and you are to find the total number of players whose ranking cannot be determined due to cyclic ordering.

Input. The input file RANK.IN consists of several lines.

The first line contains 2 integers N (2 <= N <= 20) and K (1 <= K <= 30) in this order, where N is the number of players, and K the number of games played. The players are identified by the integers 1, 2, 3, …, N.

There are K lines after the first line. Each of the K lines contains 4 integers a b sa sb representing the result of a game: a and b are the identifiers of the players, and sa and sb are the scores of players a and b respectively. All scores are non-negative integers less than 10, and the player with the larger score wins.

The input file below represents the results of a 10-player/12-game tournament:
                10 12
                1 8 2 1
                1 2 5 0
                10 7 1 2
                6 9 6 9
                3 4 3 1
                9 5 3 1
                8 2 6 8
                4 9 3 0
                4 1 5 2
                6 10 3 5
                3 5 1 9
                6 7 9 8 
Player 1 beats player 8 in game 1, player 1 beats player 2 in game 2, player 7 beats player 10 in game 3, etc.

Output. The output file RANK.OUT contains an integer which is the number of players whose ranking cannot be determined due to cyclic ordering.

In the above example, players 3, 4, 5, 9 are in one cycle, and players 6, 7, 10 in another. The output file should thus contain the number
                7 

Example 1. The input file
                5 3 
                1 3 9 7
                5 1 9 2
                3 5 2 0 
describes a 5-player/3-game tournament. Players 1, 3 and 5 are involved in a cyclic ordering, whereas players 2 and 4 did not play. The output file should contain the number
                3 

Example 2. The input file
                5 6 
                1 2 2 1
                1 5 2 1
                1 3 2 1
                5 2 0 5
                5 3 1 8
                2 4 4 2 
describes a 5-player/6-game tournament. There is no cycle in this case, so the output file contains the number
                0 

Example 3. The input file
                10 5
                2 4 0 2
                2 6 5 3
                8 2 8 2
                6 4 6 2
                8 6 0 2 
describes a 10-player/5-game tournament. There are 2 cycles: players 2, 4, 6 are involved in one cycle, while players 2, 6, 8 are in another. So players 2, 4, 6, 8 are involved in cyclic ordering and the output file should contain the number
                4 

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: FAX
Description. You are asked to design a compression scheme for transmitting fax images of documents. After an image is scanned in using a scanner, you obtain a sequence of numbers where each number x takes a value from 1 to 256. For example, an image may be converted into a sequence of the form
1, 1, 1, 1, 1, 46, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2,
1, 1, 1, 25, 26, 25, 25, 255, 256, 256, 256, 255, …

Since it is not necessary to transmit the exact image, you decide to discretize each number to 4 levels, namely 1, 86, 172 and 256, so that you can code each level using only 2 bits as follows
Level 1 86 172 256
Code 00 01 10 11

Then you realize that large areas of the same value (e.g. white) often occur in documents resulting in long sequences of very similar numbers. You decide to adopt a compression scheme as follows:
  1. For the first number in the sequence, you will use the 2 bits as described previously.
  2. For all other numbers:
    • if the previous number is the same as the current number, you will transmit the bit 0.
    • otherwise, you will transmit the bit 1 followed by the 2-bit code of the number. That is,
        – 1 followed by 00 for number 1,
        – 1 followed by 01 for number 86,
        – 1 followed by 10 for number 172,
        – 1 followed by 11 for number 256.
Finally, since you are not worried about a small amount of error, you realize that you can improve your scheme by ignoring isolated changes. For example, if the input sequence is 2, 2, 2, 2, 2, 46, 2, 2 and you transmit the sequence 1, 1, 1, 1, 1, 86, 1, 1, the total error will be 1 + 1 + 1 + 1 + 1 + 40 + 1 + 1 = 47 and the string that needs to be transmitted is 0000001011000. If, instead you choose to transmit the sequence 1, 1, 1, 1, 1, 1, 1, 1, the total error will be 1 + 1 + 1 + 1 + 1 + 45 + 1 + 1 = 52, but the string that needs to be transmitted would be 000000000 which is shorter.

You decide to measure the overall cost of a transmission by the following weighted sum
cost = total error + W × (total number of bits transmitted)
where
  1. the weight W can be adjusted to give more emphasis to either the total error or the total number of bits transmitted
  2. for an input sequence x1, x2, …, xN and a transmitted sequence y1, y2, …, yN, both of length N, the total error is Summation (i from 1 to N) |xi - yi| = |x1 - y1| + … + |xN - yN|.

Example. For the input sequence 2, 2, 2, 2, 2, 46, 2, 2 with W = 100,
  • we can transmit the sequence y1, …, y8 = 1, 1, 1, 1, 1, 86, 1, 1 by transmitting the string 0000001011000 with a cost of 47 + 100 × 13 = 1347;
  • or we can transmit the sequence y1, …, y8 = 1, 1, 1, 1, 1, 1, 1, 1 by transmitting the string 000000000 with a cost of 52 + 100 × 9 = 952.
In this case, the second option has lower cost.

Input. The input file FAX.IN consists of several lines. The first line contains two integers N (1 <= N <= 50) and W (1 <= W <= 100) in this order. Integer N denotes the length of the input sequence and integer W is the weight. Each of the subsequent N lines contains an integer x (1 <= x <= 256) of the sequence. For example, the input file
                8 100
                2
                2
                2
                2
                2
                46
                2
                2 
represents the 8-number sequence 2, 2, 2, 2, 2, 46, 2, 2 with W = 100.

Output. The output file FAX.OUT contains a single integer which is the smallest possible cost required to transmit the input sequence with the given value of W. For the input sequence given in the above example, the output file should contain the number
                952 

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 ]


Task 7: CUBE
Description. Folding six squares connected in some special ways can form a cube. For example, in the diagram below, the six squares on the left can be folded into a cube (with face 1 opposite face 4, face 2 opposite face 6, and face 3 opposite face 5) but the six squares on the right cannot be folded into a cube (faces 3 and 5 overlap).
Diagram 1

A 6 × 6 array is used to represent the six squares. Only 6 of the 36 cells are used to represent the 6 squares. A cell representing a square contains the number for the square. Other cells contain the number 0. Note that the same 6 squares can be represented in many ways. For example, the invalid six squares of the above example can be represented as follows (the one on the right is obtained after a 90 degree rotation of the one on the left):
                0 0 0 0 0 0         0 0 0 0 0 0
                0 3 0 5 0 0         0 0 0 0 0 0
                1 2 4 6 0 0         0 0 0 0 5 6
                0 0 0 0 0 0         0 0 0 0 0 4
                0 0 0 0 0 0         0 0 0 0 3 2
                0 0 0 0 0 0         0 0 0 0 0 1 
Given a square representation, determine if the squares can be folded into a cube; if so, find the face opposite face 1.

Input. The input file CUBE.IN consists of six lines with each line containing six integers. All but six of the input integers are zeros. The non-zero integers are 1, 2, 3, 4, 5, 6.

For example, the input file for the squares

Diagram 2
may look like
                0 0 0 0 0 0
                0 0 0 0 0 0
                0 0 1 0 0 0
                0 5 2 3 0 0
                0 0 4 0 0 0
                0 0 6 0 0 0 

Output. The output file CUBE.OUT consists of a single integer. The integer is 0 if the squares cannot be folded into a cube; otherwise, the integer is the number of the face opposite face 1.

For the above example, the output file should contain the number
                4

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


Design by Techsailor Group