## 10581 - Partitioning for fun and profit

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

Moderator: Board moderators

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

### 10581 - Partitioning for fun and profit

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
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### 10581

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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### thanks!

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

Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### some more test cases

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....
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
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 ;
}
``````
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### I/O

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????
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

### Re: I/O

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.
Ami ekhono shopno dekhi...
HomePage

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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 ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
got u .

thanks yaar . i am getting bored of these sorts of silly mistakes
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh
CAN ANYBODY TELL ME WHAT IS THE MAXIMUM VALUE OF K?
I AM GETTING TLE
-------------- ASHA TAR AKMATRO VHELA.