Problem D - Snap

Problem D - Snap

时间： 1ms        内存：128M

描述：

Problem D - Snap

Snap is a 2-player card game. The deck of cards contains several of each type of card. Initially each player has one half of the deck, in some random sequence, face down in a pile, and plays them in sequence from top to bottom, placing each card face-up in another pile. When the face-down pile is exhausted, the face-up pile is turned over to become the face-down pile and play continues.

The two players play their cards concurrently and synchronously. That is, each places a card face up at exactly the same time. If two cards turned up at the same time are the same type, each player calls "Snap!" and the player who calls first takes the other's face-up pile and places it on top of his or her own.

Play proceeds until one player has all the cards. This player is the winner.

Your job is to simulate a game of snap to determine whether it will end within 1000 turns and, if so, to determine the winner.

Each type of card is denoted by a single letter or digit. The first line of input Jane's initial pile of cards, from top to bottom. The second line of input is John's initial pile. Jane and John start with the same number of cards; not more than 50 each.

During play, whenever it comes time to call "Snap!" the builtin function "random" is used to determine who calls first: if the expression

   random()/141%2           {in C or C++}

   random div 141 mod 2     {in Pascal; see note below}

yields 0, Jane calls first; otherwise John calls first. Whenever Jane calls first, print "Snap! for Jane: " followed by Jane's face-up pile, from top to bottom. Whenever John calls first, print "Snap! for John: " followed by John's face-up pile. If the game ends, print "John wins." or "Jane wins.", whichever is appropriate. If the game does not end when each player has turned over 1000 cards, print "Keeps going and going ..."

输入：

输出：

示例输入：

ABCDA
CBADC

示例输出：

Snap! for Jane: BCBA
Snap! for Jane: DADCBCBA
Snap! for John: CBAC
Snap! for John: ADADCBAC
John wins.

提示：

参考答案（内存最优[752]）：

/* use of random() portable among:

   Solaris, SunOS, DECUnix, Linux

*/

#include <stdio.h>
#include <stdlib.h>

char jane[200], john[200];
int janei, johni;

main(){
   int i,j;
   gets(jane);
   gets(john);
   for (j=janei=johni=0;j<1000 && strlen(jane)&&strlen(john);j++){
      if (jane[janei] == john[johni]) {
         if (random()/141%2 == 0) { /* jane wins */
            printf("Snap! for Jane: ");
            for (i=strlen(jane);i>janei;i--) jane[i+johni+1] = jane[i];
            strncpy(jane+janei+1,john,johni+1);
            strcpy(john,john+johni+1);
            janei = janei + johni + 2;
            johni = 0;
            for (i=janei-1;i>=0;i--) printf("%c",jane[i]);
            printf("\n");
         }else{  /* john wins */ 
            printf("Snap! for John: ");
            for (i=strlen(john);i>johni;i--) john[i+janei+1] = john[i];
            strncpy(john+johni+1,jane,janei+1);
            strcpy(jane,jane+janei+1);
            johni = johni + janei + 2;
            janei = 0;
            for (i=johni-1;i>=0;i--) printf("%c",john[i]);
            printf("\n");
         }
      }else{
         janei++; johni++;
      }
      if (!jane[janei]) janei = 0;
      if (!john[johni]) johni = 0;
   }
   if (!strlen(jane)) printf("John wins.\n");
   else if (!strlen(john)) printf("Jane wins.\n");
   else printf("No winner after %d turns\n",j);
}

参考答案（时间最优[3]）：

/* use of random() portable among:

   Solaris, SunOS, DECUnix, Linux

*/

#include <stdio.h>
#include <stdlib.h>

char jane[200], john[200];
int janei, johni;

main(){
   int i,j;
   gets(jane);
   gets(john);
   for (j=janei=johni=0;j<1000 && strlen(jane)&&strlen(john);j++){
      if (jane[janei] == john[johni]) {
         if (random()/141%2 == 0) { /* jane wins */
            printf("Snap! for Jane: ");
            for (i=strlen(jane);i>janei;i--) jane[i+johni+1] = jane[i];
            strncpy(jane+janei+1,john,johni+1);
            strcpy(john,john+johni+1);
            janei = janei + johni + 2;
            johni = 0;
            for (i=janei-1;i>=0;i--) printf("%c",jane[i]);
            printf("\n");
         }else{  /* john wins */ 
            printf("Snap! for John: ");
            for (i=strlen(john);i>johni;i--) john[i+janei+1] = john[i];
            strncpy(john+johni+1,jane,janei+1);
            strcpy(jane,jane+janei+1);
            johni = johni + janei + 2;
            janei = 0;
            for (i=johni-1;i>=0;i--) printf("%c",john[i]);
            printf("\n");
         }
      }else{
         janei++; johni++;
      }
      if (!jane[janei]) janei = 0;
      if (!john[johni]) johni = 0;
   }
   if (!strlen(jane)) printf("John wins.\n");
   else if (!strlen(john)) printf("Jane wins.\n");
   else printf("No winner after %d turns\n",j);
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。