## 10213 - How Many Pieces of Land ?

**Moderator:** Board moderators

- lord_burgos
- New poster
**Posts:**43**Joined:**Mon Oct 13, 2003 4:54 pm**Location:**Mexico-
**Contact:**

### 10213 .- Why Wrong Answer?

Why Wrong Answer?

(n^4-6n^3+23n^2-18^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^4-6n^3+23n^2-18^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]

- lord_burgos
- New poster
**Posts:**43**Joined:**Mon Oct 13, 2003 4:54 pm**Location:**Mexico-
**Contact:**

### :) 10213

This is:

(n^4-6n^3+23n^2-18^n+24)/24

(n^4-6n^3+23n^2-18^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 * (N-1) * (N*N-5*N+18) / 24 ) + 1
```

value

Code: Select all

`N * (N-1) * (N*N-5*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.

- little joey
- 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.

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.

- little joey
- 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

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 (N-1) 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, (N-1), (N-2) or (N-3) 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*(N-1)/2 + N*(N-1)*(N-2)*(N-3)/24 +1`

The same thing goes for the second term:

since two of N, (N-1), (N-2) or (N-3) 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.

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.

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.