Alphabets
IOI 2011 | Practice task
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, 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
- Use the RunC programming and test environment. (See the contest environment information here)
- Implementation folder:
alpha/
(download prototype here)
-
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