10776 - Determine The Combination

[medv]

#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;
}

[Adrian Kuegel]

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.

[w k]

Hi !

I have another question related to this problem:

Is it possible to manage the input like this:

"abcdefghijklmnopqrstuvwxyzabcd 15"

within time limit?

Wojciech

[Adrian Kuegel]

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.

[medv]

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.

[w k]

Thanks,

I missed this statement from problem description.

Wojciech

[I LIKE GN]

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

[Martin Macko]

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

[I LIKE GN]

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

[Martin Macko]

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;

[I LIKE GN]

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

[beloni]

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

[sclo]

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

[valkov]

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

[mathgirl]

Can someone who got AC give the output for the following

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