HUST Monthly 2011.06.26 (Personal Contest)

From: 2011-06-26 14:30:00 To: 2011-06-26 17:30:00 Now: 2017-09-22 06:54:54 Status: Public

A - Tobor's world

Time Limit: 1s Memory Limit: 128MB

Submissions: 446 Solved: 60

         Scientist Y.D.I has created a robot, called Y.G.Tobor. It’s first version has only one ability, which is Looking The World.

         Y.D.I has considered some situation while designing Tobor, and he give Tobor a gift, with which Tobor can filter image he saw. The method of filter is Histogram Equalization. This method usually increases the global contrast of many images, and it can be expressed as follow.

         a. Consider a discrete grayscale image, every pixel has a gray level value, and let Ni be the number of occurrences of gray level i.

         b. Let us also define the Cumulative Distribution Function of gray level v corresponding to Ni as

         cdf(v) = Sum{ Ni }, where  0 <= i <=v.

         c. We can transform an old gray level value to a new one with the following expression:


         where v is the old gray level value, and h(v) is the new one, L is 256 in this problem, and cdfmin is the minimum greater than zero value of {cdf}, cdf(v) has be calculated in part b. As an example, you can search “Histogram Equalization” with

         Now you are asked to solve the question:

         Give you a gray-scale image with N rows and M columns, every element of this image is integer, you need to tell the filtered image.

         Note: if the image has only one kind of color, then put what you get. See Sample.



Multiple case, you need process to the EOF. First line of each case is N and M, 0 < N,M <= 256.

There is M integers in every next N lines, which is split by single space, and the value is in the range of [0, 255].



Print case number in the first line, and N lines follow. Each line contains M integers, which indicates the new value of gray scale. No blank lines between cases. See Sample Output.

Sample Input
2 2
1 2
3 4
1 1
Sample Output
Case 1:
0 85
170 255
Case 2:


For more information, please download the problems in zip or pdf.

Any question please mail to