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.
Your task
You have to implement:

Procedure
encode(N,D)
that encodes the data, whereN
denotes the length of data andD
is an array of integers representing the data, whereD[i]
is the ith integer in the data. (0 <=D[i]
<= 255.) This procedure must call proceduresend_data(c)
for each characterc
in the sequence to transmit the encoded data. Each encoded characterc
must be lowercase English alphabets, i.e., alphabetsa
z
. 
Procedure
decode(M)
that decodes the data, whereM
denotes the length of the encoded data. To read the encoded data as a sequence of characters, this procedure must call procedureread_data()
for each character in the sequence. It may callread_data
for at most M times. To output the decoded data, it must call procedureoutput_data(y)
for each integery
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 callsend_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 callsend_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 callsend_data
more than 2N times.
Implementation details

To be implemented by contestant:
encoder.c
orencoder.cpp
orencoder.pas
decoder.c
ordecoder.cpp
ordecoder.pas
Notes for C/C++ programmers: in the sample graders,
encoder.c[pp]
anddecoder.c[pp]
will be linked together with the grader; therefore, you should declare all global variables inside each file asstatic
to prevent them from interfering with varaibles from other files. 
Contestant interface:
encoder.h
orencoder.pas
decoder.h
ordecoder.pas
 Grader interface:
encoderlib.h
orencoderlib.pas
decoderlib.h
ordecoderlib.pas
 Sample grader:
grader.c
orgrader.cpp
orgrader.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
ingrader.c
,grader.cpp
, orgraderlib.pas
.
 Expected output for sample grader input:
grader.expect.1
,grader.expect.2
, ...  Compile and run (command line):
runc grader.c
orrunc grader.cpp
orrunc grader.pas
 Compile and run (gedit plugin): ControlR, 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 Kday 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 3day 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
orhottest.cpp
orhottest.pas
 Contestant interface:
hottest.h
orhottest.pas
 Grader interface: none
 Sample grader:
grader.c
orgrader.cpp
orgrader.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
orrunc grader.cpp
orrunc g rader.pas
 Compile and run (gedit plugin): ControlR, 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 <= N1, the ith 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 <= N1), such that the kth sensor has the minimum height,
 for all 0 <= i < k, h_{i} > h_{i+1}, and
 for all k <= i < N1, 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
orvalley.cpp
orvalley.pas
 Contestant interface:
valley.h
orvalley.pas
 Grader interface:
graderlib.h
orgraderlib.pas
 Sample grader:
grader.c
orgrader.cpp
orgrader.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 tofind
. Therefore, it is safe to assume that the heights change between different calls tofind
.
 Expected output for sample grader input:
grader.expect.1
,grader.expect.2
, ...  Compile and run (command line):
runc grader.c
orrunc grader.cpp
orrunc g rader.pas
 Compile and run (gedit plugin): ControlR, 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