IOI '13 - Brisbane, Australia

Art Class

You have an Art History exam approaching, but you have been paying more attention to informatics at school than to your art classes! You will need to write a program to take the exam for you.

The exam will consist of several paintings. Each painting is an example of one of four distinctive styles, numbered 1, 2, 3 and 4. (Click the images below to view their full-sized versions.)

Style 1 contains neoplastic modern art. For example:

Style 2 contains impressionist landscapes. For example:

Style 3 contains expressionist action paintings. For example:

Style 4 contains colour field paintings. For example:

Your task is, given a digital image of a painting, to determine which style the painting belongs to.

The image will be given as an H×W (100 ≤ H, W ≤ 500) grid of pixels. The rows of the image are numbered 0, …, H-1 from top to bottom, and the columns are numbered 0, …, W-1 from left to right.

The pixels are described using a two-dimensional arrays of integers, the encoded RGB values of the image, which give the amount of red, green and blue respectively in each pixel of the image. Each individual pixel will be a 32-bit signed integer. However, when decoded into the three RGB values, these amounts range from 0 (no red, green or blue) to 255 (the maximum amount of red, green or blue).


Input Format

The first line of input will contain the integer T (0 ≤ T ≤ 150), the number of test cases to follow.

For each test case:

  • The first line will contain the two integers H and W, the height and width of the image.
  • The next H lines will each contain W integers. Each integer will describe a pixel using the default RGB color model (see below for conversion instructions).

Output Format

For every test case, output a line containing a single integer denoting the style of the image, which must be 1, 2, 3 or 4, as described above.


Sample Tests

Individual sample test cases for the above images can be found here for you to analyse (Right click > Save link as):


Interpreting Colors

The standard conversion scheme with RGB colors uses the formula: RGB = (R<<16)|(G<<8)|B, where R, G and B are values from 0 to 255 inclusive, << is the bitshift-left operator, and | is the bitwise-OR operator. To obtain the RGB values from an individual encoded integer pixel, use the following functions:

C/C++Pascal
int getR(int RGB) { return (RGB >> 16) & 0xFF; }

int getG(int RGB) { return (RGB >> 8) & 0xFF; }

int getB(int RGB) { return RGB & 0xFF; }
function getR(RGB: longint): integer;
begin getR := (RGB shr 16) and $FF; end;

function getG(RGB: longint): integer;
begin getG := (RGB shr 8) and $FF; end;

function getB(RGB: longint): integer;
begin getB := RGB and $FF; end;

Scoring

There are no subtasks. Instead, your score for this task will be based on how many images your program correctly classifies.

Suppose you correctly classify P percent of the images (so 0 ≤ P ≤ 100):

  • If P < 25 then you will score 0 points.
  • If 25 ≤ P < 50 then you will score between 0 and 10 points, on a linear scale. Specifically, your score will be 10 × (P - 25) / 25, rounded down to the nearest integer.
  • If 50 ≤ P < 90 then you will score between 10 and 100 points, on a linear scale. Specifically, your score will be 10 + (90 × (P - 50) / 40), rounded down to the nearest integer.
  • If 90 ≤ P then you will score 100 points.

All Submissions
Best Solutions


Point Value: 30 (partial)
Time Limit: 60.00s
Memory Limit: 64M
Added: Jul 15, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...