From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details
This question is the first question(Carried 20 marks out of 100) for the Round 2 of 2013 hacker cup.
Problem Statement
“Happy birthday to you… Happy birthday to you… Happy birthday to Grovyle… Happy birthday to you…”
Today is Grovyle’s birthday and he is going to invite his friends to his birthday party. To have an awesome party, each of the attendants should get one piece of cake. Your job is to help Grovyle invite as many friends as you can.
However, Grovyle’s parents are very mean, and make him use the following rules when cutting his cake:
- There is only ONE cylindrical cake.
- Grovyle cuts the cake N times, each cut being perpendicular to the surface of the cake.
- The i-th cut is a broken line with a[i] vertices.
- The knife is only allowed to intersect the edge of the cylindrical cake at the start and end of the cut.What is the maximum number of pieces Grovyle could get?
Input
The first line contains an integer T, T ≤ 50, indicating the number of test cases. Each test case begins with an integer N, 1 ≤ N ≤ 100, followed by Nintegers a[i], 0 ≤ a[i] < 400, which indicate the number of vertices in the i-th cut.
Output
For each test case, output “Case #i: ” followed by the maximum number of pieces of cake Grovyle can cut.
Example for test case 1
Example for test case 2
Example for test case 3
Example input
5 3 0 0 0 2 1 1 2 1 2 4 0 0 0 1 4 2 2 2 2
Example output
Case #1: 7 Case #2: 7 Case #3: 10 Case #4: 14 Case #5: 63
Solution
You can derive this formula:
f(n) = f(n-1) + 1 + totalLines*(m+1) + m*(m-1)/2;
where
m = number of vertices for nth line.
totalLines are the number of lines before considering the new line(including lines due to vertices, so for m =1 , two lines are counted).
Explanation:
basically while drawing any new line we can say the number of pieces will increase by totalLines +1. for lines with vertices you have to keep increasing the previous lines it can cut.
here is the java code:
import java.util.ArrayList;
public class CakeCutting {
int getMaxPeicesCount(ArrayList<Integer> input){
int[] f = new int[input.size()+1];
f[0] = 1;
int totalLines = 0;
int index = 0;
for(int vertices: input){
index++;
f[index] = f[index-1] + getCountsDueToNextLines(totalLines, vertices);
totalLines = totalLines+vertices+1;
}
System.out.println(f[index]);
return f[index];
}
int getCountsDueToNextLines(int curentLines, int m){
return 1+ curentLines*(m+1) + m*(m-1)/2;
}
