TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Description

「團體賽時你在做什麼呢?」

眾所皆知,程式解題競賽集訓營(IOICAMP)的團體賽會場會有很多好吃的點心,殿壬是一位很會畫畫且喜歡吃點心且喜歡看動漫的可愛大學生,一直很希望能夠吃到 IOICAMP 的點心,而電仁為了獲得殿壬的歡心,便努力地練習程式,經過日以繼夜的苦練,終於順利取得了進入 IOICAMP 的資格,並於今天參加了 IOICAMP 的團體賽。

俗話說得好,「眾人皆醉我獨醒,舉世皆濁我獨清」。此時 IOICAMP 團體賽正在進行中,所有選手都在奮力寫 code、思考題目的同時,有一名少男也在思考,雖然同樣是思考,不過他腦海裡浮現的內容卻與其他參賽者所浮現的有些不一樣。

「有沒有空?」

殿壬想畫畫,雖然殿壬對程式設計一竅不通,但他仍然想用自己所擅長的方式 — 畫畫,來為電仁加油打氣。

現在他手邊有一張神奇的圖畫紙,由長、寬分別為 $W$ 和 $H$ 單位長度所構成的矩形方格圖。(為了方便大家理解,殿壬定義「為平行 x 軸方向、為平行 y 軸方向」 )

圖畫紙的每個格子都有一個數值,殿壬想「從左至右」在這圖畫紙中畫出 NPSC 這四個字,並且要求滿足一件事情 —「任意兩字不能連起來」(即假設四個字的最左邊及最右邊的 $x$ 座標分別為$L_N$, $R_N$, $L_P$, $R_P$, $L_S$, $R_S$, $L_C$, $R_C$,那麼必須有 $R_N + 1 < L_P$、$R_P + 1 < L_S$、$R_S + 1 < L_C$)

以下為在 $W = 17, H = 7$ 的神奇圖畫紙上繪製 N、P、S、C 四字的一種方式:

這幅寫著 NPSC 四個大字的繪畫看似普通,但其實擁有著顛覆眾人認知的力量,殿壬在圖畫紙上所畫的 N、P、S、C 四字覆蓋之格子數值總和越大,電仁將會獲得越多的加持,甚至還有機會獲得夢幻的電神之力壓倒性地電全場呢!現在殿壬想知道他所畫的 NPSC 四字所覆蓋的格子數值總和最大可以是多少呢?

「可以來畫畫嗎?」

如果天真地以為畫在圖畫紙上的 N、P、S、C四字可以隨便亂畫的話,那麼就大錯特錯啦!

對於 N、P、S、C 這四個字,在神奇圖畫紙上繪畫有些嚴格的定義,如果沒有按照定義好好的畫,電仁不但獲得不了神秘力量的加持,反而會獲得負面效果!

為了避免這種悲慘的事情發生,殿壬早已有所準備。他在團體賽前就已經整理好了一本 codeboook,裡面收錄著各國字符在神奇圖畫紙上的嚴格繪畫定義。殿壬帶著這本 codeboook (paint boook?)參加團體賽,很快地就在這本 codeboook 中找到了 N、P、S、C 四個字畫在神奇圖畫紙上的圖形定義,內容如下:

1 . N的定義:
N 由至少三個矩形所組成(矩形四邊皆平行於座標軸),
假設由 $K$ 個矩形組成(編號 $1$ 到 $K$),第 $i$ 個矩形的左下角方格座標為 $(L_i, B_i)$,右上角方格座標為 $(R_i, T_i)$,要求滿足:

  • $L_i \le R_i$、$B_i \le T_i$
  • 對於任意 $1 < i \le K$,有 $L_i = R_{i-1} + 1$
  • 對於任意 $3 \le i < K$,有 $B_{i-1} - 1 \le T_i \le T_{i-1}$、$B_i \le B_{i-1}$
  • $B_2 > B_1$、$T_2 = T_1$、$B_{K-1} = B_K$、$T_{K-1} < T_K$

2 . P 的定義:
P 由兩個部分組成,第一個部分為一個平行於座標軸的矩形 X 構成,第二個部分為一個平行於座標軸的大矩形 Y 挖去一個平行於座標軸的小矩形 Z 構成,設三個矩形的左下角方格座標方別為 $(L_X, B_X)$、$(L_Y, B_Y)$、$(L_Z, B_Z)$,右上角方格座標分別為 $(R_X, T_X)$、$(R_Y, T_Y)$、$(R_Z, T_Z)$,要求滿足:

  • $L_X \le R_X$、$B_X + 3 \le T_X$
  • $L_Y = R_X + 1$、$B_Y > B_X$、$T_Y = T_X$
  • $L_Y + 1 \le R_Y$、$B_Y + 2 \le T_Y$
  • $L_Z = L_Y$、$B_Z = B_Y + 1$、$R_Z = R_Y - 1$、$T_Z = T_Y - 1$

3 . S 的定義:
S 由一個大矩形 X,挖去兩個小矩形 Y、Z 得到,這三個矩形的邊都平行於座標軸。設大矩形 X 左下角方格座標為 $(L, B)$、長為 $U$($U \ge 2$)寬為 $V$($V \ge 5$ 且 $V$ 為奇數),則小矩形 Y 滿足左下角方格座標為 $(L, B + 1)$、長為 $U - 1$、寬為 $\frac{V - 1}{2} - 1$,小矩形 Z 滿足左下角方格座標為 $(L + 1, B + \frac{V + 1}{2})$、長為 $U - 1$、寬為 $\frac{V - 1}{2} - 1$。

4 . C 的定義:
C 由一個大矩形 X,挖去一個小矩形 Y 得到,這兩個矩形的邊都平行於座標軸。設大矩形 X 的左下角方格座標為 $(L, B)$,長為 $U$($U \ge 2$)、寬為 $V$($V \ge 3$),則小矩形 Y 滿足左下角方格座標為 $(L + 1, B + 1)$,長為 $U - 1$、寬為 $V - 2$。

現在,定義的部分殿壬都已經明白了,那麼讓我們開始畫畫吧! Let's draw!

Input Format

測試資料第一行包含兩個正整數 $W, H$,代表這張神奇圖畫紙是長為 $W$、寬為 $H$ 的矩形方格圖。

接下來有 $H$ 行,每行有 $W$ 個整數,輸入資料中的第 $j + 1$ 行的第 $i$ 個整數為格子座標 $(i, j)$ 的數值 $A_{i, j}$ $(1 \le j \le H, 1 \le i \le W)$

  • $1 \le W \le 200$
  • $1 \le H \le 1000$
  • $-200 \le A_{i,j} \le 200$

Output Format

輸出共一行。
若殿壬無論如何都無法在這張圖畫紙上畫出 N、P、S、C 四個字,則輸出 "Sad"。如果殿壬可以在這張圖畫紙上畫出 N、P、S、C 四個字,假設他所能畫出的 N、P、S、C 四字所覆蓋的格子數值總和最大為 $x$,若 $x$ 為正整數,輸出 "Happy x" ,反之則輸出 "Normal x"。輸出皆不含引號。

Sample Input

Sample Input 1:
16 5
42 4 22 81 197 25 20 41 194 93 61 134 123 131 97 192
127 110 47 169 21 70 16 179 132 1 120 15 178 83 123 96
179 193 164 154 85 195 116 117 169 88 105 55 61 174 77 152
48 178 153 7 173 109 65 118 116 64 65 10 53 97 136 117
199 94 116 55 168 41 7 66 13 101 113 21 172 96 149 108

Sample Input 2:
16 5
-32 -146 -88 -109 -102 -157 -87 -86 -149 -5 -81 -30 -43 -1 -190 -89
-190 -35 -85 -192 -191 -133 -180 -184 -70 -164 -187 -121 -50 -81 -194 -114
-72 -101 -109 -108 -38 -37 -180 -196 -160 -63 -32 -172 -146 -116 -83 -4
-143 -103 -72 -21 -114 -44 -3 -63 -83 -28 -57 -60 -5 -16 -99 -60
-189 -28 -95 -178 -69 -110 -80 -86 -42 -39 -111 -149 -187 -66 -162 -46

Sample Input 3:
7 5
13 3 100 -75 144 40 4
47 -66 132 147 18 0 140
-16 -17 56 192 181 198 -15
18 157 -126 -109 -98 74 -161
-7 118 -197 161 118 -95 147

Sample Input 4:
17 7
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 10 10 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 10 10 -1 10 10 -1 -1 -1 10 10 -1 -1 -1
10 10 -1 -1 10 10 -1 10 10 10 10 -1 -1 10 -1 10 10
10 10 10 10 10 10 -1 10 10 -1 10 -1 10 10 -1 10 -1
10 10 10 10 -1 10 -1 10 10 10 10 -1 10 -1 -1 10 -1
-1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 10 10 -1 10 10

Sample Output

Sample Output 1:
Happy 5759

Sample Output 2:
Normal -2080

Sample Output 3:
Sad

Sample Output 4:
Happy 470

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 15000 262144 262144
1 15000 262144 262144
2 15000 262144 262144
3 15000 262144 262144
4 15000 262144 262144
5 15000 262144 262144
6 15000 262144 262144
7 15000 262144 262144
8 15000 262144 262144
9 15000 262144 262144
10 15000 262144 262144
11 15000 262144 262144
12 15000 262144 262144
13 15000 262144 262144
14 15000 262144 262144
15 15000 262144 262144
16 15000 262144 262144
17 15000 262144 262144
18 15000 262144 262144
19 15000 262144 262144
20 15000 262144 262144
21 15000 262144 262144
22 15000 262144 262144
23 15000 262144 262144
24 15000 262144 262144
25 15000 262144 262144
26 15000 262144 262144
27 15000 262144 262144
28 15000 262144 262144
29 15000 262144 262144
30 15000 262144 262144
31 15000 262144 262144
32 15000 262144 262144
33 15000 262144 262144
34 15000 262144 262144
35 15000 262144 262144
36 15000 262144 262144
37 15000 262144 262144
38 15000 262144 262144
39 15000 262144 262144
40 15000 262144 262144
41 15000 262144 262144
42 15000 262144 262144