Problem 127 "Accordian" Patience，風琴手撲克牌遊戲

這題的ACM題目是個撲克牌遊戲，看起來有點複雜，本來想用人工方式，按照他所說的規則玩一下。後來想到，愈複雜的規則，如果電腦跑對了，就一定是對的。人跑對了，還不見得是對的，因為人眼睛有時會看不清楚。
題目是你攤開一列 52 張撲克牌，從左邊開始看，任何一張牌和它的左邊(或左邊第三張)的花色(或數字)相同，就拿起來，放在左邊(或左邊第三張)那張牌的上面。每次都只看最上面那張，每放完一張牌，要把空位(如果有空位)補起來，並從頭來過。
如果有多張牌可以拿起，每次優先拿起最左邊的那張。如果可以放在左邊，也可以放在左邊第三張，則選擇放在左邊第三張上面。記住，每放一張，都要從頭來過。
本解題的虛擬碼如下：

step 1: do
step 2:    look through the 2~52 cards
step 3:       compare i card with (i-3) card
step 4:       if the two cards match color or rank
step 5:          move i card to the top of (i-3) card
step 6:          if i is empty, move the rest cards to its left side
step 7:          go back to step 2
step 8: until no more moving cards.

這題很適合運用C語言的結構，程式碼如下

typedef struct
{
    int num;
    char card[52][3];
} CardPile;
CardPile p[52];

一堆牌有 52 個位置(p[52])，每個位置可以放 52 張牌(p[i][0]為第i個位置的第一張)，同時有個計數器(p[i].num第i個位置的牌數)。
比較i 與 i-3 位置的牌，如下列程式碼，如果條件符合，將 i 疊的牌放到 i-3 那疊上面，清除 i 疊的值，同時更新兩疊的數量，如果第 i 疊數量是零，則要移動所有後面的牌。最後的 break 是用來進行從頭開始檢視的動作。

if (i>2 && (p[i].card[p[i].num-1][0]==p[i-3].card[p[i-3].num-1][0] ||
     p[i].card[p[i].num-1][1]==p[i-3].card[p[i-3].num-1][1]))
   strcpy(p[i-3].card[p[i-3].num], p[i].card[p[i].num-1]);
   strcpy(p[i].card[p[i].num-1], "");
   p[i].num--;
   p[i-3].num++;
   if (p[i].num==0)
   {
      for (j=i;j<51;j++)
      {
        p[j].num = p[j+1].num;
        for (k=0;k<p[j+1].num;k++)
        {
            strcpy(p[j].card[k], p[j+1].card[k]);
            strcpy(p[j+1].card[k], "");
        }
        p[j+1].num = 0;
      }
   }
   break;
}

簡單地修改上述的程式碼可以用來比較 i 與 i-1 兩疊牌的內容。
最後別忘了，一疊牌以上是用複數 piles 來顯示。
p127題目連結
回ACM題庫目錄
回首頁

Problem 105 The Skyline Problem，天際線問題

這個題目我之前使用邏輯方式企圖解算，可是總有些問題無法解決。記得有找到一個建議，使用height[10000]來紀錄每一個點的高度，今天總算有點時間，解解看，果然很方便。
以下的C語言程式碼是在讀入每個建築資訊後，用來修訂每一個點的建築高度，其中l, h, r 是讀取的輸入值。

for (i=l;i<r;i++)
    if (height[i] < h)
        height[i] = h;

讀完後，直接從高度current = 0開始，只要高度有變化，就列印出座標點與高度，很容易就做完了。程式碼如下：

if (height[i] != current)
{
   current = height[i]; 
   /* print a space if not the first output */
   printf("%d %d", i, current);
}

要注意有 presentation error問題，因為輸出不可以隨便加空白。
p105題目連結
回ACM題庫目錄
回首頁

Problem 10469 To Carry or not to Carry，進位或不進位

題目中所顯示的加法器，因為有錯誤，所以無法產生進位的動作。題目有兩個例子，一個是0100與0110的相加，結果為0010。另一個6+9=15的例子，是0110+1001=1111，所以綜合起來，這個加法器其實是個 XOR 的計算器。所以程式的輸出只要顯示 a^b 兩個數字 XOR 的結果，只不過題目提醒是要用 32 位元的 unsigned，因此宣告與讀取時，要使用 unsigned。
整個程式核心內容只有三行，不是開玩笑，真的就三行。C語言程式碼如下：

unsigned a, b;
while (scanf("%u%u", &a, &b)==2)
    printf("%u\n", a ^ b);

p10469題目連結
回ACM題庫目錄
回首頁