961 . 陰陽棋

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

ytp ytp-senior ytp-2025

Description

在遙遠的嵌合蟻王國，一種全新的棋盤遊戲被發明。棋盤上，並非普通的黑白子，而是「陰陽棋」！這場對決的主角，正是蟻王梅路艾姆，他將執黑子（先手）；而與他對弈的，是人類的棋士奇才——小麥，她將執白子（後手）。一場攸關人類存亡的對決正在展開。

陰陽棋的棋盤是一個精巧的 4×4 方格。每次輪到一方下棋時，棋手可以選擇一個空著的位置放置自己顏色的棋子。然而，這盤棋的規則異常詭譎：當一個棋子被放置後，它會立即引發奇異的波動，將其上下左右的相鄰棋子顏色進行反轉（黑變白，白變黑）。這就像是棋子本身具有了生命，能夠影響周遭的一切。

雙方的目標都非常明確：最大化自己顏色棋子的數量。當棋盤上的所有格子都被填滿後，如果黑色棋子的數量多於白色棋子，則蟻王（先手）獲勝；反之，若白色棋子的數量大於或等於黑色棋子，則小麥（後手）獲勝。

現在，你作為棋局的見證者，被給定一個合法且尚未結束的陰陽棋盤。請你判斷，在這盤局勢下，若雙方都採取最佳策略，目標是最大化自己顏色的棋子數量，蟻王（先手）是否能通過精妙的計算和操作，最終戰勝小麥，抑或是小麥將憑藉她的直覺和棋藝，取得勝利。

Input Format

輸入包含四行，每行包含四個整數，代表 4×4 棋盤的初始狀態。 棋盤上的數字定義如下：

  • 0 代表該位置為空。
  • 1 代表該位置為黑子。
  • 2 代表該位置為白子。

資料範圍：

  • 輸入的棋盤保證為一個 4×4 的合法盤面（給定的盤面不一定是按照最佳策略來進行的，但一定是合法的）。
  • 棋盤上至少有一個空位。
  • 輪到誰下棋（黑子或白子），取決於棋盤上已有的棋子數量。若總棋子數量為2的倍數，則輪到黑子，反之亦然。

Output Format

第一行輸出贏家的名字：如果先手勝輸出 "Meruem"（不含雙引號）反之輸出 "Komugi"（不含雙引號）。

第二行輸出兩個整數，分別依序表示最終黑色棋子的數量和白色棋子的數量。

Sample Input 1

1 0 0 2
0 0 0 0
0 0 0 1
0 0 0 0

Sample Output 1

Komugi
6 10

Sample Input 2

1 1 2 0
2 1 1 1
2 0 1 2
1 2 1 1

Sample Output 2

Meruem
10 6

Hints

  • 遊戲保證在棋盤所有格子都被填滿後結束。
  • 雙方都會採取最佳策略，目標是最大化自己顏色的棋子數量。
  • 如果最終黑色棋子數量等於白色棋子數量，則小麥（後手）獲勝。
  • 最後一個子任務可能需要套用到許多優化技巧才能通過，建議有充足時間再來挑戰。

Problem Source

YTP 2025 高中組程式挑戰營 p11

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 2~22 盤面上 0 的數量 $\le 6$ 3
3 2~43 盤面上 0 的數量 $\le 12$ 10
4 0~60 無額外限制 2

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 4
1 3000 524288 65536 1 4
2 3000 524288 65536 2 3 4
3 3000 524288 65536 2 3 4
4 3000 524288 65536 2 3 4
5 3000 524288 65536 2 3 4
6 3000 524288 65536 2 3 4
7 3000 524288 65536 2 3 4
8 3000 524288 65536 2 3 4
9 3000 524288 65536 2 3 4
10 3000 524288 65536 2 3 4
11 3000 524288 65536 2 3 4
12 3000 524288 65536 2 3 4
13 3000 524288 65536 2 3 4
14 3000 524288 65536 2 3 4
15 3000 524288 65536 2 3 4
16 3000 524288 65536 2 3 4
17 3000 524288 65536 2 3 4
18 3000 524288 65536 2 3 4
19 3000 524288 65536 2 3 4
20 3000 524288 65536 2 3 4
21 3000 524288 65536 2 3 4
22 3000 524288 65536 2 3 4
23 3000 524288 65536 3 4
24 3000 524288 65536 3 4
25 3000 524288 65536 3 4
26 3000 524288 65536 3 4
27 3000 524288 65536 3 4
28 3000 524288 65536 3 4
29 3000 524288 65536 3 4
30 3000 524288 65536 3 4
31 3000 524288 65536 3 4
32 3000 524288 65536 3 4
33 3000 524288 65536 3 4
34 3000 524288 65536 3 4
35 3000 524288 65536 3 4
36 3000 524288 65536 3 4
37 3000 524288 65536 3 4
38 3000 524288 65536 3 4
39 3000 524288 65536 3 4
40 3000 524288 65536 3 4
41 3000 524288 65536 3 4
42 3000 524288 65536 3 4
43 3000 524288 65536 3 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4
51 3000 524288 65536 4
52 3000 524288 65536 4
53 3000 524288 65536 4
54 3000 524288 65536 4
55 3000 524288 65536 4
56 3000 524288 65536 4
57 3000 524288 65536 4
58 3000 524288 65536 4
59 3000 524288 65536 4
60 3000 524288 65536 4
Submit
Back to Top