15 August 2012

Uva 10079 - Pizza Cutting

Solution :-

#include <stdio.h>
int main()
      long long n;
      while(scanf("%lld", &n)==1)
             if(n<0) break;

             printf("%lld\n", ((n*(n+1))/2)+1);

       return 0;


Nishtha Goel said...

i can't understand the logic behind it...can u explain further

Shipu Ahamed said...

For each cut, you are guaranteed to be able to intersect all the previous cuts. If you sketch out the first few cuts, you'll see that:

p(n) = p(n-1) + (n-1) + 1

that is, for any given pizza with n cuts, the maximum number of slices is equal to a pizza with n-1 cuts, plus one slice for every cut that is intersected by the nth cut ( we know that to be n-1 ), plus 1.

From this, you get a recurrence that can be solved to give a constant time function:

p(n) = p(n-1) + n
p(n) = (n*(n+1))/2 + 1

Post a Comment