Page 1 of 2
10581 - Partitioning for fun and profit
Posted: Tue Dec 23, 2003 9:58 am
by sunhong
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
by gawry
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
by windows2k
I don't know how to solve the problem.
Could someone give me some hints?
Thx
Posted: Fri May 07, 2004 6:21 am
by wyvmak
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
by Jan
Some cases...
Input:
Code: Select all
5
220 10 50
220 2 31
12 3 4
19 5 3
35 11 11
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
by chuzpa
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
by Riyad
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
by Riyad
can't get AC still
can anyone please help. below is my code
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
by Jan
Try the cases.
Input:
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
by Riyad
but i get this output for your input. could you tell what am i doing wrong?please help.....
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
i get
is it right????
Re: I/O
Posted: Fri May 11, 2007 6:11 pm
by Jan
Riyad wrote:what is ur output for
i get
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
by Kallol
Jan ,
I am confused with ur output for the input : 61 8 52
Your output :
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
by Jan
Read the description again.
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
'a1 ≤ a2 ≤ ... ≤ an' but 28>27. So, it's not a valid configuration.
Hope these help.
Posted: Sat Jun 30, 2007 1:50 pm
by Kallol
got u .
thanks yaar . i am getting bored of these sorts of silly mistakes
Posted: Thu Nov 29, 2007 8:34 pm
by SHAHADAT
CAN ANYBODY TELL ME WHAT IS THE MAXIMUM VALUE OF K?
I AM GETTING TLE