12801 - Grandpa Pepe's Pizza

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

Moderator: Board moderators

Post Reply
agesgi
New poster
Posts: 1
Joined: Sun Oct 19, 2014 11:14 pm

Re: 12801 - Grandpa Pepe's Pizza

Post by agesgi » Sun Oct 19, 2014 11:48 pm

I understand that the size of each sector must be S = C/N, and there is no problem with integer division because C is multiple of N. In my opinion, it should be possible to divide the pizza as described if and only if there are no Xi, 1<=i<=N, for which (Xi+1 - Xi) <= S and (Xi+2 - Xi) <= S (my implementation takes XN+1 = C+X1 and XN+2 = C+X2 in order to don't run out of bounds). What's wrong?

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

Re: 12801 - Grandpa Pepe's Pizza

Post by brianfry713 » Tue Oct 21, 2014 7:59 pm

My algorithm (AC in 0.023 seconds) is to test all S possible positions for the sectors to see if the olives are properly divided. For the first sample input of C = 12, N = 3, I would test these sectors:
0.5 - 4.5, 4.5 - 8.5, 8.5 - 0.5
1.5 - 5.5, 5.5 - 9.5, 9.5 - 1.5
2.5 - 6.5, 6.5 - 10.5, 10.5 - 2.5
3.5 - 7.5, 7.5 - 11.5, 11.5 - 3.5

But really I'd stop after the first entire pizza's tests passed. I also stop testing a pizza as soon as a sector fails.
I check that each pair of adjacent olives has a sector line between them.
Check input and AC output for thousands of problems on uDebug!

ssaha22
New poster
Posts: 5
Joined: Sat Dec 14, 2013 10:00 am

Re: 12801 - Grandpa Pepe's Pizza

Post by ssaha22 » Tue Aug 25, 2015 8:22 pm

Can you please give me some critical test cases...i have tried a lot of test cases in udebug but found nothing wrong in my output..

Post Reply

Return to “Volume 128 (12800-12899)”