Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Scanner;
- /**
- * Created by marcoaltran on 28/04/17.
- */
- public class Solution {
- public static void main(String[] args){
- Scanner scan = new Scanner(System.in);
- int numCities = scan.nextInt();
- int towerRange = scan.nextInt();
- Boolean[] isTherePower = new Boolean[numCities];
- for (int i = 0; i < numCities; i++) {
- isTherePower[i] = scan.nextInt() != 0;
- }
- solveProblem(numCities, towerRange, isTherePower);
- }
- private static void solveProblem(int numCities, int towerRange, Boolean[] isTherePower) {
- for (int i = 1; i <= numCities; i++) {
- boolean solved = getSolution(i, numCities, towerRange, isTherePower,
- new boolean[numCities], 0);
- if (solved) {
- return;
- }
- }
- System.out.println("-1");
- }
- private static boolean getSolution(int citiesToLight, int numCities, int towerRange,
- Boolean[] isTherePower, boolean[] solution, int index) {
- if(index == numCities){
- if (isASolution(solution, towerRange)) {
- System.out.println(citiesToLight);
- return true;
- }
- else{
- return false;
- }
- }
- boolean solved = getSolution(citiesToLight, numCities, towerRange, isTherePower, solution, index + 1);
- if(solved){
- return true;
- }
- if(isTherePower[index] && totalCitiesOnLight(solution.clone()) < citiesToLight){
- boolean[] newSolution = solution.clone();
- newSolution[index] = true;
- return getSolution(citiesToLight, numCities, towerRange, isTherePower, newSolution, index + 1);
- }
- return false;
- }
- private static int totalCitiesOnLight(boolean[] solution) {
- int citiesOnLight = 0;
- for (Boolean city : solution) {
- if(city){
- citiesOnLight++;
- }
- }
- return citiesOnLight;
- }
- private static boolean isASolution(boolean[] solution, int towerRange) {
- boolean[] citiesOnLight = new boolean[solution.length];
- for (int i = 0; i < solution.length; i++) {
- if(solution[i]){
- for (int j = 0; j < towerRange; j++) {
- if (i + j < solution.length) {
- citiesOnLight[i+j] = true;
- }
- }
- for (int j = 0; j < towerRange; j++) {
- if (i - j >= 0) {
- citiesOnLight[i-j] = true;
- }
- }
- }
- }
- for (Boolean cityOnLight : citiesOnLight) {
- if(!cityOnLight){
- return false;
- }
- }
- return true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement