Page 1 of 2

### 10581 - Partitioning for fun and profit

Posted: Tue Dec 23, 2003 9:58 am
I got several WA.But I can't find any mistake in my algorithm.
Is there some trick in the problem?
Can anyone give me some testdata please?

Posted: Tue Dec 23, 2003 12:46 pm
I don't think there are any tricks in this problem. Try this input:
3
220 10 1234567
100 2 49
220 5 132345
output should be:
1
1
1
1
2
11
42
42
59
60
49
51
2
26
58
60
74

### 10581

Posted: Mon Jan 26, 2004 6:35 pm
I don't know how to solve the problem.
Could someone give me some hints?
Thx

Posted: Fri May 07, 2004 6:21 am
I used DP to store a 3D table, storing in how many ways using M numbers, starting from I, and sum up to S. After constructing the table, can determine each individual number starting from left to right. I cannot think of a better way (likely due to limited ability/knowledge), though I believe there exists one.

Posted: Mon Dec 18, 2006 10:41 pm
Some cases...

Input:

Code: Select all

``````5
220 10 50
220 2 31
12 3 4
19 5 3
35 11 11``````
Output:

Code: Select all

``````1
1
1
1
1
1
1
1
50
162
31
189
1
4
7
1
1
1
3
13
1
1
1
1
1
1
1
1
1
11
15``````
Hope these help.

### thanks!

Posted: Tue Dec 19, 2006 12:44 pm
They did help, thanks a lot ! I've got Acc. I was misunderstanding the problem.

### some more test cases

Posted: Mon May 07, 2007 5:31 am
i am getting WA in this problem. could anyone provide more testcases. boundary cases would be very nice. i got correct results for all the above i/o. please help....

Posted: Tue May 08, 2007 11:45 am

Code: Select all

``````# include <stdio.h>
# include <assert.h>

typedef long long i64 ;
i64 memo[250][20];

i64 go( int sum , int n ){
i64& ret = memo[sum][n];
if(ret !=-1) return ret ;
if( !sum && !n ) return ret = 1 ;
ret = 0 ; int i ;
for( i = 1 ; i <= sum && n > 0 ; ++i ){
ret += go( sum - i , n - 1 ) ;
}return ret ;
}
void doit( int sum , int n , i64 idx){
if( !sum && !n ) return ;
int i ;
i64 ret ;
for( i= 1 ; i <= sum ;++i ){
ret = go( sum - i , n - 1 ) ;
if( ret >= idx ){
printf("%d\n",i);
doit(sum - i , n - 1 , idx ) ;
return ;
}
else{
idx-= ret ;
}
}
}
int main(){
int sum , n ;
i64 idx ;
int kase , i , j ; scanf("%d",&kase);

for(i=0;i<=221;++i){
for(j=0;j<=12;++j){
memo[i][j]=-1;
}
}
while(kase--){
scanf("%d %d %lld",&sum,&n,&idx);
doit( sum , n , idx ) ;
}

return 0 ;
}
``````

Posted: Tue May 08, 2007 2:21 pm
Try the cases.

Input:

Code: Select all

``````3
61 8 52
101 8 64
111 6 66``````
Output:

Code: Select all

``````1
1
1
1
1
2
26
28
1
1
1
1
1
2
18
76
1
1
1
2
14
92``````
Hope these help.

### I/O

Posted: Fri May 11, 2007 1:22 pm

Code: Select all

``````1
1
1
1
1
1
52
3
1
1
1
1
1
1
64
31
1
1
1
1
66
41
``````
what is ur output for

Code: Select all

``````10 4 10
``````
i get

Code: Select all

``````1
2
3
4
``````
is it right????

### Re: I/O

Posted: Fri May 11, 2007 6:11 pm
Riyad wrote:what is ur output for

Code: Select all

``````10 4 10
``````
i get

Code: Select all

``````1
2
3
4
``````
is it right????
Nope. 10 4 10 is not a valid input. Try 10 4 6. You should get the output you have posted.

Posted: Fri Jun 29, 2007 10:11 am
Jan ,

I am confused with ur output for the input : 61 8 52

1
1
1
1
1
2
26
28

but i got same as Riyad bhai :

1
1
1
1
1
1
52
3

i could print the total sequences :

1 -> 1 1 1 1 1 1 1 54
2 -> 1 1 1 1 1 1 2 53
3 -> 1 1 1 1 1 1 3 52
4 -> 1 1 1 1 1 1 4 51
5 -> 1 1 1 1 1 1 5 50
6 -> 1 1 1 1 1 1 6 49
7 -> 1 1 1 1 1 1 7 48
8 -> 1 1 1 1 1 1 8 47
9 -> 1 1 1 1 1 1 9 46
10 -> 1 1 1 1 1 1 10 45
11 -> 1 1 1 1 1 1 11 44
12 -> 1 1 1 1 1 1 12 43
13 -> 1 1 1 1 1 1 13 42
14 -> 1 1 1 1 1 1 14 41
15 -> 1 1 1 1 1 1 15 40
16 -> 1 1 1 1 1 1 16 39
17 -> 1 1 1 1 1 1 17 38
18 -> 1 1 1 1 1 1 18 37
19 -> 1 1 1 1 1 1 19 36
20 -> 1 1 1 1 1 1 20 35
21 -> 1 1 1 1 1 1 21 34
22 -> 1 1 1 1 1 1 22 33
23 -> 1 1 1 1 1 1 23 32
24 -> 1 1 1 1 1 1 24 31
25 -> 1 1 1 1 1 1 25 30
26 -> 1 1 1 1 1 1 26 29
27 -> 1 1 1 1 1 1 27 28
28 -> 1 1 1 1 1 1 28 27
29 -> 1 1 1 1 1 1 29 26
30 -> 1 1 1 1 1 1 30 25
31 -> 1 1 1 1 1 1 31 24
32 -> 1 1 1 1 1 1 32 23
33 -> 1 1 1 1 1 1 33 22
34 -> 1 1 1 1 1 1 34 21
35 -> 1 1 1 1 1 1 35 20
36 -> 1 1 1 1 1 1 36 19
37 -> 1 1 1 1 1 1 37 18
38 -> 1 1 1 1 1 1 38 17
39 -> 1 1 1 1 1 1 39 16
40 -> 1 1 1 1 1 1 40 15
41 -> 1 1 1 1 1 1 41 14
42 -> 1 1 1 1 1 1 42 13
43 -> 1 1 1 1 1 1 43 12
44 -> 1 1 1 1 1 1 44 11
45 -> 1 1 1 1 1 1 45 10
46 -> 1 1 1 1 1 1 46 9
47 -> 1 1 1 1 1 1 47 8
48 -> 1 1 1 1 1 1 48 7
49 -> 1 1 1 1 1 1 49 6
50 -> 1 1 1 1 1 1 50 5
51 -> 1 1 1 1 1 1 51 4
52 -> 1 1 1 1 1 1 52 3 -> (my output)

is the ordered sequence right ? or somethng is wrong there ??

Posted: Fri Jun 29, 2007 11:55 am
A partition of a positive integer number m into n elements (n ≤ m) is a sequence of positive numbers a1,...,an such that a1+...+an = m and a1 ≤ a2 ≤ ... ≤ an.
Check line 28

Code: Select all

``28 -> 1 1 1 1 1 1 28 27``
'a1 ≤ a2 ≤ ... ≤ an' but 28>27. So, it's not a valid configuration.

Hope these help.

Posted: Sat Jun 30, 2007 1:50 pm
got u .

thanks yaar . i am getting bored of these sorts of silly mistakes

Posted: Thu Nov 29, 2007 8:34 pm
CAN ANYBODY TELL ME WHAT IS THE MAXIMUM VALUE OF K?
I AM GETTING TLE