OJ Board

Posted: **Wed Nov 24, 2004 11:07 pm**

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

int len,r;
char s[1001];
char p[1001];

int compare(const void *a, const void *b)
{
return *(char *)a - *(char *)b;
}

void print(void)
{
int i;
for(i=0;i<len;i++)
printf("%c",p[i]);
printf("\n");
}

void doit(int pos,int depth)
{
int i;
if (depth == r) print(); else
for(i=pos;i<len;)
{
p[depth] = s[i];
doit(i+1,depth+1);
i++;while(s[i] == s[i-1]) i++;
}
}

int main(void){
while(scanf("%s %d",&s,&r) == 2)
{
len = strlen(s);
qsort(s,len,sizeof(char),compare);
doit(0,0);
memset(p,0,sizeof(p));
}
return 0;
}

Posted: **Thu Nov 25, 2004 8:29 am**

void print(void)
{
int i;
for(i=0;i<len;i++)
printf("%c",p);
printf("\n");
}

I think it should be i<r, not i<len. But I wonder why you didn't notice it for the sample input/output.

Posted: **Thu Nov 25, 2004 9:46 pm**

Hi !

I have another question related to this problem:

Is it possible to manage the input like this:

"abcdefghijklmnopqrstuvwxyzabcd 15"

within time limit?

Wojciech

Posted: **Thu Nov 25, 2004 10:14 pm**

Quoting the problem description:

You can assume there are at most 1000 different ones.

Of course you can get trouble with the time and memory limit, if for example 30 'a' are given, and you remove duplicates only after you constructed all combinations.

Posted: **Thu Nov 25, 2004 10:16 pm**

Thank to Adrian. I don't know why I did sso silly mistake.

To w k: problem statement says that for each input test you have
no more than 100 solutions.

Posted: **Thu Nov 25, 2004 10:26 pm**

Thanks,

I missed this statement from problem description.

Wojciech

Posted: **Fri Aug 26, 2005 4:56 pm**

hello all
i also have problems...
please post some I/O...

thx...

Posted: **Tue Aug 30, 2005 3:31 pm**

Try this I/O:

Code: Select all

a 1
aa 1
aa 2
aaa 1
aaa 2
aaa 3
aaaa 1
aaaa 2
aaaa 3
aaaa 4
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 3
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 15
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 28
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 29
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 30
timg 2
ghtrwe 1
greuiwgnqeruingirndajfk 23
grequignfdangfjadngkfne 23
geruignreiqgnfjlangfeag 22

My AC's output:

Code: Select all

a
a
aa
a
aa
aaa
a
aa
aaa
aaaa
a
aa
aaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
gi
gm
gt
im
it
mt
e
g
h
r
t
w
adeefgggiiijknnnqrrruuw
aaddeefffggggijknnnnqru
aaeeeffgggggiijlnnnqrr
aaeeeffgggggiijlnnnqru
aaeeeffgggggiijlnnnrru
aaeeeffgggggiijlnnqrru
aaeeeffgggggiijnnnqrru
aaeeeffgggggiilnnnqrru
aaeeeffgggggijlnnnqrru
aaeeeffggggiijlnnnqrru
aaeeefgggggiijlnnnqrru
aaeeffgggggiijlnnnqrru
aeeeffgggggiijlnnnqrru

Posted: **Thu Sep 01, 2005 9:52 pm**

hello Martin Macko
i got "good" output for all the abob once but WA...
here is my code

Code: Select all

cut got ACC...

thank UUUUUUUUU

Posted: **Thu Sep 01, 2005 11:02 pm**

I LIKE GN wrote:

Code: Select all

	...
	int j; char x;

	for(j = i+1; s[j]; j++){
		if( s[j] ^ x ){
			x = s[j]; soln[len] = s[j];
			recurse(j, len+1);
		}
	}
	...

You are not initializing x in recurse(). Set it to something... eg. to 0

Code: Select all

	int j; char x=0;

Posted: **Fri Sep 02, 2005 1:41 am**

ha ha
that was my mistake!!!!!!!!!!!
really unthinkable...
thanks

Posted: **Fri Sep 08, 2006 9:40 pm**

hello,
what shall I do to avoid repeated combinations?

Code: Select all


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

#define SLEN 35

/* global environment */
	char seq[SLEN] = {0};
	char stmp[SLEN] = {0};
	int slen = 0;


int ch_cmp( const void *a, const void *b )
{
	return *((char *)a) - *((char *)b);
} 


void make_k_comb( int n, int s, int a )
{
	int i, j;

	if( n == 1 )
		{
			for( i = s; i < slen; i++ )
				{
				/*	if( seq[i] == seq[i-1] ) continue;*/
					stmp[a] = seq[i];
					stmp[a+1] = 0; /* to string */
					printf( "%s\n", stmp );
				}
		}
	else
		{
			for( i = s; i < slen-1; i++ )
				{
					stmp[a] = seq[i];
					make_k_comb( n-1, i+1, a+1 );
				}
		}
}

int main()
{
	int r;
	
	while( scanf( "%s %d", seq, &r ) == 2 )
		{
			slen = strlen(seq);
			qsort( seq, slen, sizeof(char), ch_cmp );
			make_k_comb( r, 0, 0 );
		}

	return 0;
}

thanks

Posted: **Sat Oct 14, 2006 10:08 am**

instead of working with the sorted string, work with frequencies of each letter, and always generate words in nondecreasing order.

Posted: **Sun May 08, 2011 1:23 pm**

Just got AC on this one.
Simple way to do it is:

Code: Select all

1.Sort the input string
2.After generating the current combination the next one should start with a different character

Posted: **Sun Jun 03, 2012 5:56 pm**

Can someone who got AC give the output for the following

AaBb 2
AaBb 3
aBCDE 3
aaaa 2
aabb 2
aaBB 2

OJ Board

10776 - Determine The Combination

10776 - Determine The Combination

Accepted

WAAAAAAAAAAAAAA

Re: WAAAAAAAAAAAAAA

ACCCCCCCCCC

Re: 10776 - Determine The combination

Re: 10776 - Determine The combination