Problem:
TopCoder Problem Statement - FryingHamburgers |
Single Round Match 159 Round 1 - Division I, Level One |
Overview:
Optimize the time it takes to cook a number of hamburgers given the number of burgers, and the size of a grill.
Java Source:
01: public class FryingHamburgers { 02: 03: private static final int MINS_PER_SIDE = 5; 04: private static final int MINS_PER_BURGER = 2 * MINS_PER_SIDE; 05: 06: public int howLong(int panSize, int hamburgers) { 07: 08: // If there are no hamburgers, it takes no time. 09: if (hamburgers == 0) return 0; 10: 11: // All the hamburgers can fit on one pan. 12: if (hamburgers <= panSize) return MINS_PER_BURGER; 13: 14: // The hamburgers divide evenly by panSize 15: if ((hamburgers % panSize) == 0) { 16: return (hamburgers / panSize) * MINS_PER_BURGER; 17: } 18: 19: /* 20: * If the remainder is <= panSize, we can use the trick described in 21: * the tests to save the cooking time of one side. 22: */ 23: if ((hamburgers % panSize) <= (panSize / 2)) { 24: return ((hamburgers / panSize + 1) * MINS_PER_BURGER) 25: - MINS_PER_SIDE; 26: } 27: 28: // Worst case, we just cook one side, then the other. 29: return (hamburgers / panSize + 1) * MINS_PER_BURGER; 30: 31: } 32: }
Notes:
This is the sort of nasty little problem that you might encounter during a programming interview. I've seen it asked with 3 burgers and a grill that holds two. That's easy enough to explain. Coding it up for the general case is quite a bit trickier. It's also very likely that you'll pass the given examples, and then fail during the challenge phase, since it's so easy to make a mistake in the logic that goes undetected.
There are essentially five cases to think about:
- hamburgers == 0. This is trivial, if there are no burgers, it takes no time
- hamburgers <= panSize. Again, pretty trivial. We can put all burgers on the pan at once. Flip them after 5 minutes, and they'll be done in 10. There's no way to shorten this.
- (hamburgers % panSize) == 0. The number of burgers divides evenly by the panSize. Similar to the above case, but we repeat the process until all hamburgers are gone.
- Here's out special case. If the remainder of the burgers when divided by the pan size is <= half the pans size: (hamburgers % panSize) <= (panSize / 2), then we can use a trick. We flip over half the burgers, set the other half of the burgers aside, and fill the pan with a new set of burgers. This can save us the time it takes to cook one side of a burgers.
- Failing the above cases, we fall back to the number of burgers divided by the size of the pan times how long it takes to cook a burger.
No comments:
Post a Comment