Howdy! Some hours until codejam starts again and I’ve decided to take some rust off. 🙂
This problem is called Hedgemony, quite simple:
Lord Cohen is a baron with the best-looking hedge in the country. His award-winning hedge consists of N bushes planted side by side in a straight line. The bushes are numbered left to right from 1 to N. The baron’s neighbours all cut their own hedges so that all of their bushes have the same height. But Lord Cohen has a secret key to his landscaping success. His gardener follows a special rule when trimming the hedge, which is why the baron’s hedge is always in its award-winning condition.
The rule is — to start on the left at bush #2 and move to the right. The gardener cuts the top of each bush to make it exactly as tall as the average of the two bushes on either side. If the bush is already as short as the average or shorter, then the gardener does not touch this bush and moves on to the next bush on the right, until the second-to-last bush. The baron is certain that this procedure is the key to success.
Quite simple, if you read the bold words. 😉 Here’s our code:
for case in range(1,int(raw_input())+1): #For all test cases size = int(raw_input()) #Get the case size (unused) vector =  for i in raw_input().split(" "): #Split the case values by spaces vector.append(float(i)) #Store its values as floats for i in range(1,len(vector)-1): #From second to second-to-last med = (vector[i-1]+vector[i+1])/2 #Get average from neighboors if vector[i] > med: #Am I bigger? vector[i] = med #Then average I am print "Case #%d: %.6f" % (case, vector[-2])
Evolving with smaller and clearer code. Tested with both (small and large) input sets, won at first shot. 🙂
Hope I can see you in the competition!