10581 - Partitioning for fun and profit

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

[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

[windows2k]

I don't know how to solve the problem.
Could someone give me some hints?
Thx

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

[Jan]

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.

[chuzpa]

They did help, thanks a lot ! I've got Acc. I was misunderstanding the problem.

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

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

[Jan]

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.

[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

Code: Select all

10 4 10

i get

Code: Select all

1
2
3
4

is it right????

[Jan]

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.

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

[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

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.

[Kallol]

got u .

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

[SHAHADAT]

CAN ANYBODY TELL ME WHAT IS THE MAXIMUM VALUE OF K?
I AM GETTING TLE