12801 - Grandpa Pepe's Pizza
Moderator: Board moderators
Re: 12801 - Grandpa Pepe's Pizza
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?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12801 - Grandpa Pepe's Pizza
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.
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!
Re: 12801 - Grandpa Pepe's Pizza
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..