# 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. 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:

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.

• 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.

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

• 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`
• `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 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.

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.

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

• 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`
• 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 Ti'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 hi (0 <= hi <= 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, hi > hi+1, and
• for all k <= i < N-1, hi < hi+1.

However, because the sensor installation team forgot to measure the sensors' heights, the value of k, and all the heights hi'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.

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 hi. 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:

sensorheight
010
17
29
315

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

callsreturns
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.

callsreturns
find(4,10)1
find(4,2)0
find(4,9)1
find(4,15)1
find(4,100)0

• N <= 35.

• N <= 1 000; and k = 0.

• N <= 200.

• 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, hi'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