【2015】斗地主

题目描述

牛牛最近迷上了斗地主扑克游戏，该游戏使用黑桃、红心、梅花、方片的A到K加上大小王共54张牌进行。牌的大小关系为：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，花色不影响牌的大小。 每局游戏的手牌由n张牌组成，玩家每次可按规定牌型出牌，先打光手牌的一方获胜。现在给定T组手牌，请你计算每组手牌最少需要多少次出牌可以全部打光。 本题的出牌牌型规则如下： | 牌型 | 牌型说明 | |--------|--------------------------------------------------------------------------| | 火箭 | 即双王（大小王同时出） | | 炸弹 | 四张数码相同的牌，例如四个A | | 单张牌 | 单独一张牌，例如单张3 | | 对子牌 | 两张数码相同的牌 | | 三张牌 | 三张数码相同的牌 | | 三带一 | 三张数码相同的牌 + 一张单牌，例如三张3 + 单张4 | | 三带二 | 三张数码相同的牌 + 一对牌，例如三张3 + 对4 | | 单顺子 | 五张或更多数码连续的单牌（不能包含2点和双王），例如7、8、9、10、J | | 双顺子 | 三对或更多数码连续的对牌（不能包含2点和双王），例如对3、对4、对5 | | 三顺子 | 二个或更多数码连续的三张牌（不能包含2点和双王），例如三张3、三张4、三张5 | | 四带二 | 四张数码相同的牌 + 任意两张单牌（或任意两对牌），例如四张5+单3+单8 或 四张4+对5+对7 | 注：所有顺子类牌型（单顺子、双顺子、三顺子）不要求牌的花色相同。

输入描述

第一行包含两个空格分隔的正整数T和n，分别表示手牌的组数和每组手牌的张数。 接下来T组数据，每组数据共n行，每行两个非负整数a_i和b_i，表示一张牌：

• a_i表示牌的数码：1代表A，11代表J，12代表Q，13代表K，0代表王（其中0 1为小王，0 2为大王）；
• b_i表示牌的花色：1~4分别对应黑桃、红心、梅花、方片，花色对牌的大小和牌型无影响。

  输出描述

  共输出T行，每行一个整数，表示打光第i组手牌的最少次数。

  输入样例1

  1 8
  7 4
  8 4
  9 1
  10 4
  11 1
  5 1
  1 4
  1 1

  输出样例1

  3

  样例1解释

  该组共有8张牌：方片7、方片8、黑桃9、方片10、黑桃J、黑桃5、方片A、黑桃A。 最优出牌方案：

1. 单顺子：7、8、9、10、J
2. 单张：5
3. 对子：A 共3次即可打光所有牌。

   输入样例2

   1 17
   12 3
   4 3
   2 3
   5 4
   10 2
   3 3
   12 2
   0 1
   1 3
   10 1
   6 2
   12 1
   11 3
   5 2
   12 4
   2 2
   7 2

   输出样例2

   6

   数据规模与约定

   对于不同测试点，手牌组数T与张数n的规模如下： | 测试点编号 | T | n | 测试点编号 | T | n | |------------|-----|-----|------------|-----|-----| | 1 | 100 | 2 | 11 | 100 | 14 | | 2 | 100 | 2 | 12 | 100 | 15 | | 3 | 100 | 3 | 13 | 10 | 16 | | 4 | 100 | 3 | 14 | 10 | 17 | | 5 | 100 | 4 | 15 | 10 | 18 | | 6 | 100 | 4 | 16 | 10 | 19 | | 7 | 100 | 10 | 17 | 10 | 20 | | 8 | 100 | 11 | 18 | 10 | 21 | | 9 | 100 | 12 | 19 | 10 | 22 | | 10 | 100 | 13 | 20 | 10 | 23 | 数据保证：所有手牌均为随机生成。