Goodland is a country with a number of evenly spaced cities along a line. The distance between adjacent cities is unit. There is an energy infrastructure project planning meeting, and the government needs to know the fewest number of power plants needed to provide electricity to the entire list of cities. Determine that number. If it cannot be done, return .
You are given a list of city data. Cities that may contain a power plant have been labeled . Others not suitable for building a plant are labeled . Given a distribution range of , find the lowest number of plants that must be built such that all cities are served. The distribution range limits supply to cities where distance is less than k.
For example, you are given and your city data is . Each city is unit distance from its neighbors, and we'll use based indexing. We see there are cities suitable for power plants, cities and . If we build a power plant at , it can serve through because those endpoints are at a distance of and . To serve , we would need to be able to build a plant in city or . Since none of those is suitable, we must return . It cannot be done using the current distribution constraint.
Complete the pylons function in the editor below. It should return an integer that represents the minimum number of plants required or -1 if it is not possible.
pylons has the following parameter(s):
- k: an integer that represents distribution range
- arr: an array of integers that represent suitability as a building site
The first line contains two space-separated integers and , the number of cities in Goodland and the plants' range constant.
The second line contains space-separated binary integers where each integer indicates suitability for building a plant.
- Each .
- for of the maximum score.
Print a single integer denoting the minimum number of plants that must be built so that all of Goodland's cities have electricity. If this is not possible for the given value of , print .
6 2 0 1 1 1 1 0
Cities , , , and are suitable for power plants. Each plant will have a range of . If we build in cities cities, and , then all cities will have electricity.
Solution in Python
def pylons(k, arr): i = 0 c = 0 n = len(arr) while True: u = min(i+2*k-1,n) if i else min(i+k,n) for i in range(i,u)[::-1]: if arr[i]: c+=1 if i+k>=n: return c i+=1 break else: return -1 n,k = map(int,input().split()) arr = list(map(int,input().split())) print(pylons(k, arr))