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
Description

         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:

         h(v)=Round((cdf(v)-cdfmin)/(M*N-cdfmin)*(L-1)).

         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 site:wikipedia.org” with google.com.

         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.

Input

 

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].

Output

 

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
255
Sample Output
Case 1:
0 85
170 255
Case 2:
255
Hint

 

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

Any question please mail to dy0013@163.com.

Source
idy0013@gmail.com