IOI '13 - Brisbane, Australia
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).
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).
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.
Individual sample test cases for the above images can be found here for you to analyse (Right click > Save link as):
- Style 1 — style-1-0.in, style-1-1.in, style-1-2.in, style-1-3.in
- Style 2 — style-2-0.in, style-2-1.in, style-2-2.in, style-2-3.in
- Style 3 — style-3-0.in, style-3-1.in, style-3-2.in, style-3-3.in
- Style 4 — style-4-0.in, style-4-1.in, style-4-2.in, style-4-3.in
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:
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.
Point Value: 30 (partial)
Time Limit: 60.00s
Memory Limit: 64M
Added: Jul 15, 2013
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
As an example, the first colour in style-4-0.in represents the colour with the hex code #AB8C53, and the first colour in style-4-1.in represents the colour with the hex code #2A4361.