10079 - Pizza Cutting

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

Moderator: Board moderators

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Sun Aug 13, 2006 8:29 pm

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.

Post by soyoja » Wed Feb 14, 2007 9:52 am

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

Post by tgoulart » Wed Feb 14, 2007 6:05 pm

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

Post by mahfuz05 » Fri Mar 30, 2007 6:48 am

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

Post by tgoulart » Sat Mar 31, 2007 5:29 am

Try your program with 1500000.

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:

Post by Freyr » Sun Apr 22, 2007 8:59 pm

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
Therefore: Quadratic.

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.

User avatar
saman_saadi
New poster
Posts: 31
Joined: Sun Feb 25, 2007 6:33 pm
Location: Tehran

Post by saman_saadi » Wed Jun 20, 2007 11:18 pm

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

Post by mintae71 » Thu Jan 21, 2010 11:11 am

Red Scorpion wrote::P
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.

Post by mintae71 » Thu Jan 21, 2010 12:47 pm

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.
I'm so sorry about my bad english. Thank you.
:D :D :D :D :D :D :D :D :D :D :D :D :D :D :D

adinata
New poster
Posts: 1
Joined: Mon Jul 12, 2010 6:02 am

Re: 10079 - Pizza Cutting

Post by adinata » Tue Jul 13, 2010 6:31 am

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.
I'm so sorry about my bad english. Thank you.
:D :D :D :D :D :D :D :D :D :D :D :D :D :D :D
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

Post by rein08 » Thu Jul 22, 2010 1:50 pm

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

Post by dtopic » Tue Nov 16, 2010 10:18 pm

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

Post by liya » Tue Jan 27, 2015 5:47 pm

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.
Reason: Added code blocks

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

Re: 10079 - Pizza Cutting

Post by liya » Tue Jan 27, 2015 8:42 pm

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.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10079 - Pizza Cutting

Post by brianfry713 » Tue Jan 27, 2015 9:33 pm

Don't double post.
Initialize n.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”