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

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Hi !

I have another question related to this problem:

Is it possible to manage the input like this:

"abcdefghijklmnopqrstuvwxyzabcd 15"

within time limit?

Wojciech

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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

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

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

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

### Re: WAAAAAAAAAAAAAA

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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

ha ha
that was my mistake!!!!!!!!!!!
really unthinkable...
thanks
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
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:
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

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

Can someone who got AC give the output for the following

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