2016年2月25日 星期四

[HOJ 283][Codeforces #180]Grid coloring (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 283 - Grid coloring

Special Judge

Problem Statistics
Solved Member: 5  Submission: 29  User Tried: 6
Problem:
瀚瀚有一個長方形的格子,一共 n 列 m 行,任意兩個相鄰的格子(有共用邊)之間有一個符號,等於或者不等於,如下圖所示。



瀚瀚希望在每個格子中填入 1 到 k 共 k種數字,若兩相鄰格子的符號是等於,並且填的數字相同,他就會得 1 分,或者,兩相鄰格子符號為不等於,且填入數字不同也會得 1 分。他希望他得的分數至少要有滿分的  34 倍以上。



如上圖,每種顏色代表一種不同的數字,用打勾來表示有得分的位置,打叉代表沒得分。瀚瀚一共得了 13 分,最大的分數為 17 分。因此  1317≥34 ,滿足要求。
Input:
測試資料的第一行有 3 個整數,n,m,k ,代表矩形的列數、行數、以及瀚瀚可以填的數字有幾種。

接下來共有 2n-1 行,每一行依序有 m-1,m,m-1,m, ...,m-1 個字元。字串中有 N,E 兩種字母, N 代表不等於,E 代表等於。

輸入由上到下的順序為圖中符號的排列方法(請見範測及上面的圖)。

限制:
n,m ≤ 1000
k ≤ n*m

20% 的測試資料滿足: n,m ≤ 4
50% 的測試資料滿足: n,m ≤ 100
Output:
若沒有辦法得到  34  以上的分數,請輸出一行 "NO" 即可。
否則,請在第一行輸出 "YES"。
並輸出 n 列,每一列有 m 個在 1 和 k 之間的數字,代表每一格所填入的數字。

若有多種方法可以得到滿分的  34  倍以上的分數,請任意輸出一組解即可。
Sample Input:
3 4 4
ENE
NNEE
NEE
ENEN
ENN
Sample Output:
YES
1 1 2 2
3 4 1 1
3 3 2 4
HINT:
題目敘述中的圖恰好對應到範例輸入以及範例輸出的情況。
Source:
Codeforces #180
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
01000ms65536kb
1-11000ms65536kb10
1-21000ms65536kb
1-31000ms65536kb
2-11000ms65536kb10
2-21000ms65536kb
2-31000ms65536kb
3-11000ms65536kb10
3-21000ms65536kb
3-31000ms65536kb
4-11000ms65536kb10
4-21000ms65536kb
4-31000ms65536kb
5-11000ms65536kb10
5-21000ms65536kb
5-31000ms65536kb
6-11000ms65536kb10
6-21000ms65536kb
6-31000ms65536kb
7-11000ms65536kb10
7-21000ms65536kb
7-31000ms65536kb
8-11000ms65536kb10
8-21000ms65536kb
8-31000ms65536kb
9-11000ms65536kb10
9-21000ms65536kb
9-31000ms65536kb
10-11000ms65536kb10
10-21000ms65536kb
10-31000ms65536kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原