10910 - Marks Distribution

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

Moderator: Board moderators

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

10910 - Marks Distribution

Post by ImLazy » Fri Oct 07, 2005 8:51 am

I generate all the decreasing sequences and multiply each of them with its number of permutations. But TLE.
Is there any faster algorithm?
I stay home. Don't call me out.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Fri Oct 07, 2005 12:58 pm

the algorithm you described as above will too slow for this problem;

A Simple DP will do enough.



Some key hint:

for example,
when N=3, T=34, P=9,
11 + 11 + 12 = 34
min(11, 11, 12) = 11 >= 9 = P
Do you see some relations between above and below?
2 + 2 + 3 = 7
min(2, 2, 3) = 2 >= 0
Sorry For My Poor English.. :)

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Fri Oct 07, 2005 2:04 pm

The above is 9 greater than the below. But I don't understand how to use this to solve the problem. :roll:
I stay home. Don't call me out.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Fri Oct 07, 2005 3:02 pm

min(a, b, c, ..., z) >= P

is same as :

a >= P, b >= P, c >= P, ...


So,

given statement, min(a1, a2, ..., aN) >= P means

a1 >= P, a2 >= P, a3 >= P, ..., aN >= P,
where a1 + a2 + a3 + ... + aN = T


Think a sequence {bn} = an - P
Then, the equation above is translated into these forms:

b1 >= 0, b2 >= 0, ..., bN >= 0
b1 + b2 + b3 + ... + bN = T - N * P

this form, which is easier than first, is a commonplace problem;
and it can be solved with simple DP.
Sorry For My Poor English.. :)

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Fri Oct 07, 2005 5:18 pm

:O, thanks. I'll try it. :D
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sun Oct 09, 2005 12:26 pm

No TLE now, but WA. Here is my output for small cases, are they right?
Input:

Code: Select all

210
1 1 1
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
2 2 1
2 3 1
2 4 1
2 5 1
2 6 1
2 7 1
2 8 1
2 9 1
2 10 1
2 11 1
2 12 1
2 13 1
2 14 1
2 15 1
2 16 1
2 17 1
2 18 1
2 19 1
2 20 1
2 21 1
2 22 1
3 3 1
3 4 1
3 5 1
3 6 1
3 7 1
3 8 1
3 9 1
3 10 1
3 11 1
3 12 1
3 13 1
3 14 1
3 15 1
3 16 1
3 17 1
3 18 1
3 19 1
3 20 1
3 21 1
3 22 1
3 23 1
4 4 1
4 5 1
4 6 1
4 7 1
4 8 1
4 9 1
4 10 1
4 11 1
4 12 1
4 13 1
4 14 1
4 15 1
4 16 1
4 17 1
4 18 1
4 19 1
4 20 1
4 21 1
4 22 1
4 23 1
4 24 1
5 5 1
5 6 1
5 7 1
5 8 1
5 9 1
5 10 1
5 11 1
5 12 1
5 13 1
5 14 1
5 15 1
5 16 1
5 17 1
5 18 1
5 19 1
5 20 1
5 21 1
5 22 1
5 23 1
5 24 1
5 25 1
6 6 1
6 7 1
6 8 1
6 9 1
6 10 1
6 11 1
6 12 1
6 13 1
6 14 1
6 15 1
6 16 1
6 17 1
6 18 1
6 19 1
6 20 1
6 21 1
6 22 1
6 23 1
6 24 1
6 25 1
6 26 1
7 7 1
7 8 1
7 9 1
7 10 1
7 11 1
7 12 1
7 13 1
7 14 1
7 15 1
7 16 1
7 17 1
7 18 1
7 19 1
7 20 1
7 21 1
7 22 1
7 23 1
7 24 1
7 25 1
7 26 1
7 27 1
8 8 1
8 9 1
8 10 1
8 11 1
8 12 1
8 13 1
8 14 1
8 15 1
8 16 1
8 17 1
8 18 1
8 19 1
8 20 1
8 21 1
8 22 1
8 23 1
8 24 1
8 25 1
8 26 1
8 27 1
8 28 1
9 9 1
9 10 1
9 11 1
9 12 1
9 13 1
9 14 1
9 15 1
9 16 1
9 17 1
9 18 1
9 19 1
9 20 1
9 21 1
9 22 1
9 23 1
9 24 1
9 25 1
9 26 1
9 27 1
9 28 1
9 29 1
10 10 1
10 11 1
10 12 1
10 13 1
10 14 1
10 15 1
10 16 1
10 17 1
10 18 1
10 19 1
10 20 1
10 21 1
10 22 1
10 23 1
10 24 1
10 25 1
10 26 1
10 27 1
10 28 1
10 29 1
10 30 1
Output:

Code: Select all

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
3
6
10
15
21
28
36
45
55
66
78
91
105
120
136
153
171
190
210
231
1
4
10
20
35
56
84
120
165
220
286
364
455
560
680
816
969
1140
1330
1540
1771
1
5
15
35
70
126
210
330
495
715
1001
1365
1820
2380
3060
3876
4845
5985
7315
8855
10626
1
6
21
56
126
252
462
792
1287
2002
3003
4368
6188
8568
11628
15504
20349
26334
33649
42504
53130
1
7
28
84
210
462
924
1716
3003
5005
8008
12376
18564
27132
38760
63273
89628
100947
134596
177100
230230
1
8
36
120
330
792
1716
3432
6435
11440
19448
31824
50388
77520
116280
242616
384582
346104
480700
657800
888030
1
9
45
165
495
1287
3003
6435
12870
24310
43758
75582
125970
203490
319770
823647
1469061
1120185
1635205
2351349
3334851
1
10
55
220
715
2002
5005
11440
24310
48620
92378
167960
293930
497420
817190
2478674
4921565
3510650
5489055
8365500
12559599
I stay home. Don't call me out.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Oct 09, 2005 12:55 pm

ImLazy: Some of your outputs are wrong. Here is my output:

Code: Select all

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
3
6
10
15
21
28
36
45
55
66
78
91
105
120
136
153
171
190
210
231
1
4
10
20
35
56
84
120
165
220
286
364
455
560
680
816
969
1140
1330
1540
1771
1
5
15
35
70
126
210
330
495
715
1001
1365
1820
2380
3060
3876
4845
5985
7315
8855
10626
1
6
21
56
126
252
462
792
1287
2002
3003
4368
6188
8568
11628
15504
20349
26334
33649
42504
53130
1
7
28
84
210
462
924
1716
3003
5005
8008
12376
18564
27132
38760
54264
74613
100947
134596
177100
230230
1
8
36
120
330
792
1716
3432
6435
11440
19448
31824
50388
77520
116280
170544
245157
346104
480700
657800
888030
1
9
45
165
495
1287
3003
6435
12870
24310
43758
75582
125970
203490
319770
490314
735471
1081575
1562275
2220075
3108105
1
10
55
220
715
2002
5005
11440
24310
48620
92378
167960
293930
497420
817190
1307504
2042975
3124550
4686825
6906900
10015005

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sun Oct 09, 2005 2:56 pm

I've found my bug and get AC. Thanks. :D
The bug is in the function of calculating the number of permutation & combination. In the above wrong output, my program calculates 14C6 as 12012, but it should be 3003.
I stay home. Don't call me out.

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Why WA??

Post by ranban282 » Thu Mar 01, 2007 2:41 pm

I have absolutely no idea why this gives WA. It passes the test cases given above. Can anybody give me test cases with solutions?

Code: Select all

Removed after AC
Last edited by ranban282 on Thu Mar 01, 2007 2:47 pm, edited 1 time in total.

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Problem description

Post by ranban282 » Thu Mar 01, 2007 2:47 pm

When I used int, it gave WA. When I used long long, I got AC

rohituberoi
New poster
Posts: 1
Joined: Sat Jun 09, 2007 12:38 pm

Runtime Error

Post by rohituberoi » Sun Jun 10, 2007 3:39 pm

Plzz help.......i don't know why i m getting runtime error in this code......It is working perfectly on my compliler......

#include<iostream>
using namespace std;
int main(){
long long int u,v,y;
long long int l,i,n,t,p,j,s,k;
cin>>l;
for(i=0;i<l;i++){
n=t=p=j=0;
cin>>n>>t>>p;
j=t-(n*p);
s=j+n-1;
if(n>1){
v=1;
for(k=1;k<=(n-1);k++){
v=v*s;
s--;
}
u=1;
for(k=1;k<=(n-1);k++){
u=u*k;
}
y=v/u;
cout<<y<<endl;
}
else if(n==1){
cout<<"1"<<endl;
}
}
return 0;
}

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jun 10, 2007 8:56 pm

I don't know whether this is the problem but you might use "long long" instead of "long long int".

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Jun 10, 2007 9:06 pm

'long long' and 'long long int' are the same thing.

Runtime error is in "y=v/u;"
He tries to put (N-1)! into u, and that overflows, and results in u=0.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jun 10, 2007 9:14 pm

ic... :oops: Thx for the correction :wink:

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm

Post by lucky16g » Tue Jul 10, 2007 9:44 pm

why my code got wrong anser

can anyone tell me what input will let it wrong

is it over flower for long long int ?

thx before

Code: Select all

i have got ac

thanks for mf's help

Last edited by lucky16g on Wed Jul 11, 2007 11:50 am, edited 1 time in total.

Post Reply

Return to “Volume 109 (10900-10999)”