10776 - Determine The Combination

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

Moderator: Board moderators

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10776 - Determine The Combination

Post by medv » 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;
}

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » 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.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » 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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » 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.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Accepted

Post by medv » 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.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Thu Nov 25, 2004 10:26 pm

Thanks,

I missed this statement from problem description.

Wojciech

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

WAAAAAAAAAAAAAA

Post by I LIKE GN » Fri Aug 26, 2005 4:56 pm

hello all
i also have problems...
please post some I/O...
:oops: thx...
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: WAAAAAAAAAAAAAA

Post by Martin Macko » 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

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » 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
Last edited by I LIKE GN on Fri Sep 02, 2005 1:42 am, edited 1 time in total.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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;

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

ACCCCCCCCCC

Post by I LIKE GN » Fri Sep 02, 2005 1:41 am

ha ha
that was my mistake!!!!!!!!!!!
really unthinkable...
thanks :D :D :D :D :wink: :wink: :wink:
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » 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
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 10776 - Determine The combination

Post by valkov » 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

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 10776 - Determine The combination

Post by mathgirl » 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

Post Reply

Return to “Volume 107 (10700-10799)”