The IOI 2011 Competition - Practice Tasks

Return to IOI 2011 Home

Alphabets

You would like to transmit integer data through a special channel, i.e., this channel only supports transmission of alphabets a - z. In order to do so, you have to encode the data into a sequence of alphabets, transmit the encoded data, and decode it to obtain the original integer data.

The overall process is shown in the following figure.

process overview

Your task

You have to implement:

Procedure encode(N,D) that encodes the data, where N denotes the length of data and D is an array of integers representing the data, where D[i] is the i-th integer in the data. (0 <= D[i] <= 255.) This procedure must call procedure send_data(c) for each character c in the sequence to transmit the encoded data. Each encoded character c must be lowercase English alphabets, i.e., alphabets a - z.
Procedure decode(M) that decodes the data, where M denotes the length of the encoded data. To read the encoded data as a sequence of characters, this procedure must call procedure read_data() for each character in the sequence. It may call read_data for at most M times. To output the decoded data, it must call procedure output_data(y) for each integer y in the decoded data.

Example

Consider as an example the case where N = 3, and D = 10 20 30.

Procedure encode, using some strange method, may encode the message as axsdxa; it should call procedure send_data as follows:

send_data('a')

send_data('x')

send_data('s')

send_data('d')

send_data('x')

send_data('a')

Note that the data length M = 6. When decode calls procedure read_data, the return values are:

calls	returns
`read_data()`	`'a'`
`read_data()`	`'x'`
`read_data()`	`'s'`
`read_data()`	`'d'`
`read_data()`	`'x'`
`read_data()`	`'a'`

The decode procedure should produce the output by calling procedure output_data as follows.

output_data(10)

output_data(20)

output_data(30)

Remarks: the encoded message here is chosen randomly to illustrate the task idea.

Subtasks

Subtask 1 (30 points)

N <= 100 and 0 <= D[i] <= 25.
The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

Subtask 2 (30 points)

N <= 100.
The encoded data should not contain more than 100N characters, i.e., encode may not call send_data more than 100N times.

Subtask 3 (40 points)

N <= 100.
The encoded message should not contain more than 2N characters, i.e., encode may not call send_data more than 2N times.

Implementation details

To be implemented by contestant:
- encoder.c or encoder.cpp or encoder.pas
- decoder.c or decoder.cpp or decoder.pas
Notes for C/C++ programmers: in the sample graders, encoder.c[pp] and decoder.c[pp] will be linked together with the grader; therefore, you should declare all global variables inside each file as static to prevent them from interfering with varaibles from other files.
Contestant interface:
- encoder.h or encoder.pas
- decoder.h or decoder.pas
Grader interface:
- encoderlib.h or encoderlib.pas
- decoderlib.h or decoderlib.pas
Sample grader: grader.c or grader.cpp or grader.pas
Sample grader input: grader.in.1, grader.in.2, ...
Note:
- The sample grader reads N and D from standard input.
- The grader ensures that the encoded messages are no longer than 100N characters. If you want to change this (e.g., to work on Subtask 3), you can change the limit in procedure size_limit in grader.c, grader.cpp, or graderlib.pas.
Expected output for sample grader input: grader.expect.1, grader.expect.2, ...
Compile and run (command line): runc grader.c or runc grader.cpp or runc grader.pas
Compile and run (gedit plugin): Control-R, while editing any implementation or grader file.
CPU time limit: 1 seconds
Memory limit: 256 MB

Hottest

Thailand is a tropical country. Thai people usually say that Thailand has 3 seasons: Hot Summer, Hotter Summer, and Hottest Summer. It especially feels very hot when you have many consecutive days with high temperatures.

You are planning a K-day trip to Thailand. Since you would like to experience the real Thai Summer, you want your stay to be as hot as possible.

You are given a list of forecasted temperatures of N consecutive days. You would like to find the maximum sum of temperatures of K consecutive days. It is guaranteed that 1 <= K <= N.

Your task

You are to implement procedure maxk(N,T,K) that returns the maximum sum of temperatures of any K consecutive days, where N is the number of days and T is an array of positive integers where T[i], for 0 <= i < N, is the temperature of day i.

Example

Suppose that N=6, K=3 and T = 10 50 30 20 5 1.

There are 4 possible 3-day trips, starting from day 0, day 1, day 2, and day 3; and their sum of temperatures are 90, 100, 55, and 26. Therefore, procedure maxk should return 100.

Subtasks

Subtask 1 (50 points)

N <= 1 000, 0 < T[i] <= 1 000

Subtask 2 (50 points)

N <= 1 000 000, 0 < T[i] <= 1 000

Implementation details

To be implemented by contestant: hottest.c or hottest.cpp or hottest.pas
Contestant interface: hottest.h or hottest.pas
Grader interface: none
Sample grader: grader.c or grader.cpp or grader.pas
Sample grader input: grader.in.1, grader.in.2, ...
Note: the sample grader reads N, K, and T_i's, and the expected solution from standard input.
Expected output for sample grader input: grader.expect.1, grader.expect.2, ...
Compile and run (command line): runc grader.c or runc grader.cpp or runc g rader.pas
Compile and run (gedit plugin): Control-R, while editing any implementation or grader file.
CPU time limit: 2 seconds
Memory limit: 256 MB

Valley

Animal behavior researchers would like to get information on animal movements in a valley. They have placed N motion sensors along a straight line crossing the valley at various heights. For 0 <= i <= N-1, the i-th sensor's height is h_i (0 <= h_i <= 1 000 000 000). No two sensors are on the same height.

Since the line is on a valley, the heights of sensors satisfy these constraints:

there is an integer k (0 <= k <= N-1), such that the k-th sensor has the minimum height,
for all 0 <= i < k, h_i > h_i+1, and
for all k <= i < N-1, h_i < h_i+1.

However, because the sensor installation team forgot to measure the sensors' heights, the value of k, and all the heights h_i's are not known.

You would like to find if there is a sensor at height X. This seems to be hopelessly impossible, but you recall that each sensor has a height meter and can report its height. To minimize the power usage, you would like to make only a small number of height queries.

Your task

You have to implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise. Your procedure can call a procedure query(i) to get h_i. However, you can make at most 50 calls, for each run of procedure find.

Note: In a single run, the sample grader, provided with the prototype, may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to procedure find. Therefore, you should not assume that two different calls to procedure find share the same height information.

Example

Suppose that N=4 and the height of each sensor is:

sensor	height
0	10
1	7
2	9
3	15

Note that in this case, k=1. The following are the return values from procedure query:

calls	returns
`query(0)`	`10`
`query(1)`	`7`
`query(2)`	`9`
`query(3)`	`15`

The correct implementation of procedure find, when called by the grader, should return as in the following table.

calls	returns
`find(4,10)`	`1`
`find(4,2)`	`0`
`find(4,9)`	`1`
`find(4,15)`	`1`
`find(4,100)`	`0`

Subtasks

Subtask 1 (25 points)

N <= 35.

Subtask 2 (25 points)

N <= 1 000; and k = 0.

Subtask 3 (25 points)

N <= 200.

Subtask 3 (25 points)

N <= 1 000.

Implementation details

To be implemented by contestant: valley.c or valley.cpp or valley.pas
Contestant interface: valley.h or valley.pas
Grader interface: graderlib.h or graderlib.pas
Sample grader: grader.c or grader.cpp or grader.pas
Sample grader input: grader.in.1, grader.in.2, ...
Note:
- The sample grader reads N, h_i's, the number of X's, and X's from the standard input.
- In a single run, the sample grader may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to find. Therefore, it is safe to assume that the heights change between different calls to find.
Expected output for sample grader input: grader.expect.1, grader.expect.2, ...
Compile and run (command line): runc grader.c or runc grader.cpp or runc g rader.pas
Compile and run (gedit plugin): Control-R, while editing any implementation or grader file.
CPU time limit: The grader would make 100 calls to procedure find; the total running time should be within 1 second.
Memory limit: 256 MB