UVAOJ127

Written by    12:54 December 13, 2014 

UVAOJ127

127 – “Accordian” Patience

Time limit: 3.000 seconds

 Accordian” Patience 

You are to simulate the playing of games of Accordian” patience, the rules for which are as follows:

Deal cards one by one in a row from left to right, not overlapping. Whenever the card matches its immediate neighbour on the left, or matches the third card to the left, it may be moved onto that card. Cards match if they are of the same suit or same rank. After making a move, look to see if it has made additional moves possible. Only the top card of each pile may be moved at any given time. Gaps between piles should be closed up as soon as they appear by moving all piles on the right of the gap one position to the left. Deal out the whole pack, combining cards towards the left whenever possible. The game is won if the pack is reduced to a single pile.

Situations can arise where more than one play is possible. Where two cards may be moved, you should adopt the strategy of always moving the leftmost card possible. Where a card may be moved either one position to the left or three positions to the left, move it three positions.

Input

Input data to the program specifies the order in which cards are dealt from the pack. The input contains pairs of lines, each line containing 26 cards separated by single space characters. The final line of the input file contains a # as its first character. Cards are represented as a two character code. The first character is the face-value (A=Ace, 2-9, T=10, J=Jack, Q=Queen, K=King) and the second character is the suit (C=Clubs, D=Diamonds, H=Hearts, S=Spades).

Output

One line of output must be produced for each pair of lines (that between them describe a pack of 52 cards) in the input. Each line of output shows the number of cards in each of the piles remaining after playing Accordian patience” with the pack of cards as described by the corresponding pairs of input lines.

Sample Input

Sample Output

模拟题做起恶心, 读起来更恶心.

这个题目的关键之一就是首先要读懂规则:

  • 给你五十二张牌, 每张牌作为一堆, 一共五十二堆, 每张牌由两个字母代替, 第一个字母是牌的大小, 第二个是牌的花色.
  • 牌与牌之间如果花色或者大小相同的话即匹配成功.
  • 每一张牌一旦发现与左边第一张或者左边第三张牌的匹配的话即可将这张牌移到匹配的牌上面去.
  • 如果同时发现左边第一张和左边第三张相同的话优先移动到左边第三张.
  • 如果发现所有的牌堆中有多个牌可以移动的话优先移动最左边的.
  • 如果一个牌堆所有的牌都移出去的话其右边的所有牌堆应该立即左移一个单位填补空缺.
  • 直至没有一张牌可以移动为止.

大概的方法就是从左往右开始遍历, 然后一旦发现可移动的牌就移动一次, 然后如果产生了空堆就立马把空堆右边的牌堆左移填补空缺, 再又重新从左往右遍历, 直至没有一张牌可以移动为止.

一开始用STL的stack做TLE了, 后来只能自己模拟堆栈, 其间还碰到了一些奇怪的东西, 最后还因为输出空字符的问题卡了几次WA.

话说还是第一次尝试自己随机模拟测试数据, 然后和udebug的输出来对比, 对比的话输出比较多用的也是自己写的小程序读取字符串对比, 基本上随机个一千个数据没问题就可以AC了.

随机数据生成代码:

输出结果对比代码(因为是在本地机器上面跑所以没有比较计较运行时间和占用内存, 然后也比较好写, 所以用的是Java)

Category : acmstudy

Tags :