10079 - Pizza Cutting

[Moha]

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]

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?

[tgoulart]

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.

[mahfuz05]

thanks ........

code removed............***********.........

[tgoulart]

Try your program with 1500000.

And search before opening a new thread.

[Freyr]

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.

[saman_saadi]

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]

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]

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.

[adinata]

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.

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]

Trying to sove the problem.
I tried five times.
But still got WA.

[dtopic]

a

[liya]

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;
}

[liya]

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;
}

[brianfry713]

Don't double post.
Initialize n.