TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

21.1% (12/57)

Description

History became legend. . .
Legend became myth. . .
And some things that should not have been forgotten. . .
were lost.

在中土太陽時代第二紀元,黑暗魔君阿拉法特打造了魔戒二十一戒送給了人類,而阿拉法特則在暗中也鑄造了一只至尊魔戒,準備控制整個中土世界,而謂為至尊乃因他內藏強大無比的特殊查克拉與王印之光的庇護。精靈世界發覺了異狀而向阿拉法特宣戰,頓時世界陷入了黑暗,戰火綿延不斷,燒了好幾世紀......。

這時候世界的主神----八掛太極之神(簡稱八神),決定參與這場戰爭,將世界恢復平衡,因此利用了結界忍術將阿拉法特以絕對零度冰封在一個黑箱裡......,而魔戒則流落人間......。

至於魔戒的下落...相信大家知道了。而阿拉法特呢?在另一個世界成為了一個外表看似普通,實際卻過於常人的冰箱。因為它的高效能,所以被當成極度高價的拍賣品在友克鑫市拍賣會中被拍賣。
但是因為內部的阿拉法特還有著意識,在冰箱中修練了上千萬年,已經獲得了可以預知未來的能力。
因為太久沒看到正妹,所以蠢蠢欲動的阿拉法特一但看到正妹就會開始蠢蠢欲動(產生一種叫做蠢蠢欲動之力的力),力量也會不斷的上升,一但力量超過冰封的咒印力,他就可以被解放出來,重新征服世界。
因此有著預知能力的他決定控制拍賣會,使得他能夠自己決定主人並早日被解放出來。

現在他已經鎖定了某個區域,因為那個區域住滿了正妹。
那個區域是一個m*n大小的棋盤狀住宅區,每一格中住了一個人,他以預知能力將整個區域的每戶都標上了一個實數,代表正妹度a[i]j。但是因為力量傳遞是衰減很快的,所以距離遠進也會影響他的蠢蠢欲動之力,這又牽扯到一個叫做蠢蠢欲動衰減率k的東西。

總而言之這個冰箱的蠢蠢欲動之力會 = sum( a[i][j] / k ^ (|x-i|+|y-j|) )for every(i,j) = (1,1) ~ (m,n)

其中(x,y)代表的是購買他的主人家的座標,而要讓他解放就必須要使這個蠢蠢欲動之力最大才行。
依他的聰明才智當然難不倒他了。所以很快的就找到了目標並且蠢蠢欲動。

現在身為八神後裔的你--八仙,你在過海察看的時候不小心發覺了這項陰謀,因此決定來消滅它。
但是麻煩的是,假如你攻擊他的力量大於蠢蠢欲動之力的話,將會殃及無辜;假如小於的話又無法阻止他。
所以一定要恰當剛好才行。因此你決定開始寫一個程式計算出需要以多少的力量來攻擊冰箱才可以使他陰謀不會得逞。

Input Format

每組測資只有一筆測資。
第一行有三數m,n,k(1<=m,n<=1000,k>1)。
接下來有一個m*n的表格。
第i+2行的第j個數則代表住在座標(i,j)的人的正妹度a[i][j]。
註:除了m,n之外,k與a[i][j]都是浮點數。

Output Format

輸出一數代表你需要破壞冰箱的力量(到小數後第三位)。

Sample Input

5 5 4
1.0 9.3 7.2 -90 8
-3.1 4.2 5.8 9.1 0.1
-7.4 -6.3 2.4 1.8 5.4
-7.1 -8.2 1.2 2.1 4.2
7.7 -6 26 38 24.5

Sample Output

51.114

Hints

Problem Source

原TIOJ1527 / INFOR 22nd幹部考(prob D)。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10