# 淘汰遊戲
:::success

有11 個人圍成一個圓圈，如下圖表示。從箭頭所指為開始，每隔一人，就淘汰一人，從1號開始編號，編號1開始不淘汰，（例如3號離開，5號離開…，依此類推，若超過編號11號就接回到1號繼續淘汰下去），請問最後剩下來的那個人，是編號幾號？
:::

## 輸入說明
每次輸入兩個數字
$n$與$p$,$n$表示每次參加淘汰遊戲的人數，$p$表示間隔多少人淘汰一人，輸入$n$小於100，且$p$<$n$。

## 輸出說明
輸出一個數字，表示最後剩下一人的編號。

## 輸入範例
11 3

## 輸出範例
10

## 解題構思
1. 使用陣列進行模擬，宣告一個101個元素的陣列，陣列第一個元素不使用，也就是陣列索引值為0的元素不使用。
2. 先設定陣列中所有元素為0，若被淘汰改成1。
3. 一個變數紀錄淘汰幾個了，當剩最後一個時，就使用迴圈找出陣列值為0 的索引值，就是答案。

### 參考程式

#include <iostream>
#include <cstring>   //for memset()
#define     MAX     100+5  //設定最大人數
using namespace std;
int a[MAX];   // Array to store users

int main()
{
    int n;  //總人數
    int p;  //間隔數
    // 不斷讀取輸入的 n, p 直到輸入結束後停止
    while(cin>>n>>p)
    {
        //將陣列的初始值全部設為0
        //0:未淘汰    1:被淘汰
        memset(a, 0, sizeof(a));
        //模擬淘汰過程
        int outs=0;  //紀錄累計淘汰的人數
        int steps;   //從目前位置往前累計的次數
        int curPos=2; //記錄下一個要被淘汰的位置
        while(outs<(n-1))
        {
            steps = 0;
            while(steps<p)
            {
                if(!a[curPos])
                {
                    //累計間隔人數 + 1
                    steps++;
                    //如果目前位置的索引還未到最大值(n)
                    //目前位置的索引 + 1
                    if(curPos<n)
                        curPos++;
                    //設成從第1個位置索引
                    else curPos=1;
                }

                else
                {
                    //如果目前位置的索引還未到最大值(n)
                    //目前位置的索引 + 1
                    if(curPos<n)
                        curPos++;
                    //設成從第1個位置索引
                    else curPos=1;
                }
            }
            //由 curPos往後找到下一個未被淘汰的位置
            while(a[curPos])
            {
                //如果目前位置的索引還未到最大值(n)
                //目前位置的索引 + 1
                if(curPos<n)
                    curPos++;
                //設成從第1個位置索引
                else curPos=1;
            }
            //curPos的位置被淘汰
            a[curPos] = 1;
            //累計淘汰人數
            outs++;

        }
        //輸出結果
            for(int i=1; i<=n; i++)
            {
                if(!a[i])
                {
                    cout<<i<<"\n";
                    break;
                }
            }
    }
    return 0;
}


# 服務顧客（模擬時間的進行）

## 題目說明
1. 便利商店店員服務顧客，請幫他計算沒有顧客的時間。
2. 已知顧客到達時間與服務所需時間，假設店員服務時不用休息，當顧客到時店員若在服務其他客人，則顧客會依序排隊等待服務，若超過該店員服務時間則由下一位店員服務。
3. 時間以分鐘為單位，同時間到的客人可以任意順序進行排隊，請計算店員在指定上班時間，沒有顧客的總時間，以分鐘為單位。

## 輸入說明
1. 每次輸入兩個數字$t$與$n$，$t$表示店員要上班幾小時，$n$表示有幾個客人需要服務。
2. 接著後面有$n$行，每行兩個數字$a$與$b$。
3. $a$表示顧客到達時間，所輸入的$a$為採用將小時與分鐘累加為累計分鐘數呈現，累計分鐘數從0開始，第一個小時為0到59，第二個小時為60到119,例如:80，表示第2小時的第20分鐘結束時，第2小時的第21分鐘剛開始時到便利商店。
4. $b$表示顧客服務所需時間，以分鐘為單位。
5. 所輸入資料會以顧客到達時間進行排序，$n$小於200人，$t$小於10小時。

## 輸出說明

輸出一個數字，表示店員沒有顧客的總時間，以分鐘為單位。

## 輸入範例

4 5
1 3
45 20
160 3
161 80
170 10

## 輸出範例

137

## 解題構思

1. 使用陣列進行模擬，宣告一個600個元素的陣列 $ser$ 先設定為0，若需要服務客人改成1。
2. 一個變數 $now$ 紀錄服務目前客人完成的時間，不斷經由客人到達時間與服務時間，更新陣列 $services$ 與變數$now$。
3. 最後統計服務時間內的陣列 $ser$ 的值等於0的個數。

### 參考程式

#include <iostream>

#include <cstring>       // for memset()
#define     MAXN    200  // MAX. of the customers
#define     MAXT    600  // MAX. of the working time
using namespace std;

int arroveTime[MAXN];        //紀錄MAXN個顧客到達時間
int serviceTime[MAXN];       //紀錄MAXN個顧客所需服務時間
int services[MAXT];          //記錄所有上班時間每分鐘的狀態


int main()
{
    int t;                  //儲存輸入的工作時間
    int n;                  //儲存有幾個客人需要服務
    while(cin>>t>>n){
        //n個客戶到達時間與所需服務時間存入陣列
        for(int i=0; i<n; i++){
            cin>>arroveTime[i]>>serviceTime[i];
        }
        //將記錄所有上班時間每分鐘的狀態的陣列全設為0
        memset(services, 0, sizeof(services));

        //模擬動作
        int totals = t*60;  //總工作時間分鐘
        int now = -1;       //每次開始服務時間(累加)
        for(int i=0; i<n; i++){
            //判斷是否在上班時間
            if(now>=totals)
                break;
            //不須排隊
            if(now<=arroveTime[i]){
                //將第i個人到達時間至服務時間的間隔設為1
                for(int j=arroveTime[i]; j<arroveTime[i]+serviceTime[i]; j++){
                    services[j]=1;
                }
                now = arroveTime[i]+serviceTime[i];
            }else{ //需要排隊
                //目前可以服務時間至服務時間的間隔設為1
                for(int j=now; j<=now+arroveTime[i]; j++){
                    services[j]=1;
                }
                now = now+serviceTime[i];
            }
        }
        //輸出結果
        int ans=0;
        for(int i=0; i<totals; i++){
            if(!services[i])
                ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}


# 神奇的蝸牛

## 題目說明

1. 蝸牛天天往上爬，想爬到樹頂。
2. 題目只給你樹的高度，蝸牛白天往上爬，晚上休息就會往下掉，且隨著天數增加往下掉的距離會不斷增加，且往下掉增加的距離都是第一天晚上往下掉的距離的10%。
3. 例如：第一天往下掉1公尺，第二天往下掉1.1公尺，第三天往下掉1.2公尺依此類推。
4. 問第幾天爬到樹頂，或者會掉到地面，所有輸入的單位都以公尺為單位，而且都是整數。

## 輸入說明

每次輸入三個數字$h$、$d$與$n$，$h$表示樹的高度，$d$表示蝸牛白天爬幾公尺，$n$表示蝸牛第一天晚上往下掉幾公尺。

## 輸出說明

輸出一個數字，表示第幾天爬到樹頂，若是第一天就爬到樹頂，就輸出「第1天爬到樹頂」，或者第二天掉到地面，就輸出「第2天掉到地面」

## 輸入範例

100 5 1

## 輸出範例

第$84$天掉到地面

### 參考程式

#include <iostream>

using namespace std;

int main(){
    int h,d;
    double n;

    while(cin>>h>>d>>n){
        int day=0;    // 天數
        double curHei=0;    // 目前高度
        double down=double(n);
        double n01=n*0.1;   // n的10%

        cout<<"down="<<down;

        while(1){
            day++;
            curHei+=d;

            if(curHei>=h||curHei<=0) break;
            curHei-=down;
            down+=n01;
        }
        if(curHei>=h)   cout<<"第"<<day<<"天爬到樹頂\n";
        if(curHei<=0)   cout<<"第"<<day<<"天掉到地面\n";
    }
}

# 撲克牌比大小（模擬撲克牌遊戲進行）

## 題目說明
1. 兩位玩家各拿5張牌，比較兩位玩家手中的五張撲克牌的大小來決定勝負。
2. 個別牌的數字大小順序分別為$A$、$K$、$Q$、$J$、$T$、$9$、$8$、$7$、$6$、$5$、$4$、$3$、$2$。
3. 花色大小順序分別為為黑梅©、紅磚(D)、紅心(H)與黑桃(S)。
4. 所輸入資料一定可以區分兩位玩家的勝負，可以不考慮平手情形，牌由小到大如下表，編號越大牌越大，大者獲勝。
5. 這個範例很複雜，需要耐心依據題意解題。


## 輸入說明

1. 輸入十張牌前面五張牌表示第一位玩家的牌，後面五張牌表示第二位玩家的牌
2. 輸入的牌由兩個字元的花色與數字組合起來，例如$S$$A$表示黑桃$A$、$D$$T$表示紅磚$10$，$C$$J$
表示黑莓$J$，$H$$K$表示紅心$K$，依此類推。

## 輸出說明

若第一位玩家較第二位玩家較大，就輸出「第一位玩家獲勝」，若第二位玩家較第一位玩家較大，就輸出「第二位玩家獲勝」。

## 輸入範例

CJ CK CT C2 C4 D2 S2 H2 DJ DT

## 輸出範例

第一位玩家獲勝

## 解題構思

1. 將撲克牌黑莓2到黑莓A轉換成數字0到12；
紅磚2到紅磚A轉換成數字0到12；
紅心2到紅心A轉換成數字0到12；
黑桃2到黑桃A轉換成數字0到12。
2. 利用將第一位與第二位玩家的撲克牌傳成數字後分別儲存到陣列fp（第一位）與陣列sp（第二位），由小到大排序fp 與sp，並統計兩位玩家五張牌中，不考慮花色只考慮數字，五張牌的數字出現個數到陣列f（第一位）與陣列s（第二位）。
3. 第一位玩家撲克牌的大小等級可以利用陣列fp 與f 進行判斷，第二位玩家撲克牌的大小等級可以利用陣列sp 與s 進行判斷。若兩位玩家的撲克牌大小等級相同，則需另外判斷最高位的牌區分出哪一方獲勝。

### 參考程式

#include <iostream>

#include <string>    //for string 物件
#include <sstream>   //for stringstream 物件
#include <cstring>   //for memset()
#include <algorithm> //for algorithm
#define     CARDS   13   //每種花色有13張牌
#define     SIZE    5    //每個人的牌數
using namespace std;

int user1[CARDS];    //紀錄2.3...A在5張牌中出現的次數
int user2[CARDS];    //紀錄2.3...A在5張牌中出現的次數
int src1[5];         //紀錄原來5張牌的編號
int src2[5];         //紀錄原來5張牌的編號

/*
將 poker 依據花色與點數編碼成 0~51的數字
1.梅花 1~12
2.方塊 13~25
3.紅心 26~38
4.黑桃 39~51
*/
int getCardNO(string s)
{
    int suit, num;    //紀錄花色, 點數
    switch(s[0]){  // 花色
    case 'C':       //1~12
        suit=0; break;
    case 'D':       //3~25
        suit=1; break;
    case 'H':       //26~38
        suit=2; break;
    case 'S':       //39~51
        suit=3; break;
    }
    switch(s[1]){  //點數
    case 'A':
        num=12; break;
    case 'K':
        num=11; break;
    case 'Q':
        num=10; break;
    case 'J':
        num=9; break;
    case 'T':
        num=8; break;
    default:
        num=s[1]-'2'; break;
    }
    // 回傳轉換後的編碼
    return (suit*CARDS+num);
}
void showArray(int *poker, int size)
{
    for(int i=0; i<size; i++){
        cout<<poker[i]<<" ";
    }
    cout<<"\n";
}
//判斷是否為Straight Flush同花順
bool isStraightFlush(int* src, int* points)
{
    //Assume: 1 2 3 4 5
    //最大點數 - 最小點數 = 4
    if(src[4]-src[0]==4){
        // 判斷5張牌的花色是否相同
        //5張牌是梅花
        if(src[0]>=CARDS*0 && src[4]<CARDS*1) return true; //  0~12 為 梅花
        //5張牌是方塊
        if(src[0]>=CARDS*1 && src[4]<CARDS*2) return true; // 13~25 為 方塊
        //5張牌是紅心
        if(src[0]>=CARDS*2 && src[4]<CARDS*3) return true; // 26~38 為 紅心
        //5張牌是黑桃
        if(src[0]>=CARDS*3 && src[4]<CARDS*4) return true; // 39~51 為 黑桃
    }
    return false;
}
// 判斷 src 是否為Flush(同花)
// src 已經由小到大排序
bool isFlush(int* src,int* points)
{
    // 所有牌必須同一種花色
    if(src[0]>=CARDS*0 && src[4]<CARDS*1) return true;  //  0~12 為 club
    if(src[0]>=CARDS*1 && src[4]<CARDS*2) return true;  // 13~25 為 diamond
    if(src[0]>=CARDS*2 && src[4]<CARDS*3) return true;  // 26~38 為 heart
    if(src[0]>=CARDS*3 && src[4]<CARDS*4) return true;  // 39~51 為 Spade
    return false;
}
//判斷5張牌是否為Straight順子
//points:5張牌點數出現的次數
bool isStraight(int* src,int* points)
{
    // 5 6 7 8 9: 各出現1次
    for(int i=0; i<CARDS; i++){
        if(points[i]==1 &&
           points[i+1]==1 &&
           points[i+2]==1 &&
           points[i+3]==1 &&
           points[i+4]==1)
            return true;
    }
    return false;
}
//判斷5張牌是否為isFourOfKind(鐵支)
//points:5張牌點數有一次出現4次
bool isFourOfKind(int* src,int* points)
{
    // 0~12有一個數字出現4次
    for(int i=0; i<CARDS; i++){
        if(points[i]==4) return true;
    }
    return false;
}

// 判斷5張牌是否為 Full house(葫蘆)
bool isFullHouse(int* src,int* points)
{
    for(int i=0; i<CARDS; i++){
        // 出現 1對
        if(points[i]==2){
            // 出現 3條: i+1開始到12有一個點數出現 3次
            for(int j=i+1; j<CARDS; j++){
                if(points[j]==3) return true;
            }
        }
        // 出現 3條
        if(points[i]==3){
            // 出現 1對: i+1開始到12有一個點數出現 2次
            for(int j=i+1; j<CARDS; j++){
                if(points[j]==2) return true;
            }
        }
    }
    return false;
}

// 判斷5張牌是否為Three of a Kind(三條)
//points:5張牌點數有一次出現3次
bool isThreeOfKind(int* src,int* points)
{
    // 0~12有一個數字出現3次
    for(int i=0; i<CARDS; i++){
        if(points[i]==3) return true;
    }
    return false;
}

// 判斷5張牌是否為Two Pairs(兩對)
//points:5張牌點數有兩個數字出現2次
bool isTwoPairs(int* src,int* points)
{
    // 0~12有一個數字出現2次
    for(int i=0; i<CARDS; i++){
        if(points[i]==2){
            // 出現 1對: i+1開始到12有一個點數出現 2次
            for(int j=i+1; j<CARDS; j++){
                if (points[j]==2) return true;
            }
        }
    }
    return false;
}

// 判斷5張牌是否為One Pair(一對 )
//points:5張牌點數有一個數字出現2次
bool isOnePair(int* src,int* points)
{
    // 0~12有一個數字出現2次
    for(int i=0; i<CARDS; i++){
        if(points[i]==2) return true;
    }
    return false;
}
//由 src 與 points 陣列來得知5張牌的等級
int getLeve1(int* src, int* points)
{
    if(isStraightFlush(src,points)) return 9;  // 同花順
    else if(isFourOfKind(src,points)) return 8;   // 鐵支
    else if(isFullHouse(src,points)) return 7;    // 葫蘆
    else if(isFlush(src,points)) return 6;     // 同花
    else if(isStraight(src,points)) return 5;  // 順子
    else if(isThreeOfKind(src,points)) return 4;  // 三條
    else if(isTwoPairs(src,points)) return 3;     // 兩對
    else if(isOnePair(src,points)) return 2;      // 一對
    else return 1;                         // 散牌
}
int checkLevel(int leve)
{
    return 1;
}

int main()
{
    string s;         //讀取一行資料儲存的字串
    while(getline(cin, s)){
        //s為一行資料,資料間以空白隔開
        //以s初始化stringstream物件(ss)
        stringstream ss(s);
        //將 user1, user2 紀錄2.3...A在5張牌中出現的次數的陣列全部設為0
        memset(user1, 0, sizeof(user1));
        memset(user2, 0, sizeof(user2));

        //把輸入資料的前面5筆存入src1, user1
        //          把後面5筆存入src2, user2
        string tmp;
        int cardNo;
        for(int i=0; i<10; i++){
            //從ss串流讀取一個字串
            ss>>tmp;
            //將tmp編碼成0~51的數字
            cardNo = getCardNO(tmp);
            //前面5筆存入src1, user1
            if(i<5){
                src1[i]=cardNo;
                user1[cardNo%CARDS]++;
            }else{
                //後面5筆存入src2,user2
                src2[i%SIZE]=cardNo;
                user2[cardNo%CARDS]++;
            }
        }
        //由小到大將2個人的牌點數由小到大排序
        sort(src1, src1+SIZE);
        sort(src2, src2+SIZE);
        //showArray(src1, SIZE);
        //showArray(src2, SIZE);

        //取得5張牌的等級
        int level1 = getLeve1(src1, user1);
        int level2 = getLeve1(src2, user2);
        if(level1>level2) cout<<"第一位玩家獲勝\n";
        else if(level1<level2) cout<<"第二位玩家獲勝\n";
        else{
            int check = checkLevel(level1);
            (check==1) ? (cout<<"第一位玩家獲勝\n") : (cout<<"第二位玩家獲勝\n");
        }
    }


    return 0;
}