uva 758 - The Same Game

The Same Game

The game named ``Same'' is a single-person game played on a 10  15 board. Each square contains a ball colored red (R), green (G), or blue (B). Two balls belong to the same cluster if they have the same color, and one can be reached from another by following balls of the same color in the four directions up, down, left, and right. At each step of the game, the player chooses a ball whose cluster has at least two balls and removes all balls in the cluster from the board. Then, the board is ``compressed'' in two steps:

1.

Shift the remaining balls in each column down to fill the empty spaces. The order of the balls in each column is preserved.

2.

If a column becomes empty, shift the remaining columns to the left as far as possible. The order of the columns is preserved.

For example, choosing the ball at the bottom left corner in the sub-board below causes:

The objective of the game is to remove every ball from the board, and the game is over when every ball is removed or when every cluster has only one ball. The scoring of each game is as follows. The player starts with a score of 0. When a cluster of m balls is removed, the player's score increases by (m - 2)². A bonus of 1000 is given if every ball is removed at the end of the game.


You suspect that a good strategy might be to choose the ball that gives the largest possible cluster at each step, and you want to test this strategy by writing a program to simulate games played using this strategy. If there are two or more balls to choose from, the program should choose the leftmost ball giving the largest cluster. If there is still a tie, it should choose the bottommost ball of these leftmost balls.

Input 

You will be given a number of games in the input. The first line of input contains a positive integer giving the number of games to follow. The initial arrangement of the balls of each game is given one row at a time, from top to bottom. Each row contains 15 characters, each of which is one of ``R'', ``G'', or ``B'', specifying the colors of the balls in the row from left to right. A blank line precedes each game.

Output 

For each game, print the game number, followed by a new line, followed by information about each move, followed by the final score. Each move should be printed in the format:

Move x at (r,c): removed b balls of color C, got s points.


where x is the move number, r and c are the row number and column number of the chosen ball, respectively. The rows are numbered from 1 to 10 from the bottom, and columns are numbered from 1 to 15 from the left. b is the number of balls in the cluster removed. C is one of ``R'', ``G'', or ``B'', indicating the color of the balls removed. s is the score for this move. The score does not include the 1000 point bonus if all the balls are removed after the move.


The final score should be reported as follows:


Final score: s, with b balls remaining.


Insert a blank line between the output of each game. Use the plural forms ``balls'' and ``points'' even if the corresponding value is 1.

Sample Input 

3

RGGBBGGRBRRGGBG
RBGRBGRBGRBGRBG
RRRRGBBBRGGRBBB
GGRGBGGBRRGGGBG
GBGGRRRRRBGGRRR
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRGGGGRRRRR
GGGGGGGGGGGGGGG

RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
RRRRRRRRRRRRRRR
RRRRRRRRRRRRRRR
GGGGGGGGGGGGGGG
GGGGGGGGGGGGGGG

RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG
BGRBGRBGRBGRBGR
GRBGRBGRBGRBGRB
RBGRBGRBGRBGRBG

Sample Output 

Game 1:

Move 1 at (4,1): removed 32 balls of color B, got 900 points.
Move 2 at (2,1): removed 39 balls of color R, got 1369 points.
Move 3 at (1,1): removed 37 balls of color G, got 1225 points.
Move 4 at (3,4): removed 11 balls of color B, got 81 points.
Move 5 at (1,1): removed 8 balls of color R, got 36 points.
Move 6 at (2,1): removed 6 balls of color G, got 16 points.
Move 7 at (1,6): removed 6 balls of color B, got 16 points.
Move 8 at (1,2): removed 5 balls of color R, got 9 points.
Move 9 at (1,2): removed 5 balls of color G, got 9 points.
Final score: 3661, with 1 balls remaining.

Game 2:

Move 1 at (1,1): removed 30 balls of color G, got 784 points.
Move 2 at (1,1): removed 30 balls of color R, got 784 points.
Move 3 at (1,1): removed 30 balls of color B, got 784 points.
Move 4 at (1,1): removed 30 balls of color G, got 784 points.
Move 5 at (1,1): removed 30 balls of color R, got 784 points.
Final score: 4920, with 0 balls remaining.

Game 3:

Final score: 0, with 150 balls remaining.

---

Miguel A. Revilla
2000-02-09

simulation

#include<stdio.h>
#include<cstring>
#include<string>
#include<iostream>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N=15,M=10,LEFT,cases=1,total,score,move;
bool erase[15][10],erase2[15][10];
char dir[4][2];
vector<string>vc;
void init(){
    dir[0][0]=1,dir[1][0]=-1,dir[2][1]=1,dir[3][1]=-1;
}
bool isValid(int r,int c){return r>=0&&r<vc.size()&&c>=0&&c<vc[r].size();}
void flood(int r,int c,char tar){
    int a,b;
    if(erase[r][c])return;
    if(DBG)printf("(flood) %d,%d %c\n",r,c,vc[r][c]);
    total++;
    erase[r][c]=erase2[r][c]=1;
    rep(i,4){
        a=r+dir[i][0],b=c+dir[i][1];
        if(isValid(a,b)&&vc[a][b]==tar)
            flood(a,b,tar);
    }
}
void del(bool erase[][10]){
    int b,c,i,rsize=vc.size();
    rep(k,rsize){
        i=rsize-1-k;
        c=vc[i].size();
        rep(j,c)
            if(erase[i][c-1-j]){
                //if(DBG)printf("erase %d %d\n",i,c-1-j);
                vc[i].erase(vc[i].begin()+c-1-j);
                if(!vc[i].size())vc.erase(vc.begin()+i);;
            }
    }
}
void print(){
    int c;
    rep(i,M){
        c=M-i;
        rep(j,vc.size()){
            if(j>0)printf(" ");else printf("    ");
            if(vc[j].size()>=c)printf("%c",vc[j][c-1]);
            else printf(" ");
        }
        printf("\n");
    }
}
bool go(){
    bool er[15][10];
    memset(erase,0,sizeof(erase));
    total=0;
    int m=0,mr,mc;
    rep(i,15)rep(j,10){
        if(vc.size()>i&&vc[i].size()>j
            &&!erase[i][j]){
            memset(erase2,0,sizeof(erase2));
            if(DBG){printf("flood %d,%d %c\n",i,j,vc[i][j]);}
            total=0;
            flood(i,j,vc[i][j]);
            if(DBG)printf("rt\n");
            if(DBG)printf("totol %d\n",total);
            if(total>1&&m<total)memcpy(er,erase2,sizeof(er)),m=total,mr=i,mc=j;
        }
    }
    if(m>1){
        int sc=(m-2)*(m-2);
        printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",
            move++,mc+1,mr+1,m,vc[mr][mc],sc);
        del(er);
        LEFT-=m,score+=sc;
        if(DBG)printf("LFET %d\n",LEFT);
        if(DBG)print();
    }
    return m;
}
int main(){
    int n;
    bool ll=0;
    char chs[20];
    init();
    cin>>n;
    rep(i,n){
        LEFT=10*15,score=0;
        move=1;
        string s(10,'0');
        vc.assign(15,s);
        rep(i,10){
            scanf("%s",chs);
            rep(j,strlen(chs))vc[j][10-1-i]=chs[j];
        }
        if(ll)printf("\n");ll=1;
        printf("Game %d:\n\n",cases++);
        while(LEFT&&go());
        if(LEFT==0)score+=1000;
        printf("Final score: %d, with %d balls remaining.\n",score,LEFT);
    }
}

uva 556 - Amazing

Amazing

One of the apparently intelligent tricks that enthousiastic psychologists persuade mice to perform is solving a maze. There is still some controversy as to the exact strategies employed by the mice when engaged in such a task, but it has been claimed that the animal keepers eavesdropping on conversations between the mice have heard them say things like "I have finally got Dr. Schmidt trained. Everytime I get through the maze he gives me food".


Thus when autonomous robots were first being built, it was decided that solving such mazes would be a good test of the 'intelligence' built into such machines by their designers. However, to their chagrin, the first contest was won by a robot that placed a sensor on the right-hand wall of the maze and sped through the maze maintaining contact with the right-hand wall at all times. This led to a change in the design of mazes, and also to the interest in the behaviour of such robots. To test this behaviour the mazes were modified to become closed boxes with internal walls. The robot was placed in the south west corner and set of pointing east. The robot then moved through the maze, keeping a wall on its right at all times. If it can not proceed, it will turn left until it can proceed. All turns are exact right angles. The robot stops when it returns to the starting square. The mazes were always set up so that the robot could move to at least one other square before returning. The researchers then determined how many squares were not visited and how many were visited one, twice, thrice and four times. A square is visited if a robot moves into and out of it. Thus for the following maze, the values (in order) are: 2, 3, 5, 1, 0.

Write a program to simulate the behaviour of such a robot and collect the desired values.

Input 

Input will consist of a series of maze descriptions. Each maze description will start with a line containing the size of the maze (b and w), This will be followed by b lines, each consisting of w characters, either '0' or '1'. Ones represent closed squares, zeroes represent open squares. Since the maze is enclosed, the outer wall is not specified. The file will be terminated by a line containing two zeroes.

Output 

Output will consist of a series of lines, one for each maze. Each line will consist of 5 integer values representing the desired values, each value right justified in a field of width 3.

Sample Input 

3 5
01010
01010
00000
0 0

Sample Output 

  2  3  5  1  0

---

Miguel A. Revilla
1998-03-10

simulation

#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<iostream>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,M,D;
int dir[4][2],ndir[4],rside[4][2];
char **vc;
void init(){
    dir[0][0]=1,dir[1][1]=1,dir[2][0]=-1,dir[3][1]=-1;
    rside[0][1]=-1,rside[1][0]=1,rside[2][1]=1,rside[3][0]=-1;
    rep(i,4)ndir[i]=(i+1)%4;
}
bool isValid(int a,int b){return a>=0&&a<N&&b>=0&&b<M;}
void next(int &r,int &c){
    //if(DBG)printf("r c %d %d\n",r,c);
    int x=r+dir[D][0],y=c+dir[D][1];
    //if(DBG)printf("x y %d %d\n",x,y);
    if(isValid(x,y))
        if(vc[x][y]=='0'){
            r=x,c=y;
            if(isValid(r+rside[D][0],c+rside[D][1])&&
                vc[r+rside[D][0]][c+rside[D][1]]=='0'){
                D=(D-1)>=0?D-1:3;      //maintain against the wall
            }
        }
        else D=ndir[D],next(r,c);  //block
    else D=ndir[D],next(r,c);      //outside
}
void ans(){
    D=1;
    int steps[N][M];
    int cnt[5];
    memset(steps,0,sizeof(steps));
    memset(cnt,0,sizeof(cnt));
    int sr=N-1,sc=0,cr=N-1,cc=0;
    steps[cr][cc]=1;
    while(1){
        if(DBG)printf("cur %d %d\n",cr,cc);
        next(cr,cc);
        if(cr==N-1&&cc==0)break;else steps[cr][cc]++;
    }
    rep(i,N)rep(j,M)if(steps[i][j]<5&&vc[i][j]=='0')cnt[steps[i][j]]++;
    rep(i,5)printf("%3d",cnt[i]);
    printf("\n");
}
int main(){
    int a;
    init();
    while(scanf("%d%d",&N,&M)==2){
        if(N==0&&M==0)break;
        vc=(char **)malloc(N*sizeof(char *));
        rep(i,N)vc[i]=(char *)malloc(M+1);
        rep(i,N)scanf("%s",vc[i]);
        ans();
    }
}

uva 305 - Joseph

Joseph

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among npeople, numbered 1, 2, ..., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30

simulation, linked list

#include<stdio.h>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 1
using namespace std;

int K;
int dp[14],next[28];
void ans(){
    int left,m,i,tmp,pn,np,pre;
    bool fail;
    i=2*K,m=K;
    //if(DBG)printf("N %d\n",i);
    while(1){
        fail=0,m++,left=i;
        rep(j,i-1)next[j]=j+1;
        next[i-1]=0;
        //if(DBG)printf("%d: ",m);
        np=0;
        while(left>K){
            pn=m%left;
            if(pn==0)pn=left;
            int j=np;
            for(tmp=1;tmp++<pn;)pre=j,j=next[j];
            //if(DBG)printf(" %d",j);
            next[pre]=next[j];
            if(j<K){fail=1;break;}
            left--;
            np=next[j];
        }
        if(!fail){dp[K]=m;break;}
    }
}
void init(){
    REP(i,1,14)K=i,ans();
}
int main(){
    init();
    while(scanf("%d",&K)==1){
        if(K==0)break;
        printf("%d\n",dp[K]);
    }
}

uva 162 - Beggar My Neighbour

Beggar My Neighbour

``Beggar My Neighbour'' (sometimes known as ``Strip Jack Naked'') is a traditional card game, designed to help teach beginners something about cards and their values. A standard deck is shuffled and dealt face down to the two players, the first card to the non-dealer, the second to the dealer, and so on until each player has 26 cards. The dealer receives the last card. The non-dealer starts the game by playing the top card of her deck (the second last card dealt) face up on the table. The dealer then covers it by playing her top card face up. Play continues in this fashion until a ``face'' card (Ace, King, Queen or Jack) is played. The next player must then ``cover'' that card, by playing one card for a Jack, two for a Queen, three for a King and four for an Ace. If a face card is played at any stage during this sequence, play switches and the other player must cover that card. When this sequence has ended, the player who exposed the last face card takes the entire heap, placing it face down under her existing deck. She then starts the next round by playing one card face up as before, and play continues until one player cannot play when called upon to do so, because they have no more cards.

Write a program that will simulate playing this game. Remember that a standard deck (or pack) of cards contains 52 cards. These are divided into 4 suits--Spades (  ), Hearts (  ), Diamonds (  ) and Clubs (  ). Within each suit there are 13 cards--Ace (A), 2-9, Ten (T), Jack (J), Queen (Q) and King (K).

Input

Input will consist of a series of decks of cards. Each deck will give the cards in order as they would be dealt (that is in the example deck below, the non-dealer would start the game by playing the H2). Decks will occupy 4 lines with 13 cards on each. The designation of each card will be the suit (S, H, D, C) followed by the rank (A, 2-9, T, J, Q, K). There will be exactly one space between cards. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each deck in the input. Each line will consist of the number of the winning player (1 is the dealer, 2 is the first to play) and the number of cards in the winner's hand (ignoring any on the stack), right justified in a field of width 3.

Sample input

HA H3 H4 CA SK S5 C5 S6 C4 D5 H7 HJ HQ
D4 D7 SJ DT H6 S9 CT HK C8 C9 D6 CJ C6
S8 D8 C2 S2 S3 C7 H5 DJ S4 DQ DK D9 D3
H9 DA SA CK CQ C3 HT SQ H8 S7 ST H2 D2
#

Sample output

1 44

simulation

#include<stdio.h>
#include<string>
#include<iostream>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int fn[128];
struct Node{
    Node(){}
    Node(string a){flower=a[0];if(isdigit(a[1]))which=a[1]-'0';else which=fn[a[1]];}
    void cons(string a){flower=a[0];if(isdigit(a[1]))which=a[1]-'0';else which=fn[a[1]];}
    int which;
    char flower;
    Node *pre;
    Node *next;
};
Node *head[2],*tail[2];
int fm[14];
void init(){
    fn['A']=1,fn['J']=11,fn['Q']=12,fn['K']=13,fn['T']=10;
    fm[1]=4,fm[11]=1,fm[12]=2,fm[13]=3;
}
int getN(int term){
    int num=0;
    Node *card=head[term];
    while(card!=NULL){
        num++;
        card=card->next;
    }
    return num;
}
void run(){
    bool term=1;
    int winner,need=0,cnum=0,c[2];
    bool smode=0;
    Node *card,*ttail=NULL,*thead=NULL;
    c[0]=c[1]=26;
    while(1){
        if(head[term]==NULL){winner=!term;break;}
        card=head[term],head[term]=head[term]->next;
        c[term]--;
        if(DBG)printf("term %d play %c%d\n",term,card->flower,card->which);
        
        card->next=NULL;
        if(thead==NULL)thead=card,ttail=card;
        else ttail->next=card,ttail=card;
        cnum++;
        
        if(card->which>=11||card->which==1){
            smode=1;
            need=fm[card->which],term=!term;
            if(DBG)printf("-------------seq %d start-----------\n",need);
        }
        else if(need>0)need--;
        if(!need){      //regular or end of cover
            if(smode){
                c[!term]+=cnum;
                if(head[!term]==NULL){head[!term]=thead;tail[!term]=ttail;} //don't mess up!!
                else tail[!term]->next=thead,tail[!term]=ttail;
                if(DBG){printf("-------------seq end-----------\n");
                    printf("%d acquire %d cards(%d)(%d)\n",!term,cnum,c[!term],getN(!term));
                }
                thead=ttail=NULL;
                smode=cnum=0;
            }
            term=!term;
        }
    }
    int num=c[winner];
    printf("%d%3d\n",winner+1,num);
}
int main(){
    string s1;
    init();
    bool term;
    while(cin>>s1){
        if(s1=="#")break;
        term=1;
        head[0]=head[1]=tail[0]=tail[1]=NULL;
        rep(i,52){
            if(i>0)cin>>s1;
            Node *n=new Node(s1);
            n->next=head[term],head[term]=n;
            if(tail[term]==NULL)tail[term]=n;
            term=!term;
        }
        run();
    }
    
}