11035 - Card Hands

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

Moderator: Board moderators

Post Reply
naguib
New poster
Posts: 5
Joined: Sat Mar 12, 2005 3:29 am

11035 - Card Hands

Post by naguib » Tue May 30, 2006 12:13 am

I get runtime error

Code: Select all

		for(i=0;i<n;i++)
		{
			fscanf(in,"%d",hands+i);
				for(j=0;j<hands[i];j++)
				{
					fscanf(in,"%s",cstr);
					cards[t++]=tonum(cstr);
				}
		}
		
is this a right way to read input
I checked "cstr" is some times more than 2 chars
is there problem with judge or with my code???

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 30, 2006 12:24 am

The problem statement says that one of the values a card may have is '10', which is two chars.
So yes, some card names may be longer than 2 characters.

naguib
New poster
Posts: 5
Joined: Sat Mar 12, 2005 3:29 am

Post by naguib » Tue May 30, 2006 1:13 am

stupid me anyway it still gives runtime error

Code: Select all

#include<algorithm>
#include<cstdio>
#include<list>
using namespace std;
FILE *in=stdin;//fopen("hands.in","r");
class node{public:
int i,c;
};
node arr[100009];
char cards[100009];
int hands[100009];
int cum[100009];
bool vis[55];
int n;
void err()
{
	while(1)printf("%s\n",cards);
}  
int tonum(char* c)
{
	int a,b;
	
	if(*c=='J')		b=10;
	else if(*c=='Q')b=11;
	else if(*c=='K')b=12;
	else if(*c=='A')b=0;
	else if(*c=='1')b=9,c[1]=c[2];
	else b=*c-'1';

	if(c[1]=='C')	  a=0;
	else if(c[1]=='D')a=1;
	else if(c[1]=='H')a=2;
	else			  a=3;

	return a*13+b;
}
bool operator < (node a,node b)
{
	return a.c<b.c;
}
bool cmp(char a,char b)
{
	return b<a;
}
int main()
{
	int i,j,k,t=0,ans=0,s,l;
	char cstr[10];
	cards[100008]=0;
	while(1)
	{
		fscanf(in,"%d",&n);
		ans=0;
		if(n==0)return 0;
		t=0;
		l=0;
		for(i=0;i<n;i++)							//reading hands
		{
			fscanf(in,"%d",hands+i);
				for(j=0;j<hands[i];j++)
				{
					fscanf(in,"%s",cstr);
					cards[t++]=tonum(cstr);
				}
		}
		for(i=0;i<n;i++)
			arr[i].i=i,arr[i].c=hands[i],l=max(l,hands[i]);   //storing in a array of class "node"

		cum[0]=0;
		for(i=1;i<n;i++)										//bulding cummulative sum table
			cum[i]=cum[i-1]+hands[i-1];

		sort(arr,arr+n);									//sorting hands  accsendingly on number of cards


		for(i=0;i<n;i++)								//sorting each hand
			sort(cards+cum[i],cards+cum[i]+hands[i],cmp);
		s=0;
		for(i=0;i<l;i++)								//greedy algorithm to count nodes
		{
			memset(vis,0,sizeof(vis));					
			for(j=s;j<n;j++)							//count how many different card in position i of each hand
			{
				if(!vis[cards[cum[arr[j].i]+i]])ans++,vis[cards[cum[arr[j].i]+i]]=1;
				if(arr[j].c-1==i)
					s++;
			}
		}
		printf("%d\n",ans);
	}
}
I know that u probably hates reading others code ,but would u plz help me to find what could cause runtime error

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jun 03, 2006 5:55 pm

What is the output for the following input set?

Input:

Code: Select all

3
3 7D AH 5S
4 9C 3D 4D 5S
2 AH 5S
3
3 7D AH 5S
4 9C 3D 4D 5S
2 AH 5S
3
4 2D 4D AH 5S
3 3D AH 5S
4 2D 3D AH 5S
2
2 2D 3D
1 2D
3
4 9C 3D 4D 6S
4 9C 3D 4D 5S
3 10C 4D 7S
3
2 10C 10H
2 10C 10S
1 10H
3
3 7D AH 5S
4 9C 3D 4D 5S
3 3D AH 5S
0
Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Jun 03, 2006 8:26 pm

anyone please describe your algo, i cant find a good solution
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jun 03, 2006 9:13 pm

I reverse each hand and insert them into a trie.
And then just print the number of nodes in the trie.

To Jan:
I get this output

Code: Select all

6
6
6
3
11
4
7

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Jun 03, 2006 9:29 pm

oh, thats it. i just misunderstood the problem :oops:
ok now, i solved the problem,
to mf:
my program takes memory 12MB, while yours less than 2 MB, dont your trie node has 52 pointers? i used
typedef struct rec
{
struct rec *next[52];
} node;
and of course i free the trie everytime.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jun 03, 2006 10:53 pm

You can implement a trie with just two pointers per node: pointer to node's first child and node's sibling (the node following it in its parent's childs list).

naguib
New poster
Posts: 5
Joined: Sat Mar 12, 2005 3:29 am

Post by naguib » Sat Jun 03, 2006 11:41 pm

I think I missunderstood the problem would some body reword it with examples

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sun Jun 04, 2006 8:34 am

to mf, thank you very much, i didnt know the great idea before.

to naguib:

Code: Select all

for the test case:
3 
3 7D AH 5S 
4 9C 3D 4D 5S 
2 AH 5S

9C-3D-4D
        \
         5S   (only 6 nodes)
        /
   7D-AH

3 
3 7D AH 5S 
4 9C 3D 4D 5S 
3 3D AH 5S

    7D
     \
   3D-AH-5S   (only 7 nodes)
        /
9C-3D-4D
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 04, 2006 11:31 am

My method was similar to that of mf...
.. but I didn't use any tries.

1] Reverse all the hands.
2] Sort each hand in increasing order of first value, if there is a tie then in order of increasing second value and so on..
3] Set ans = total number of cards
3] Then simply apply plain, old dfs() to reduce the number of common starting cards.

It took 3MB of memory.

JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

Re: 11035 - Card Hands

Post by JohnTortugo » Sat Apr 11, 2009 1:57 am

Hi, I know its too late, but I'll apreciate if somebody can give me the correct output for the input case below :wink: :

Code: Select all

3
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
5
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
4 6D 7D 8D AH
4 6D 7D 8D AH
0
Thank you very much.
John.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11035 - Card Hands

Post by Jan » Fri May 08, 2009 4:38 am

My code returns.

Output:

Code: Select all

5
8
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 110 (11000-11099)”