10213  How Many Pieces of Land ?
Moderator: Board moderators

 New poster
 Posts: 43
 Joined: Mon Oct 13, 2003 4:54 pm
 Location: Mexico
 Contact:
10213 . Why Wrong Answer?
Why Wrong Answer?
(n^46n^3+23n^218^n+24)/24
[c]
# include <stdio.h>
main(){
double x,y,z;
int n,i;
scanf("%d",&n);
for(i = 0; i<n;i++){
scanf("%lf",&x);
y =(((x*x*x*x)(x*x*x*6) + (23*x*x)  (18*x) + 24))/24;
printf("%.0lf\n",y);
}
return 0;
}
[/c]
(n^46n^3+23n^218^n+24)/24
[c]
# include <stdio.h>
main(){
double x,y,z;
int n,i;
scanf("%d",&n);
for(i = 0; i<n;i++){
scanf("%lf",&x);
y =(((x*x*x*x)(x*x*x*6) + (23*x*x)  (18*x) + 24))/24;
printf("%.0lf\n",y);
}
return 0;
}
[/c]

 New poster
 Posts: 43
 Joined: Mon Oct 13, 2003 4:54 pm
 Location: Mexico
 Contact:
:) 10213
This is:
(n^46n^3+23n^218^n+24)/24
(n^46n^3+23n^218^n+24)/24
10213 Combinatorics Approach
There is a combinatorics explaination to the formula, it is actually 1 + (n choose 2) + (n choose 4).
1 is the original circle.
(n choose 2) is the number of lines we are drawing, by choosing the 2 endpoints.
(n choose 4) is the number of intersections inside the circle, by choosing 4 points ABCD(in clockwise order) on the circle, then line AC and BD forms a unique intersection.
Basically each time we draw a line on the circle, we are adding (1+m) to the number of pieces, where m is the number of intersections on the new line.
1 is the original circle.
(n choose 2) is the number of lines we are drawing, by choosing the 2 endpoints.
(n choose 4) is the number of intersections inside the circle, by choosing 4 points ABCD(in clockwise order) on the circle, then line AC and BD forms a unique intersection.
Basically each time we draw a line on the circle, we are adding (1+m) to the number of pieces, where m is the number of intersections on the new line.
wa.. don't know why
I am also using the formula 1 + nc2 + nc4 but getting WA.
I also match all the samples from the board.
Can someone confirm the following I/O
Input
Output
BTW : I have used BIGNUM.
I also match all the samples from the board.
Can someone confirm the following I/O
Input
Code: Select all
10
0
1
54
12575
312544
110010
1112143
1000000000
2000000000
1234567890
Code: Select all
1
1
317683
1041390301833851
397580508821554746073
6102302473357942756
63742478475498293889839
41666666416666667624999999250000001
666666664666666670499999998500000001
96794050695522260242568330014498846
Oh, sorry for that stupid remark of mine.
I see now, 10 is just the number of test cases to follow.
By the way I also have a BigInt custom class but currently
it does support division. And so I can not use it.
I mean that as the formula is :
we should be able to divide by 24 once we generate the BigInt
value
Should I necessarily implement division in my BigInt or is
that some tricky workaround letting me get away without
doing division of 24 at the end of the computation ?
What do you think about that ?
I see now, 10 is just the number of test cases to follow.
By the way I also have a BigInt custom class but currently
it does support division. And so I can not use it.
I mean that as the formula is :
Code: Select all
F(N) = ( N * (N1) * (N*N5*N+18) / 24 ) + 1
value
Code: Select all
N * (N1) * (N*N5*N+18)
Should I necessarily implement division in my BigInt or is
that some tricky workaround letting me get away without
doing division of 24 at the end of the computation ?
What do you think about that ?
Last edited by Sedefcho on Sun Mar 13, 2005 7:42 pm, edited 1 time in total.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
You are getting the smilies because you are typing an '8' followed by a ')', which is interpreted as
There are several ways around this:
 allways place code within code tags:will suppres the smilies (and is much better to read)
 disable smilies for the message: you can check this when writing it.
About your question:
You can't get around doing division on bignums for this question (AFAIK), but since you're only dividing by small numbers, it isn't hard to implement long division (like you learned at school).
If your bigint is stored as a string of digits, you can split the division by 24 into a division by 3 followed by a division by 8. Then you only need to divide the bignum by a single digit, which is very easy to implement.
There are several ways around this:
 allways place code within code tags:
Code: Select all
8)
 disable smilies for the message: you can check this when writing it.
About your question:
You can't get around doing division on bignums for this question (AFAIK), but since you're only dividing by small numbers, it isn't hard to implement long division (like you learned at school).
If your bigint is stored as a string of digits, you can split the division by 24 into a division by 3 followed by a division by 8. Then you only need to divide the bignum by a single digit, which is very easy to implement.
I don't want to implement a method like
divideBy24
I will either have a general method divide(BigInt, int) or
won't have one at all.
That is what I mean.
By workaround I mean doing the multiplications in a clever
way so that I don't need to divide by 24 at the end.
That is what I mean.
And not implementing an easy or tricky or whatever method
divideBy24.
divideBy24
I will either have a general method divide(BigInt, int) or
won't have one at all.
That is what I mean.
By workaround I mean doing the multiplications in a clever
way so that I don't need to divide by 24 at the end.
That is what I mean.
And not implementing an easy or tricky or whatever method
divideBy24.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hmm. Suit yourself.
What I wanted to say is that divide(BigInt, int) isn't hard to implement if your BigInt is based on an array of ints. But if it's based on an array of digits, there would be an easy trick that would help you solve this particular problem. But of course you're free to implement and solve any problem you like.
Did you discover the formula yourself? Or did you just copy it from the previous posts. If you did it yourself, you might have discovered that it is equivalent to:
Since either N or (N1) is even, you can divide out 2 in the first term before doing the multiplication.
The same thing goes for the second term:
since two of N, (N1), (N2) or (N3) are even, one of them is divisible by four and the other is divisible by 2. Also (at least) one of the four numbers is divisible by three.
So you can divide out 4, 2 and 3 before you do the multiplication.
And then there's no need for division on BigNums.
What I wanted to say is that divide(BigInt, int) isn't hard to implement if your BigInt is based on an array of ints. But if it's based on an array of digits, there would be an easy trick that would help you solve this particular problem. But of course you're free to implement and solve any problem you like.
Did you discover the formula yourself? Or did you just copy it from the previous posts. If you did it yourself, you might have discovered that it is equivalent to:
Code: Select all
F(N) = N*(N1)/2 + N*(N1)*(N2)*(N3)/24 +1
The same thing goes for the second term:
since two of N, (N1), (N2) or (N3) are even, one of them is divisible by four and the other is divisible by 2. Also (at least) one of the four numbers is divisible by three.
So you can divide out 4, 2 and 3 before you do the multiplication.
And then there's no need for division on BigNums.
Of course there's no need of division of BigNums.
I mean we don't need a method like
divide(BigNum, BigNum).
But still we need a method divide(BigNum, int). It seems we can not
avoid that, right ?
And yes, my implementation of BigNum has an internal
integer array, in which each integer is a decimal digit.
OK, I continue working on this problem. I will see how it
goes with implementing the method
divide(BigNum, int) .
Thank you for the comments, Little Joey.
I mean we don't need a method like
divide(BigNum, BigNum).
But still we need a method divide(BigNum, int). It seems we can not
avoid that, right ?
And yes, my implementation of BigNum has an internal
integer array, in which each integer is a decimal digit.
OK, I continue working on this problem. I will see how it
goes with implementing the method
divide(BigNum, int) .
Thank you for the comments, Little Joey.
It's only now that I got what you mean!
We should do the division before even forming our BigNum
instances. I see. I will try this.
Currently I am happy anyway as I managed to get my
JAVA program receive "TLE" from the Online Judge and not
WA, which is quite OK.
My BigNum class gets better and better which will be
useful for other problems too.
Thanks.
We should do the division before even forming our BigNum
instances. I see. I will try this.
Currently I am happy anyway as I managed to get my
JAVA program receive "TLE" from the Online Judge and not
WA, which is quite OK.
My BigNum class gets better and better which will be
useful for other problems too.
Thanks.