IOI Photos have been posted

Posted first Newsletter

IOI Program

Schedule updated including information about new Evening Lectures.

Rules, competition environment and sample tasks added to site.

Registration activated and many ioi2010.org web updates.

# Day 1 Task 3: Quality of Living

Cities in Alberta tend to be laid out as rectangular grids of blocks. Blocks are labeled with coordinates 0 to**R**-1 from north to south and 0 to

**C**-1 from west to east.

The quality of living in each particular block has been ranked
by a distinct number, called *quality rank*,
between 1 and **R*****C**, where 1 is the best and **R*****C**
is the worst.

The city planning department wishes to identify a rectangular
set of blocks with dimensions **H** from north to south
and **W** from west to east, such that the median
quality rank among all blocks in the rectangle is
the best.
**H** and **W** are *odd* numbers not exceeding
**R** and **C** respectively.
The *median quality rank*
among an odd number of quality ranks is defined to be
the quality rank **m** in the set such that
the number of quality ranks better than **m** equals
the number of quality ranks worse than **m**.

You are to implement a procedure **rectangle(R,C,H,W,Q)**
where **R** and **C** represent the total size of the
city, **H** and **W** represent the dimensions of
the set of blocks, and **Q** is an
array such that **Q[a][b]** is the quality rank
for the block labeled **a** from north to south and
**b** from west to east.

Your implementation of **rectangle** must return a number:
the best (numerically smallest) possible median quality rank of
an **H** by **W** rectangle of blocks.

Each test run will only call **rectangle** once.

### Example 1

For this example, the best (numerically smallest) median quality rank of 9 is achieved by the middle-right rectangle ofR=5,C=5,H=3,W=3,Q= 5 11 12 16 25 17 182 7 104 2320 3 124 2119 146 22 8 13 159

**Q**shown in bold. That is,

rectangle(R,C,H,W,Q)=9

### Example 2

For this example the correct answer is 5.R=2,C=6,H=1,W=5,Q= 6 1 2 11 7 5 9 3 4 10 12 8

### Subtask 1 [20 points]

Assume R and C do not exceed 30.### Subtask 2 [20 points]

Assume R and C do not exceed 100.### Subtask 3 [20 points]

Assume R and C do not exceed 300.### Subtask 4 [20 points]

Assume R and C do not exceed 1 000.### Subtask 5 [20 points]

Assume R and C do not exceed 3 000.### Implementation Details

- Use the RunC programming and test environment
- Implementation folder:
`/home/ioi2010-contestant/quality/`(prototype: quality.zip) - To be implemented by contestant:
`quality.c`or`quality.cpp`or`quality.pas` - Contestant interface:
`quality.h`or`quality.pas` - Grader interface:
*none* - Sample grader:
`grader.c`or`grader.cpp`or`grader.pas` - Sample grader input:
`grader.in.1``grader.in.2`etc.*Note: The first line of input contains: R,C,H,W The following lines contain the elements of Q, in row-major order.* - Expected output for sample grader input:
`grader.expect.1``grader.expect.2`etc. - 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 file. - Submit (command line):
`submit grader.c`or`submit grader.cpp`or`submit grader.pas` - Submit (gedit plugin):
*Control-J*, while editing any implementation or grader file.