KöMaL - Középiskolai Matematikai és Fizikai Lapok
A lap

Rendelje meg a KöMaL-t!

VersenyVizsga portál


Matematika oktatási portál

I. 378. We are given a black-and-white image of \(\displaystyle N\times M\) pixels, described by 0s and 1s arranged in a grid. An image is considered to be nicer, if there are more adjacent pixels that are identical. In this exercise, two pixels are adjacent if they share a common edge. Your goal is to make the original image nicer by negating certain pixel values. Negating the value of a single pixel costs \(\displaystyle Q\) units of money. However, in the final image, every pair of adjacent pixels with different colors will result in an additional penalty of \(\displaystyle P\) units of money.

For some given images you should find the transformation such that the sum of the \(\displaystyle P\) and \(\displaystyle Q\) quantities is the smallest.

Without submitting a program, your task now is the convert the three input files in.1, in.2 and in.3 (downloadable from our web site) to out.1, out.2 and out.3. The first line of an input file contains 4 integers (\(\displaystyle N\), \(\displaystyle M\), \(\displaystyle P\) and \(\displaystyle Q\)), describing the number of rows and columns of the grid, and the cost and penalty parameters. The image itself is described in the following \(\displaystyle N\) lines, each containing \(\displaystyle M\) characters. The output should have a similar format with an \(\displaystyle N\times M\) grid of pixel values. You are not required to submit an optimal solution, but solutions will compete against one another: the solution with the smallest total \(\displaystyle P+Q\) value for the 3 images will obtain 10 points, and other, suboptimal solutions will get proportionally less points.

A sample input file is presented below, together with a possible (not necessarily optimal) transformation. The total cost \(\displaystyle P+Q\) here is \(\displaystyle 6\cdot 2+3\cdot 3 =21\) units of money.

The three output files should be submitted in a compressed file (i378.zip).

(10 points)

Deadline expired on 10 June 2015.

Statistics on problem I. 378.
6 students sent a solution.
10 points:Gercsó Márk.
9 points:Kovács 246 Benedek.
8 points:1 student.
7 points:1 student.
6 points:1 student.
5 points:1 student.

  • Problems in Information Technology of KöMaL, May 2015

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley