You are not logged in. Please login at www.codechef.com to post your questions!

×

Getting Wrong answer in Problem name Pizza ?

1
1

I am trying to solve this problem http://www.codechef.com/problems/CM1404 but i am getting wrong answer. can anyone tell me where i am wrong ?

My algorithm

  1. I am calculating the maximum number of piece can be cut using N line.
  2. To maximize this we have to divide N into two equal parts if N is even, else floor(N/2) and ceil(N/2).
  3. After that checking whether the given number fall into that range or not. Maximum number piece can be done = floor(N/2) * ceil(N/2)
  4. If number is perfect square then return (sqrt(n)-1)*2;
  5. Else, check whether the number fall into lower range o higher.

(i). If N > floor(N/2)ceil(N/2) then return ((ceil(sqrt(N/2)))-1)2) ;

(ii) Else return ((floor(sqrt(N/2)))-1)*2)+1;

here is the link of my code https://gist.github.com/Shravan40/cc9c509d325c0c959df6

asked 25 Oct '14, 05:20

shravan40's gravatar image

2★shravan40
2112
accept rate: 0%


I honestly don't know why you have to divide N to 2 or even divide them. N means the sliced pizza already. What you've been asked in the problem is minimum number of SLICES for you to get N or greater than that. Well, to solve it, you can picture out the pizza and slice once, twice, thrice and so on. alt text

As you can see, the best way to cut the pizza into its maximum, is to cut it straight through ALL the slices already. As shown above in the picture, you can get 2 pieces with 1 slice, 4 pieces with 2 slices, 7 pieces with 3 slices and 11 pieces with 4 slices. The problem didn't state to cut the pizza equally so the cutting style should be OK.

The maximum number of pieces cut is also a sequence called "lazy caterer's sequence". You can read about it here: link text

Then, to solve the problem, you just have to check the range in which N first appeared. :D

Happy coding~

link

answered 25 Oct '14, 06:20

stheitive16_'s gravatar image

4★stheitive16_
14915
accept rate: 50%

You're method is a bit wrong the pieces need not to be equal. for ex if n=10 your code will give output 5 but 10 piecesalt text can be obtained in 4 proper cuts.

link

answered 25 Oct '14, 06:11

anichavan20's gravatar image

2★anichavan20
9314
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,901
×1,650
×1,056

question asked: 25 Oct '14, 05:20

question was seen: 5,157 times

last updated: 25 Oct '14, 06:20