10568 - n Group k

All about problems in Volume 105. 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
rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

10568 - n Group k

Post by rbuchan »

Am I missing something with this problem? Or is it ridiculously easy?

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

Well...... I understand the question to mean something like a group 10 3 would include things like:
ABC DEF GHI J
ADF BCJ EHI G
etc.... at first glance it doesn't appear 'ridiculously easy' to me......

poulls
New poster
Posts: 3
Joined: Mon Jul 21, 2003 12:54 pm

10568 why I got ML and WA ?

Post by poulls »

can you help me why I got WA?
and why after I plus the red sentence it becomes ML?

Code: Select all

#include<iostream>
#include<string.h>

using namespace std;

unsigned long long cnt;
int n,k,p,q;
char z[100],tab[100],s[1000];
int ptag,qtag,partial,len;


unsigned long long cmb(int k,int n)
{
	unsigned long long i;
	unsigned long long t=1;
	for (i=1;i<=k;i++)
	{t*=(n+1-i); t/=i;}
	return (unsigned long long)(t);
}

unsigned long long pmn(int t)
{
	unsigned long long i;
	unsigned long long result=1;
	for (i=1;i<=t;i++)
	result*=i;
	return result;
}

unsigned long long  getmethod()
{
	unsigned long long i=n,j;
	unsigned long long count=1;
	if (n%p==0){ k=n/p;q=0;
		ptag=k; qtag=0;
	}else{
		k=n/p+1;
		q=n-(k-1)*p;
		ptag=k-1; qtag=1;
	}
	j=ptag;
	while(j)
	{
		count*=cmb(p,i);
		i-=p; j--;
	}
	count/=pmn(ptag);
	return count;
}


void initial()
{
	z[1]='A'; tab[1]=1;
	len=n+k-1; 
	partial=1;
	for (int i=2;i<=n;i++)
	tab[i]=0;
}

void printstring()
{
	for (int i=1;i<=len;i++)
		cout<<z[i];
		cout<<endl;
}


void print(int level,int t)
{
	int i,first;
	if (level==len+1){
		z[len+1]='\0';
		printstring();
		return;
	}
	 
	first=(partial==0?2:t+1);
	if (qtag&&n%p&&partial==q)
	{
		z[level]=' '; partial=0; qtag--; print(level+1,i); qtag++;partial=q;
		for (i=first;i<=n;i++)
		if (!tab[i])
		{	tab[i]=1; z[level]='A'+i-1; partial++; print(level+1,i);
			partial--; tab[i]=0;}
	}else  if (ptag&&partial==p)
	{
		z[level]=' '; partial=0; ptag--; print(level+1, i);partial=p; ptag++;
	}else 
	{
		if (partial==0)
		{
			for (i=first;i<=n;i++)
			if (!tab[i])
			{	tab[i]=1; z[level]='A'+i-1; partial++; print(level+1,i);
			partial--; tab[i]=0;return;}	
		}
		else{
		for (i=first;i<=n;i++)
		if (!tab[i])
		{	tab[i]=1; z[level]='A'+i-1; partial++; print(level+1,i);
			partial--; tab[i]=0;}
		}
	}
}

void printmethod()
{
	initial();
	print(2,1);
}
int main()
{
	while(cin>>s)
	{
		if (strcmp(s,"END")==0) break;
		cin>>n>>p;
		[color=red]//if (p>n){int temp=p; p=n;n=temp;}[/color]
		cnt=getmethod();
		if (strcmp(s,"COUNT")==0)
		cout<<cnt<<endl;
		if (strcmp(s,"GENERATE")==0)
		{
			cout<<cnt<<endl;
			printmethod();
		}
	}
	return 0;
}

poulls
New poster
Posts: 3
Joined: Mon Jul 21, 2003 12:54 pm

I found my fault!

Post by poulls »

With the help of a friend I found my fault:
1 I didn't use the BigNum
2 if (k>n) then you should do k=n;

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan »

Why do you need to use BigNumber for this problem? The problem statement clearly says:
You can assume that the output will always fit in a 64bit unsigned integer.
It may happen that for your implementation the intermediate results go out of that limit. But trust me there are ways to avoid that.

koala
New poster
Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China
Contact:

agree

Post by koala »

Yes, use recursion. :D

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

give me some outputs

Post by the LA-Z-BOy »

what is the correct output for this set of data?

Code: Select all

COUNT 1 1
COUNT 10 11
COUNT 30 1
COUNT 30 2
COUNT 30 3
COUNT 30 4
COUNT 30 5
COUNT 30 6
COUNT 30 7
COUNT 30 8
COUNT 30 9
COUNT 30 10
COUNT 30 11
COUNT 30 12
COUNT 30 13
COUNT 30 14
COUNT 30 15
COUNT 30 16
COUNT 30 17
COUNT 30 18
COUNT 30 19
COUNT 30 20
COUNT 30 21
COUNT 30 22
COUNT 30 23
COUNT 30 24
COUNT 30 25
COUNT 30 26
COUNT 30 27
COUNT 30 28
COUNT 30 29
COUNT 27 1
COUNT 27 2
COUNT 27 3
COUNT 27 4
COUNT 27 5
COUNT 27 6
COUNT 27 7
COUNT 27 8
COUNT 27 9
COUNT 27 10
COUNT 27 11
COUNT 27 12
COUNT 27 13
COUNT 27 14
COUNT 27 15
COUNT 27 16
COUNT 27 17
COUNT 27 18
COUNT 27 19
COUNT 27 20
COUNT 27 21
COUNT 27 22
COUNT 27 23
COUNT 27 24
COUNT 27 25
COUNT 27 26
COUNT 15 1
COUNT 15 2
COUNT 15 3
COUNT 15 4
COUNT 15 5
COUNT 15 6
COUNT 15 7
COUNT 15 8
COUNT 15 9
COUNT 15 10
COUNT 15 11
COUNT 15 12
COUNT 15 13
COUNT 15 14
COUNT 12 1
COUNT 12 2
COUNT 12 3
COUNT 12 4
COUNT 12 5
COUNT 12 6
COUNT 12 7
COUNT 12 8
COUNT 12 9
COUNT 12 10
COUNT 12 11
COUNT 9 1
COUNT 9 2
COUNT 9 3
COUNT 9 4
COUNT 9 5
COUNT 9 6
COUNT 9 7
COUNT 9 8
COUNT 6 1
COUNT 6 2
COUNT 6 3
COUNT 6 4
COUNT 6 5
END
i get( WA)

Code: Select all

1
1
1
6190283353629375
1208883745669600000
5737475589799078125
123378675083039376
11423951396577720
8564395049496000
936730708538625
154194355315000
925166131890
2064420294300
802830114450
142514221500
8725360500
77558760
145422675
119759850
86493225
54627300
30045015
14307150
5852925
2035800
593775
142506
27405
4060
435
30
1
213458046676875
2977546171600000
13189599057009375
1823330173640976
281378113216200
19688264481600
4614436987875
37978905250
82034435340
28474762680
3954828150
140408100
20058300
17383860
13037895
8436285
4686825
2220075
888030
296010
80730
17550
2925
351
27
1
2027025
1401400
2627625
126126
210210
25740
6435
5005
3003
1365
455
105
15
1
10395
15400
5775
8316
462
792
495
220
66
12
1
945
280
315
126
84
36
9
1
15
10
15
6
thanks.
Istiaque Ahmed [the LA-Z-BOy]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

my accepted code gives the same output.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

thank you very much .. for your reply...
so i must have trouble with generating the groups... ( COUNT n,k shouldn't have any other crucial test cases... as my input seems to cover all types)
as the outputs are long enough i can't post some ins or outs for GENERATE n,k in this board... so i've to find my bug myself :(
by the way... unsigned long longs should be printed using %llu, in C/C++ right?
Istiaque Ahmed [the LA-Z-BOy]

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

:)

Post by the LA-Z-BOy »

i just got it AC :). the problem was in sorting the output in lexic order...
thanks.
Istiaque Ahmed [the LA-Z-BOy]

Post Reply

Return to “Volume 105 (10500-10599)”