## 10079 - Pizza Cutting

Moderator: Board moderators

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
There is no diffrence between 0.500000000000 and 0.499999999999 but when you want to cast it to int the problems arises. Moreover the final results may become rational number so avoid this methods in the integer computation.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### 10079 Pizza Cutting - I want to know the proof.

It's a very easy problem, and I solved it within 10 min.
In my intuition, I can see that answer makes following arithmetic progression
a(n) = 1 + (n(n+1))/2;
However, I want to know why pizza cutting makes this expression.
Anyone tell me the proof of this expression?
I love Problem Solving!!!   tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
I don't know if it really is a proof, but when I coded my first version of this problem I made an iterative solution, when at each step I just added the number of pieces for the best possible cut.

Drawing it on the paper, I saw that I could ever cut all the previous lines with a single line, thus creating the sequence

1+2+3+4+...

It ran for almost 25 seconds, so after that i figured out that it was actually an arithmetic progression, and then just used this formula.
Thiago Sonego Goulart - UFMG/Brazil

mahfuz05
New poster
Posts: 3
Joined: Fri Mar 30, 2007 6:26 am

### 10079_WA

thanks ........

code removed............***********.........
Last edited by mahfuz05 on Sun Apr 15, 2007 3:34 pm, edited 1 time in total.

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

And search before opening a new thread.
Thiago Sonego Goulart - UFMG/Brazil

Freyr
New poster
Posts: 5
Joined: Sun Apr 22, 2007 8:47 pm
Contact:
Well, the way I approached it was with common differences and regression.

Obviously, if you have zero cuts in the pizza, you'll have 1 slice. If you have one slice you'll have two pieces. It's given that you'll have 7 pieces with 3 slices, and you should also know that two slices would equate to four pieces.

(0,1)
(1,2)
(2,4)
(3,7)

Code: Select all

``````       1 - 2 - 4 - 7
D1:       1   2   3
D2:         1   1``````

Using y = ax^2+bx+c (and knowing that 1 is your c value, as (0,1))

2 = a(1)^2 + b(1) + 1
1 = a + b

4 = a(2)^2+b(2) + 1
3 = 4a + 2b

Then eliminate:
2*2 = (a + b)*2
- 3 = 4a + 2b
1 = 2a
a = 1/2

1 = a + b
1 = 1/2 + b
1/2 = b

Thusly:
y = ax^2+bx+c
y = (x^2)/2+(x/2)+1

Or

y = ((x^2+x)/2)+1

That's how I looked at it anyways.

New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran
The proof is by mathematical induction:

f(n) = the maximum number of pieces with n cuts

Proof: suppose we know f(n - 1) now consider f(n):
if we remove the nth cut we know the answer by the hypothesis. The question is how to add the nth cut and gain the maximum number of pieces. It's obvious that the nth cut not be parallel with any cuts and no three cuts intersect each other in one point (We say these cuts (lines) are in General Position). So the nth cut must intersect with all n - 1 cuts (with above conditions) then n new pieces we have:

f(n) = f(n - 1) + n
f(0) = 1

if we solve above recurrence we have f(n) = 1 + n * (n +1) / 2

Hope it's useful.

mintae71
New poster
Posts: 18
Joined: Tue Jan 19, 2010 10:50 am

### Re: 10079

Red Scorpion wrote: Hi, I am trying to solve problem 10079, and got failed.

I use this method :

for n=an, MAX = bn
n=0 , MAX = 0
n=1, MAX = 2
n=2, MAX = 4 (2 + 2 )
n=3, MAX = 7 (4 + 3 )
n=4, MAX = 11 (7 + 4)
n=5, MAX=16 (11 + 5)
n=6, MAX=22 (b(n-1) + an)
n=7, MAX=29
n=8, MAX=37
n=9, MAX=46
n=10, MAX=56

... and so forth (and the number will be very huge)

If Anyone have time, Please tell me what wrong with this method ?

Thanks.
First I'm sorry for my bad english.. Please forgive me because I am a korean and i'm an Elementry School student.....

eh?? I made it like you and I got AC in 1.4..... did you used for? that will make better mintae71
New poster
Posts: 18
Joined: Tue Jan 19, 2010 10:50 am

### Re: 10079 Pizza Cutting - I want to know the proof.

soyoja wrote:It's a very easy problem, and I solved it within 10 min.
In my intuition, I can see that answer makes following arithmetic progression
a(n) = 1 + (n(n+1))/2;
However, I want to know why pizza cutting makes this expression.
Anyone tell me the proof of this expression?
I am sorry but I think your code is wrong.
I did as same as you but I got WA.               New poster
Posts: 1
Joined: Mon Jul 12, 2010 6:02 am

### Re: 10079 - Pizza Cutting

mintae71 wrote:
soyoja wrote:It's a very easy problem, and I solved it within 10 min.
In my intuition, I can see that answer makes following arithmetic progression
a(n) = 1 + (n(n+1))/2;
However, I want to know why pizza cutting makes this expression.
Anyone tell me the proof of this expression?
I am sorry but I think your code is wrong.
I did as same as you but I got WA.               No, Soyoja algorithm is right. I've tried it and it's worked. It's just need some carefully arithmetic for doing so.

But for the prove I can't give a thing why it's worked sorry.

rein08
New poster
Posts: 3
Joined: Mon Jul 19, 2010 2:25 pm

### Re: 10079 - Pizza Cutting

Trying to sove the problem.
I tried five times.
But still got WA.  dtopic
New poster
Posts: 1
Joined: Tue Nov 16, 2010 10:12 pm

### Re: 10079 - Pizza Cutting

a
Last edited by dtopic on Sat Feb 26, 2011 7:32 pm, edited 1 time in total.

liya
New poster
Posts: 10
Joined: Fri Jan 23, 2015 2:36 pm

### WA-10079

it's gettung WA...???

Code: Select all

``````#include<stdio.h>
int main()
{
long long int n;
for( ; ; )
{
if(n<0)
{
break;
}
scanf("%lld",&n);
printf("%lld\n",(n*(n+1)/2)+1);
}
return 0;
}``````
Last edited by brianfry713 on Tue Jan 27, 2015 9:26 pm, edited 1 time in total.

liya
New poster
Posts: 10
Joined: Fri Jan 23, 2015 2:36 pm

### Re: 10079 - Pizza Cutting

WA....

Code: Select all

``````#include<stdio.h>
int main()
{
long long int n;
for( ; ; )
{
if(n<0)
{
break;
}
scanf("%lld",&n);
printf("%lld\n",(n*(n+1)/2)+1);
}
return 0;
}``````
Last edited by brianfry713 on Tue Jan 27, 2015 9:26 pm, edited 1 time in total.