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:

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

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

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