Soluție HackerRank pentru Goodland Electricity. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Goodland Electricity
Cerinta completa
Goodland is a country with a number of evenly spaced cities along a line. The distance between adjacent cities is [Expresie matematică indisponibilă în copia arhivată] 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 -1.
You are given a list of city data. Cities that may contain a power plant have been labeled [Expresie matematică indisponibilă în copia arhivată]. Others not suitable for building a plant are labeled [Expresie matematică indisponibilă în copia arhivată]. Given a distribution range of [Expresie matematică indisponibilă în copia arhivată], 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.
Example
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
Each city is [Expresie matematică indisponibilă în copia arhivată] unit distance from its neighbors, and we’ll use [Expresie matematică indisponibilă în copia arhivată] based indexing. We see there are [Expresie matematică indisponibilă în copia arhivată] cities suitable for power plants, cities [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]. If we build a power plant at [Expresie matematică indisponibilă în copia arhivată], it can serve [Expresie matematică indisponibilă în copia arhivată] through [Expresie matematică indisponibilă în copia arhivată] because those endpoints are at a distance of [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]. To serve [Expresie matematică indisponibilă în copia arhivată], we would need to be able to build a plant in city [Expresie matematică indisponibilă în copia arhivată] or [Expresie matematică indisponibilă în copia arhivată]. Since none of those is suitable, we must return -1. It cannot be done using the current distribution constraint.
Function Description
Complete the pylons function in the editor below.
pylons has the following parameter(s):
- int k: the distribution range
- int arr[n]: each city’s suitability as a building site
Returns
- int: the minimum number of plants required or -1
Input Format
The first line contains two space-separated integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], the number of cities in Goodland and the plants’ range constant.
The second line contains [Expresie matematică indisponibilă în copia arhivată] space-separated binary integers where each integer indicates suitability for building a plant.
Constraints
- [Expresie matematică indisponibilă în copia arhivată]
- Each [Expresie matematică indisponibilă în copia arhivată].
Subtask
- [Expresie matematică indisponibilă în copia arhivată] for [Expresie matematică indisponibilă în copia arhivată] of the maximum score.
Output Format
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 [Expresie matematică indisponibilă în copia arhivată], print [Expresie matematică indisponibilă în copia arhivată].
Sample Input
STDIN Function
----- --------
6 2 arr[] size n = 6, k = 2
0 1 1 1 1 0 arr = [0, 1, 1, 1, 1, 0]
Sample Output
2
Explanation
Cities [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată] are suitable for power plants. Each plant will have a range of [Expresie matematică indisponibilă în copia arhivată]. If we build in cities [Expresie matematică indisponibilă în copia arhivată] cities, [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], then all cities will have electricity.
Limbajul de programare folosit: java8
Cod:
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the pylons function below.
static int pylons(int k, int[] arr) {
int counter = 0;
int index = 0;
int notCovered = 1;
int lastAvailable = -1;
while (index < arr.length) {
if (arr[index] == 1) {
lastAvailable = index;
}
if (notCovered >= k) {
if (lastAvailable == -1) {
return -1;
}
notCovered = - (k - 1) + (index - lastAvailable) + 1;
index++;
counter++;
lastAvailable = -1;
} else if (index == arr.length - 1) {
if (notCovered > 0) {
if (lastAvailable != 0) {
counter++;
} else {
return -1;
}
}
index++;
} else {
notCovered++;
index++;
}
}
return counter;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nk = scanner.nextLine().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
int[] arr = new int[n];
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}
int result = pylons(k, arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Scor obtinut: 1.0
Submission ID: 464604517
Link challenge: https://www.hackerrank.com/challenges/pylons/problem