UVAOJ127 | 哈喽哈咯

Written by razrlele 12:54 December 13, 2014

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

QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C 6S

8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C 5C

AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD KD

AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS KS

Sample Output

1 2	6 piles remaining: 40 8 1 1 1 1 1 pile remaining: 52

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

* File Name: uvaoj127.cpp

* Author: razrLeLe

* Mail: razrlele@outlook.com

* Homepage: https://yueyu.io

* Created Time: 2014年12月11日星期四 17时24分35秒

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#define LOCAL

const int maxn = 52;

int pilecount;

using namespace std;

#define INF 0x3f3f3f3f

struct pile

{

char cards[maxn+10][2];

int num;

}p[maxn+10];

void pop(const int k)

{

p[k].num--;

return ;

}

void cpycards(char* a, char* b)

{

a[0] = b[0];

a[1] = b[1];

return ;

}

void push(const int k, char* a)

{

cpycards(p[k].cards[++p[k].num], a);

return ;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

char tmp[2];

while(scanf("%s", tmp))

{

if(tmp[0] == '#') break;

cpycards(p[1].cards[1], tmp);

p[1].num = 1;

for(int i = 2; i <= maxn; i++)

{

scanf("%s", p[i].cards[1]);

p[i].num = 1;

}

pilecount = maxn;

bool moved = true;

while(moved)

{

int i;

moved = false;

for( i = 2; i <= pilecount; i++)

{

int pa = i-1, pb = i-3;

cpycards(tmp, p[i].cards[p[i].num]);

char tmpa[2];

cpycards(tmpa, p[pa].cards[p[pa].num]);

if(pb > 0)

{

char tmpb[2];

cpycards(tmpb, p[pb].cards[p[pb].num]);

if(tmp[1] == tmpb[1] || tmp[0] == tmpb[0])

{

moved = true;

pop(i);

push(pb, tmp);

break;

}

else if(tmp[1] == tmpa[1] || tmp[0] == tmpa[0])

{

moved = true;

pop(i);

push(pa, tmp);

break;

}

else if(tmp[1] == tmpa[1] || tmp[0] == tmpa[0])

{

moved = true;

pop(i);

push(pa, tmp);

break;

}

if(p[i].num == 0 && moved)

{

for(int j = i+1; j <= pilecount; j++)

{

swap(p[j-1], p[j]);

}

//debug

pilecount--;

/* for(int j = 0; j < pilecount; j++)

cout << " " << pile[j].top();

printf("\n");

}

printf("%d pile", pilecount);

if(pilecount > 1)

printf("s remaining:");

else

printf(" remaining:");

for(int i = 1; i <= pilecount; i++)

{

printf(" %d", p[i].num);

}

printf("\n");

}

return 0;

}

随机数据生成代码:

* File Name: data.cpp

* Author: razrLeLe

* Mail: razrlele@outlook.com

* Homepage: https://yueyu.io

* Created Time: 2014年12月11日星期四 14时52分55秒

#define LOCAL

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <iostream>

using namespace std;

int n = 100, m = 100000;

char rank[13] = {'A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K'};

char color[4] = {'C', 'D', 'H', 'S'};

using namespace std;

#define INF 0x3f3f3f3f

double randomnum()

{

return (double)rand()/ RAND_MAX; // [0, 1]

}

int randomnum(int m)

{

return (int)(randomnum() * (m-1) + 0.5); //[0, m-1]

}

int main()

{

#ifdef LOCAL

//freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/data.txt", "w", stdout);

#endif

srand(time(NULL)); //initiate randomnum seed

/*printf("%d %d\n", n, m);

for(int i = 0; i < m ; i++)

{

if(rand() % 2 == 0) printf("A"); else printf("B");

int X, Y;

for(;;)

{

X = randomnum(n) + 1;

Y = randomnum(n) + 1;

if(X != Y) break;

}

printf(" %d %d\n", X, Y);

}*/

int nums = 1000 ;

while(nums--)

{

for(int i = 0; i < 52; i++)

{

if(i) printf(" ");

printf("%c%c", rank[randomnum(13)], color[randomnum(4)]);

}

cout << endl;

}

cout << "#" << endl;

return 0;

}

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

* File Name: compare.java

* Author: razrLeLe

* Mail: razrlele@outlook.com

* Homepage: https://yueyu.io

* Created Time: 2014年12月12日星期五 20时37分50秒

import java.io.*;

import java.util.*;

public class compare{

public static void main(String[] args) throws Exception{

File outfile = new File("/home/razrlele/build/out.txt");

File correctfile = new File("/home/razrlele/build/outc.txt");

Scanner input0 = new Scanner(outfile);

Scanner input1 = new Scanner(correctfile);

int count = 1;

while(input0.hasNext() && input1.hasNext()){

String s1 = input0.nextLine();

String s2 = input1.nextLine();

if(!s1.equals(s2))

System.out.println(count+" is wrong\n" + "s1: " + s1 + "\ns2: " + s2);

count++;

}

input0.close();

input1.close();

}