14463 - Take 6！

https://acm.cs.nthu.edu.tw/problem/14463/

“Take 6”（也稱為“6 Nimmt！”）是一種由 104 張牌組成的紙牌遊戲，每張牌都有一個數位（範圍從 1 到 104）和一定數量的牛頭符號。一張牌的牛頭數量各不相同，編號較高的牌通常包含更多的牛頭。玩家的目標是以最少的牛頭完成遊戲，因為每個牛頭都算作一個扣分。遊戲分輪進行。

遊戲中的每張牌都有一定數量的「牛頭」（罰分）。牛頭在卡片上的分佈如下：

• 1 張卡片，上面有 7 個牛頭——編號 55
• 8 張牌，上面有 5 個牛頭——11 的倍數（55 除外）：11、22、33、44、66、77、88、99
• 10 張帶有 3 個牛頭的牌 - 10 的倍數：10、20、30、40、50、60、70、80、90、100
• 9 張帶有 2 個牛頭的牌——5 的倍數不是 10 的倍數（55 除外）：5、15、25、35、45、65、75、85、95
• 76 張牌，1 個牛頭 - 其餘的牌，從 1 到 104

遊戲規則

• 每個玩家都發 M 張牌，遊戲由 M 輪組成。
• 遊戲從 P 行牌開始，每行以一張起手牌開始。
• 在每一輪中：
  • 所有玩家同時從他們的手牌中選擇一張牌來玩。
  • 一旦顯示，卡片將根據其值按升序排列，從最小的數字開始。
  • 每張牌必須放在高於該行中的最後一張牌但價值最接近的行中。
  • 如果一行已經包含五張牌，則放置第六張牌的玩家必須拿走該行中的所有五張牌作為懲罰。然後，他們的牌將成為該行中新的第一張牌。
    
    
  • 如果玩家的牌小於任何行中的最後一張牌，則玩家必須從最後一張牌最大的行中取出所有牌（作為懲罰），並將他們的牌作為該行的新第一張牌。
• 遊戲繼續進行，直到所有玩家都打完了所有的牌。

目標是避免收集牛頭，因為它們代表著扣分。遊戲結束時牛頭最少的玩家獲勝。

輸入

輸入以包含三個整數 N 、 M 和 P 的行開頭，這些整數表示玩家的數量、每個玩家持有的牌數以及桌子上的行數。

接下來的 P 行各包含一個整數 Di ，表示表上行中的起始卡。

以下 N 行各包含 M 個整數 Ci，1 ，Ci，2 ,...,Ci，M ，其中 Ci，j 代表玩家在一輪中打出的牌。每個玩家每輪將打出一張牌。

約束

• 2 ≤ N ≤ 10
• 1 ≤ M ≤ 50
• 1 ≤ N×M ≤ 100
  
• 1 ≤ P ≤ 4
  
• 1 ≤ Di , Ci,j ≤ N×M + P
  
• 對於所有三元組 （i， j， k） ， Di ≠ Cj，k

子任務

• 測試案例 1~2： P = 1
• 測試案例 3~4：M = 1
• 測試案例 5~6： N = 2
• 測試案例 7~10：沒有額外的限制。

輸出

輸出應由 N 行組成，其中每行包含一個整數，表示遊戲結束時玩家的牛頭總數。每個玩家的牛頭數反映了整個遊戲過程中產生的處罰。

示例說明

開始時，桌上有兩排牌，分別有11張和6張牌。

在第一輪中，四名玩家各打出一張牌：12、1、7 和 8。

玩家 2（綠色）先打出 1 號牌。由於牌桌上沒有小於 1 的牌，因此該玩家必須從倒數最大的行中取出所有牌。玩家拿走編號為 11 的牌，獲得 5 個牛頭。

接下來，將牌按順序放置：7 放在 6 之後，8 放在 7 之後，12 放在 8 之後。

在第二輪中，四名玩家各打出一張牌：5、13、2 和 14。

玩家 3（紫色）先打出 2 張牌，牌按順序放置：2 在 1 之後，5 在 2 之後，13 在 12 之後，14 在 13 之後。

由於玩家 4（灰色）的牌 （14） 是該行的第六張牌，作為懲罰，他們必須拿該行的前五張牌並賺取 5 個牛頭。

這兩個新行將成為下圖所示的行。

在第三輪中，四名玩家各打出一張牌：9、10、4 和 3。

玩家 4（灰色）首先打出 3 號牌，但由於桌上沒有小於 3 的牌，因此該玩家必須從倒數最大的那一行中拿走所有牌。

玩家拿起編號為 14 的牌，獲得 1 個牛頭。

接下來，將牌按順序放置：4 在 3 之後放置，9 在 5 之後放置，10 在 9 之後放置。

這題的目標是要模擬一個簡化版本的卡牌遊戲，並計算每位玩家的懲罰分數（cattle heads）。我們將每位玩家出牌的過程進行模擬，並根據規則將牌放入正確的排隊中，如果有玩家因為放入第六張卡而必須拿起整排牌，則他會累計相應的懲罰分數。

解題思路：

1.初始化每個排隊中的初始卡牌。

2.每一輪，所有玩家同時出一張牌，我們將這些卡按照從小到大的順序排列。

3.對每張牌進行處理：

• 找到適合放入的那一列，如果該列已有5張牌，則該玩家必須拿走這些牌並累計懲罰分數。
• 如果這張牌比所有列的最後一張牌還小，則該玩家必須選擇其中最後一張最大的那列並拿走，累計懲罰分數。

4.重複上述過程直到所有牌都打完。

5.計算並輸出每位玩家的懲罰分數。

解法步驟：

1.初始化一個紀錄每列卡牌的陣列。

2.用一個變數來追蹤每位玩家的懲罰分數。

3.每輪依照規則處理出牌並更新每列卡牌的狀態。

第一行：

4 3 2

三個整數：

• N = 4：有4位玩家。
• M = 3：每位玩家有3張牌。
• P = 2：有2列卡牌。

第二行和第三行：

11 

6

這兩行表示遊戲開始時的兩列牌，每一列的初始卡牌。

第一列以卡牌 11 開始。

第二列以卡牌 6 開始。

接下來的4行： 這些行代表每位玩家每一輪打出的牌，依次對應每位玩家的出牌順序：

12 5 9 → 第1位玩家 

1 13 10 → 第2位玩家 

7 2 4 → 第3位玩家 

8 14 3 → 第4位玩家

第1位玩家：12, 5, 9，這是第1位玩家的出牌順序。

第2位玩家：1, 13, 10，這是第2位玩家的出牌順序。

第3位玩家：7, 2, 4，這是第3位玩家的出牌順序。

第4位玩家：8, 14, 3，這是第4位玩家的出牌順序。

輸出結果說明

表示每位玩家在遊戲結束後的總懲罰分數（牛頭數量），分別是：

• 第1位玩家的懲罰分數是 0。
• 第2位玩家的懲罰分數是 5。
• 第3位玩家的懲罰分數是 0。
• 第4位玩家的懲罰分數是 6。

程式碼

#include <stdio.h>

//用來計算每張卡牌的懲罰牛頭數量。
int cattle_heads(int card) {
    if (card == 55) return 7;// 卡牌 55 有 7 個牛頭
    if (card % 11 == 0 && card != 55) return 5;// 每個 11 的倍數（除 55）有 5 個牛頭
    if (card % 10 == 0) return 3;// 每個 10 的倍數有 3 個牛頭
    if (card % 5 == 0) return 2;// 每個 5 的倍數（除 10 的倍數）有 2 個牛頭
    return 1;// 其他牌有 1 個牛頭
}

int main() {
    int N, M, P;
    scanf("%d %d %d", &N, &M, &P);// 輸入玩家數量 N、每位玩家手牌數 M、卡牌列數 P

    int rows[4][5] = {0};// 每列最多可以容納5張牌
    int row_size[4] = {0};// 記錄每列當前有幾張牌
    int player_points[10] = {0};// 記錄每位玩家的懲罰牛頭數

    // 讀取每列的初始卡牌
    for (int i = 0; i < P; i++) {
        int D;
        scanf("%d", &D); // 讀取初始卡牌
        rows[i][row_size[i]] = D;// 把初始卡牌放進相應的列
        row_size[i]++;              // 更新第 i 列的卡牌數量
    }

    // 讀取每位玩家的手牌
    int cards[10][50];// 玩家手牌，最多 10 位玩家，每位玩家最多 50 張牌
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%d", &cards[i][j]);// 讀取玩家手牌

    //模擬遊戲過程
    for (int round = 0; round < M; round++) {
        for (int i = 0; i < N; i++) {// 每一輪每位玩家各出一張牌
            int card = cards[i][round];// 當前玩家出的卡
            int best_row = -1;// 最適合放入的列
            int min_diff = 105;// 記錄牌與列尾牌的最小差值

            // 找出最適合的列，該列的最後一張牌比當前牌小且差值最小
            for (int r = 0; r < P; r++) {
                if (card > rows[r][row_size[r] - 1] && card - rows[r][row_size[r] - 1] < min_diff) {
                    best_row = r;
                    min_diff = card - rows[r][row_size[r] - 1];
                }
            }

            // 如果牌比所有列的最後一張牌都小，必須選擇最大的列，並拿走該列的所有牌
            if (best_row == -1) {
                int max_last = -1;
                for (int r = 0; r < P; r++) {
                    if (rows[r][row_size[r] - 1] > max_last) {
                        best_row = r;
                        max_last = rows[r][row_size[r] - 1];
                    }
                }
                // 拿走該列所有牌，並累計牛頭數量
                for (int r = 0; r < row_size[best_row]; r++)
                    player_points[i] += cattle_heads(rows[best_row][r]);
                row_size[best_row] = 0;// 清空該列
            } else if (row_size[best_row] == 5) {// 如果該列已有5張牌，必須拿走該列的所有牌
                for (int r = 0; r < 5; r++)
                    player_points[i] += cattle_heads(rows[best_row][r]);
                row_size[best_row] = 0;// 清空該列
            }
            // 將當前牌放入選定的列
            rows[best_row][row_size[best_row]] = card;   // 將玩家的卡牌放到最合適的列
            row_size[best_row]++;                        // 更新這列的卡牌數量
        }
    }

    // 輸出每位玩家的懲罰牛頭數
    for (int i = 0; i < N; i++)
        printf("%d\n", player_points[i]);

    return 0;
}

根據題目中的規則：

1. 卡牌 55 有 7 個牛頭：這是一個特例，題目明確指出卡牌號碼 55 有 7 個牛頭，因此我們首先處理這個特殊情況。
2. 每個 11 的倍數（除了 55）有 5 個牛頭：根據題目，所有是 11 的倍數的卡牌（除了 55）都有 5 個牛頭。比如 11、22、33、44、66、77、88、99。
3. 每個 10 的倍數有 3 個牛頭：每個是 10 的倍數的卡牌都有 3 個牛頭。比如 10、20、30、40、50、60、70、80、90、100。
4. 每個 5 的倍數（不包括 10 的倍數）有 2 個牛頭：每個是 5 的倍數但不是 10 的倍數的卡牌都有 2 個牛頭。比如 5、15、25、35、45、65、75、85、95（這裡特別排除了 10 的倍數，因為它們已有 3 個牛頭）。
5. 其他卡牌有 1 個牛頭：其餘不是上述倍數的卡牌都只有 1 個牛頭。

將規則轉換為程式：

1. 先處理特殊情況：卡牌 55 是一個特殊情況，因此我們在函數的第一個條件處理這個。
2. 處理 11 的倍數：接著我們檢查是否是 11 的倍數，並排除卡牌 55。
3. 處理 10 的倍數：這個檢查很簡單，檢查是否是 10 的倍數。
4. 處理 5 的倍數（排除 10 的倍數）：因為 5 的倍數不包括 10 的倍數，所以我們檢查是否是 5 的倍數並確保它不是 10 的倍數。
5. 最後處理其他卡牌：最後，對於不符合上述條件的卡牌，我們直接返回 1，因為它們只有 1 個牛頭。