Costly Binary Search (Large)
Time limit60sMemory limit1536 MB
Given the cost of comparing against each array position, find the smallest worst-case total cost of an adaptive binary search for the insertion point.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Divide and conquer, Greedy
- Solved
- No attempts yet
Problem
You want to insert one new object into a sorted array, and you find the insertion position by binary search. Comparing the new object with an object of the array answers either "greater" or "less". "Greater" means the new object goes to the right of the compared object, and "less" means it goes to the left. A comparison never answers "equal" in this problem.
The answers never contradict each other. If the new object is greater than some object of the array, it is also greater than every object to the left of that one. If it is less than some object, it is also less than every object to the right of that one. For an array of elements there are possible insertion positions.
Comparisons do not all cost the same. Comparing the new object with the -th object of the array costs , an integer between 1 and 9.
You may pick the next object to compare after seeing the answers so far. Play a strategy that minimizes the total cost in the worst case, and report that worst-case total cost.
Input
The first line has the number of test cases . Each of the next lines holds the comparison costs of one test case as a sequence of digits written with no spaces. The length of the array is the length of that sequence.
Limits
- Every digit is between 1 and 9.
- There are no spaces between the digits on one line.
Output
For each test case, print one line Case #x: y, where is the test case number starting from 1 and is the worst-case total cost of the binary search.