10205 - Stack 'em Up

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zhenh
New poster
Posts: 10
Joined: Mon Oct 18, 2004 3:52 pm

I got WA,too

Post by zhenh » Mon Oct 18, 2004 3:57 pm

[code][c]
#include <stdio.h>

char n_club[] = "Clubs";
char n_diamond[] = "Diamonds";
char n_heart[] = "Hearts";
char n_spade[] = "Spades";
char *suit_names[4] = { n_club, n_diamond, n_heart, n_spade };

char n_2[] = "2";
char n_3[] = "3";
char n_4[] = "4";
char n_5[] = "5";
char n_6[] = "6";
char n_7[] = "7";
char n_8[] = "8";
char n_9[] = "9";
char n_10[] = "10";
char n_J[] = "Jack";
char n_Q[] = "Queen";
char n_K[] = "King";
char n_A[] = "Ace";
char *card_names[13] = { n_2, n_3, n_4, n_5, n_6, n_7, n_8,
n_9, n_10, n_J, n_Q, n_K, n_A };

int shuffle[100][52];

void reset_cards( int * cards )
{
int i;
for ( i=1;i<53;i++ )
cards[i] = i;
}

void copy_cards( int *dest, int *src )
{
int i;
for ( i=1;i<53;i++ )
dest[i] = src[i];
}

int main( int argc, char *argv[] )
{
int n_case;
int n_shuffles;
int cmd;
int i,j;
int cards_A[53],cards_B[53];

// FILE *si,*so;
// si = freopen( "input.txt","r",stdin);
// so = freopen( "output.txt","w",stdout);

fscanf(stdin,"%d",&n_case);

while ( n_case )
{
fscanf(stdin,"%d",&n_shuffles);
reset_cards( cards_A );
j = 0;
while ( j < n_shuffles )
{
for ( i=0;i<52;i++ )
{
fscanf(stdin,"%d",&cmd);
shuffle[j][i] = cmd;
}
j++;
}
while ( (cmd = getc(stdin)) != EOF )
{
if ( (j=getc(stdin))=='\n')
break;
else
ungetc(j,stdin);
fscanf(stdin,"%d",&cmd);
for ( i=1;i<53;i++ )
cards_B[i] = cards_A[shuffle[cmd-1][i-1]];
copy_cards( cards_A, cards_B );
}

for ( i=1;i<53;i++ )
printf("%s of %s\n",card_names[(cards_A[i]-1)%13],
suit_names[(cards_A[i]-1)/13] );
if ( --n_case > 0 )
putchar('\n');
}
// fclose(so);
// fclose(si);
return 0;
}[/code][/c]

Well, I see nothing wrong...but...I got WAs... :-?

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

why WA in 10205

Post by CodeMaker » Sat Nov 13, 2004 7:47 am

Hi , I am getting continuous WA in problems one after another.....looks like i will go mad....a helping hand will do :cry: [c]#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct cardlist
{
char value[20];
int pos;
};

typedef struct cardlist card;

int cmp(const void *a,const void *b)
{
card *p=(card*)a;
card *q=(card*)b;

return p->pos-q->pos;
}

void main()
{
int cases,shufle,a[101][53],j,k,v;
card stack[52+1];
char temp[100];

freopen("st.in","r",stdin);
scanf("%d",&cases);
while(cases--)
{
scanf("%d",&shufle);

strcpy(stack[1].value,"2 of Clubs");
strcpy(stack[2].value,"3 of Clubs");
strcpy(stack[3].value,"4 of Clubs");
strcpy(stack[4].value,"5 of Clubs");
strcpy(stack[5].value,"6 of Clubs");
strcpy(stack[6].value,"7 of Clubs");
strcpy(stack[7].value,"8 of Clubs");
strcpy(stack[8].value,"9 of Clubs");
strcpy(stack[9].value,"10 of Clubs");
strcpy(stack[10].value,"Jack of Clubs");
strcpy(stack[11].value,"Queen of Clubs");
strcpy(stack[12].value,"King of Clubs");
strcpy(stack[13].value,"Ace of Clubs");

strcpy(stack[14].value,"2 of Diamonds");
strcpy(stack[15].value,"3 of Diamonds");
strcpy(stack[16].value,"4 of Diamonds");
strcpy(stack[17].value,"5 of Diamonds");
strcpy(stack[18].value,"6 of Diamonds");
strcpy(stack[19].value,"7 of Diamonds");
strcpy(stack[20].value,"8 of Diamonds");
strcpy(stack[21].value,"9 of Diamonds");
strcpy(stack[22].value,"10 of Diamonds");
strcpy(stack[23].value,"Jack of Diamonds");
strcpy(stack[24].value,"Queen of Diamonds");
strcpy(stack[25].value,"King of Diamonds");
strcpy(stack[26].value,"Ace of Diamonds");

strcpy(stack[27].value,"2 of Hearts");
strcpy(stack[28].value,"3 of Hearts");
strcpy(stack[29].value,"4 of Hearts");
strcpy(stack[30].value,"5 of Hearts");
strcpy(stack[31].value,"6 of Hearts");
strcpy(stack[32].value,"7 of Hearts");
strcpy(stack[33].value,"8 of Hearts");
strcpy(stack[34].value,"9 of Hearts");
strcpy(stack[35].value,"10 of Hearts");
strcpy(stack[36].value,"Jack of Hearts");
strcpy(stack[37].value,"Queen of Hearts");
strcpy(stack[38].value,"King of Hearts");
strcpy(stack[39].value,"Ace of Hearts");

strcpy(stack[40].value,"2 of Spades");
strcpy(stack[41].value,"3 of Spades");
strcpy(stack[42].value,"4 of Spades");
strcpy(stack[43].value,"5 of Spades");
strcpy(stack[44].value,"6 of Spades");
strcpy(stack[45].value,"7 of Spades");
strcpy(stack[46].value,"8 of Spades");
strcpy(stack[47].value,"9 of Spades");
strcpy(stack[48].value,"10 of Spades");
strcpy(stack[49].value,"Jack of Spades");
strcpy(stack[50].value,"Queen of Spades");
strcpy(stack[51].value,"King of Spades");
strcpy(stack[52].value,"Ace of Spades");


for(j=1;j<=52;j++)
{
stack[j].pos=j;
}

stack[0].pos=-99999999;

for(j=1;j<=shufle;j++)
{
for(k=1;k<=52;k++)
{
scanf("%d",&a[j][k]);
}
}

getchar();
while(gets(temp) && strlen(temp))
{
v=atoi(temp);

for(j=1;j<=52;j++)
{
stack[j].pos=a[v][j];
}
qsort(stack,52+1,sizeof(stack[0]),cmp);

}

for(j=1;j<=52;j++)
{
printf("%s\n",stack[j].value);
}
if(cases)
printf("\n");
}
}
[/c]
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sat Nov 13, 2004 12:54 pm

:D Hi, I got accepted right now, what I did wrong was that I was swaping in reverse.... :oops:
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sat Nov 13, 2004 12:56 pm

:D Hi, I got accepted right now, what I did wrong was that I was swaping in reverse.... :oops:
Jalal : AIUB SPARKS

JackBauer
New poster
Posts: 19
Joined: Sun Mar 21, 2004 8:07 pm

10205

Post by JackBauer » Sun Nov 28, 2004 3:05 am

Hello,

is problem's 10205, Stack 'em Up, out, output example correct ?

Let's see:

the sequence starts with:

0 | 1 | 2 | 2 | ... | 50 | 51
1 | 2 | 3 | 4 .... | 51 | 52

(first line is array index)

And they say there are two shuffles:

1st (x = 0, y = 1)
2nd ( x=0, y=51)

SO shuffle #1 changes to:

2 | 1 | 3 | 4 | ... 51 | 52

and now, shuffle #2 changes to:

52 | 1 | 3 | 4 ... | 51 | 2

card # 52 = Ace of Spades
card # 2 = 3 of Clubs

But the example output gives "King of Spades" as first card (that would be card #51).

What do you think? Maybe I'm not understanding the problem.

Thanks for your help.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Nov 28, 2004 9:58 am

You assume that only one exchange can happen during each shuffle, but in fact any permutation of the cards can happen during one shuffle.
In the first shuffle of the sample input both (0 <-> 1) and (50 <-> 51) take place!

JackBauer
New poster
Posts: 19
Joined: Sun Mar 21, 2004 8:07 pm

Post by JackBauer » Sun Nov 28, 2004 5:02 pm

little joey wrote:You assume that only one exchange can happen during each shuffle, but in fact any permutation of the cards can happen during one shuffle.
In the first shuffle of the sample input both (0 <-> 1) and (50 <-> 51) take place!
Didn't read the example input properly. Thanks for your help.

Billy
New poster
Posts: 3
Joined: Wed Nov 03, 2004 11:40 am

Post by Billy » Wed Dec 01, 2004 12:36 am

CodeMaker wrote::D Hi, I got accepted right now, what I did wrong was that I was swaping in reverse.... :oops:
Please, could you show us the correction of your swaping??

Thanks ...

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

10205 TLE is unbelievable

Post by Nazmul Quader Zinnuree » Thu Sep 08, 2005 8:07 pm

Am i taking too much time?? or
misunderstanding the problem...
or, doing sth wrong...
Here is it...

Code: Select all

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

#define MAX 102

char suit[5][10] = {"Clubs", "Diamonds", "Hearts", "Spades"};
char value[15][10] = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"};

int suffle[MAX][55];
char cards[55][25], newcards[55][25];

void init_deck(void)
{
	int i, j, k = 0;

	for (i = 0; i < 4; i++)
		for (j = 0; j < 13; j++)
		{
			strcpy(cards[k], value[j]);
			strcat(cards[k], " of ");
			strcat(cards[k], suit[i]);
			k++;
		}
}

int main(void)
{
	char in[500], *p;
	int tc;
	int n, i, j, d;

	gets(in);
	tc = atoi(in);
	gets(in);
	while (tc--)
	{
		gets(in);
		n = atoi(in);
		for (i = 0; i < n; i++)
		{
			j = 0;
			gets(in);
			p = strtok(in, " ");
			while (p != NULL)
			{
				suffle[i][j++] = atoi(p);
				p = strtok(NULL, " ");
			}
			gets(in);
			p = strtok(in, " ");
			while (p != NULL)
			{
				suffle[i][j++] = atoi(p);
				p = strtok(NULL, " ");
			}
		}

		init_deck();

		while (1)
		{
			gets(in);
			if (!in[0])
				break;
			p = strtok(in, " ");
			if (p == NULL)
				break;

			d = atoi(p);
			for (i = 0; i < 52; i++)
				strcpy(newcards[suffle[d - 1][i] - 1], cards[i]);

			for (i = 0; i < 52; i++)
				strcpy(cards[i], newcards[i]);
		}
		
		for (i = 0; i < 52; i++)
			printf ("%s\n", cards[i]);

		if (tc)
			printf ("\n");
	}
	return 0;
}
THNX

mosaick2
New poster
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

10205 - I got TLE..

Post by mosaick2 » Sat Mar 18, 2006 6:37 am

I have a question.
I used the dynamic allocation for this problem.
Was it the reason why I got TLE?

If I use a static array instread of dynamic allocation,
Is It possible to faster my program than before?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Mar 18, 2006 9:34 am

I don't think that is the problem.

I got an AC in Java in 0.025. You are probably in an infinite loop.

Darko

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

10205

Post by WRJ » Thu Mar 30, 2006 10:23 pm

http://acm.uva.es/p/v102/10205.html
I have WA :(
Please help or send test which my program fails.

Code: Select all

#include <cstdio>

int tab[105][54], wyn[54], seq[800000], n, st;

void printcard(int x)
{
	int col, nr;
	x--;
	nr = x%13;
	col = x/13;
	if (nr<=8) printf("%d", nr+2);
	if (nr==9) printf("Jack");
	if (nr==10) printf("Queen");
	if (nr==11) printf("King");
	if (nr==12) printf("Ace");
	printf(" of ");
	if (col==0) printf("Clubs\n");
	if (col==1) printf("Diamonds\n");
	if (col==2) printf("Hearts\n");
	if (col==3) printf("Spades\n");	
}


void printresult()
{
	int i;
	for (i=1;i<53;i++) printcard(wyn[i]);
}

void readdata()
{
	st = -1;
	scanf("%d", &n);
	int i, j, pom;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<53;j++) scanf("%d", &tab[i][j]);
	}
	char pop, wc;
	int ak;
	ak  = 0;
	pop = ' ';
	while(scanf("%c",&wc)!=EOF)
	{
		if (wc=='\n')
		{
			if (pop =='\n') 
			{
				ak = 0;
				break;
			} else
			{
				if (ak) seq[++st] = ak;
				ak = 0;
				pop = wc;
				continue;
			}
		} 
		ak *= 10;
		ak += wc-48;
		pop = wc;
	}
	if (ak) seq[++st] = ak;
}

void oblicz()
{
	int i, j, x;
	for (i=1;i<53;i++)
	{
		x = i;
		for (j=0;j<=st;j++)
		{
			x = tab[seq[j]][x];
		}		
		wyn[x] = i;
	}
}

void set()
{
	int i;
	for (i=0;i<53;i++) wyn[i] = i;
}

int main()
{
	int b, il;
	b = 0;
	scanf("%d", &il);
	while (il--)
	{
		set();
		if (b) printf("\n");
		readdata();
		oblicz();
		printresult();
		b = 1;
	}
	return 0;
}

spicy_hair
New poster
Posts: 7
Joined: Wed Jul 19, 2006 12:26 am
Location: Calgary, Canada

10205

Post by spicy_hair » Thu Jul 20, 2006 9:46 pm

SOMEONE HELP ME!!! i keep getting lte on this program and i cant take it anymore

Code: Select all

#include <stdio.h>

int main(void){
	int nc, n, k, s1, ran;
    int counter=0,i,j,a;  /*counter*/
    int shuffle [105][53];
    int order [1][53];
    char s[10], r;
    
    scanf ("%d", &nc);
    gets(s);
    
    for (i=0;i<nc;i++){
    	scanf ("%d", &n);
    	for (j=1;j<=n;j++){
    		for (a=1;a<=52;a++){
                scanf ("%d", &shuffle [j][a]);
    		}
    	}
    	
    	counter=0;
    	for (j=1;j<=52;j++) order [counter][j]=j; /*cards before shuffle*/
    	
        gets (s);
        gets (s);
        while (s[0]!='\0'){
        	sscanf (s, "%d", &s1);
        	if (counter){
        		for (j=1;j<=52;j++){
        			order[0][shuffle[s1][j]]=order[1][j];
        		}
        		counter=0;
        	}
        	else{
        		for (j=1;j<=52;j++){
        			order[1][shuffle[s1][j]]=order[0][j];
        		}
        		counter=1;
        	}
        	gets (s);
        }
        
        if (counter){
        	for (j=1;j<=52;j++){
        		if (order[1][j]%13<10 && order[1][j]%13>0 ){
        		printf ("%d of ", order[1][j]%13+1);
        		}
        		else {
        			if (order[1][j]%13==10) printf ("Jack of ");
        			if (order[1][j]%13==11) printf ("Queen of ");
        			if (order[1][j]%13==12) printf ("King of ");
        			if (order[1][j]%13==0) printf ("Ace of ");
        		}
        		switch ((order[1][j]-1)/13){
        			case 0:
        			printf ("Clubs\n");
        			break;
        			case 1:
        			printf ("Diamonds\n");
        			break;
        			case 2:
        			printf ("Hearts\n");
        			break;
        			case 3:
        			printf ("Spades\n");
        			break;
        			default:
        			printf ("apohrgaepogauhg");
        		}
        	}
        }
        else {
        	for (j=1;j<=52;j++){
        		if (order[0][j]%13<10 && order[0][j]%13>0 ){
        		printf ("%d of ", order[0][j]%13+1);
        		}
        		else {
        			if (order[0][j]%13==10) printf ("Jack of ");
        			if (order[0][j]%13==11) printf ("Queen of ");
        			if (order[0][j]%13==12) printf ("King of ");
        			if (order[0][j]%13==0) printf ("Ace of ");
        		}
        		switch ((order[0][j]-1)/13){
        			case 0:
        			printf ("Clubs\n");
        			break;
        			case 1:
        			printf ("Diamonds\n");
        			break;
        			case 2:
        			printf ("Hearts\n");
        			break;
        			case 3:
        			printf ("Spades\n");
        			break;
        			default:
        			printf ("apohrgaepogauhg");
        		}
        	}
        }
        printf ("\n");
    }
    
    return 0;
    
}
thanx

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Jul 20, 2006 11:57 pm

Does that work on your computer? On mine it doesn't - when I compile it it warns me about gets, and it runs forever. So I looked it up (man gets) and it says "Never use gets." Right there in gets() man pages :)

So I removed all gets() and it worked. Only thing is - instead of that while(s[0] != '\0') I had while(k-- > 0) (I set k to 52) and used scanf() instead of sscanf().

Btw, I think scanf just skips whitespace, you don't need gets() to read blank line before scanf().

[EDIT] Hm, I just realized you are from Calgary - do I know you? :)

spicy_hair
New poster
Posts: 7
Joined: Wed Jul 19, 2006 12:26 am
Location: Calgary, Canada

Post by spicy_hair » Fri Jul 21, 2006 6:39 am

Darko

thanx for replying!

the gets () function does not work on your computer? well...i didnt know how that happened (cuz it worked perfectly on mine). but i do think it is the problem. i just have one more question: without gets(), how would i detect blank lines? the question states that there would be a blank line in between each case, and the number of shuffles (k) actually performed by the dealer is unknown. i tried your method (swithing while(s[0] != '\0') to while(k-- > 0) ) and got re. do you have any idea what happened?

ps: ur from calgary as well? hehe maybe you dont know me. i just moved in calgary from toronto three weeks ago. :P you seem to have a lot of programming experience! hope we can keep in touch (you can alwayz email me or msn me :wink: )

Post Reply

Return to “Volume 102 (10200-10299)”