Page 3 of 3

Posted: Sun Aug 13, 2006 8:29 pm
by 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.

10079 Pizza Cutting - I want to know the proof.

Posted: Wed Feb 14, 2007 9:52 am
by 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?

Posted: Wed Feb 14, 2007 6:05 pm
by 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.

10079_WA

Posted: Fri Mar 30, 2007 6:48 am
by mahfuz05
thanks ........

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

Posted: Sat Mar 31, 2007 5:29 am
by tgoulart
Try your program with 1500000.

And search before opening a new thread.

Posted: Sun Apr 22, 2007 8:59 pm
by 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.

Posted: Wed Jun 20, 2007 11:18 pm
by 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.

Re: 10079

Posted: Thu Jan 21, 2010 11:11 am
by mintae71
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 :)

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

Posted: Thu Jan 21, 2010 12:47 pm
by mintae71
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

Re: 10079 - Pizza Cutting

Posted: Tue Jul 13, 2010 6:31 am
by adinata
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.

Re: 10079 - Pizza Cutting

Posted: Thu Jul 22, 2010 1:50 pm
by rein08
Trying to sove the problem.
I tried five times.
But still got WA. :( :(

Re: 10079 - Pizza Cutting

Posted: Tue Nov 16, 2010 10:18 pm
by dtopic
a

WA-10079

Posted: Tue Jan 27, 2015 5:47 pm
by 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;
}

Re: 10079 - Pizza Cutting

Posted: Tue Jan 27, 2015 8:42 pm
by 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;
}

Re: 10079 - Pizza Cutting

Posted: Tue Jan 27, 2015 9:33 pm
by brianfry713
Don't double post.
Initialize n.