10568 - n Group k

[rbuchan]

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

[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]

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]

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]

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]

Yes, use recursion.

[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.

[..]

my accepted code gives the same output.

[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?

[the LA-Z-BOy]

i just got it AC . the problem was in sorting the output in lexic order...
thanks.