Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.90 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. /**
  5.  * Created by marcoaltran on 28/04/17.
  6.  */
  7. public class Solution {
  8.  
  9.     public static void main(String[] args){
  10.         Scanner scan = new Scanner(System.in);
  11.         int numCities = scan.nextInt();
  12.         int towerRange = scan.nextInt();
  13.         Boolean[] isTherePower = new Boolean[numCities];
  14.         for (int i = 0; i < numCities; i++) {
  15.             isTherePower[i] = scan.nextInt() != 0;
  16.         }
  17.         solveProblem(numCities, towerRange, isTherePower);
  18.  
  19.     }
  20.  
  21.     private static void solveProblem(int numCities, int towerRange, Boolean[] isTherePower) {
  22.         for (int i = 1; i <= numCities; i++) {
  23.             boolean solved = getSolution(i, numCities, towerRange, isTherePower,
  24.                     new boolean[numCities], 0);
  25.             if (solved) {
  26.                 return;
  27.             }
  28.         }
  29.         System.out.println("-1");
  30.     }
  31.  
  32.     private static boolean getSolution(int citiesToLight, int numCities, int towerRange,
  33.                                     Boolean[] isTherePower, boolean[] solution, int index) {
  34.         if(index == numCities){
  35.             if (isASolution(solution, towerRange)) {
  36.                 System.out.println(citiesToLight);
  37.                 return true;
  38.             }
  39.             else{
  40.                 return false;
  41.             }
  42.         }
  43.         boolean solved = getSolution(citiesToLight, numCities, towerRange, isTherePower, solution, index + 1);
  44.         if(solved){
  45.             return true;
  46.         }
  47.         if(isTherePower[index] && totalCitiesOnLight(solution.clone()) < citiesToLight){
  48.             boolean[] newSolution = solution.clone();
  49.             newSolution[index] = true;
  50.             return getSolution(citiesToLight, numCities, towerRange, isTherePower, newSolution, index + 1);
  51.         }
  52.         return false;
  53.     }
  54.  
  55.     private static int totalCitiesOnLight(boolean[] solution) {
  56.         int citiesOnLight = 0;
  57.         for (Boolean city : solution) {
  58.             if(city){
  59.                 citiesOnLight++;
  60.             }
  61.         }
  62.         return citiesOnLight;
  63.     }
  64.  
  65.     private static boolean isASolution(boolean[] solution, int towerRange) {
  66.         boolean[] citiesOnLight = new boolean[solution.length];
  67.         for (int i = 0; i < solution.length; i++) {
  68.             if(solution[i]){
  69.                 for (int j = 0; j < towerRange; j++) {
  70.                     if (i + j < solution.length) {
  71.                         citiesOnLight[i+j] = true;
  72.                     }
  73.                 }
  74.                 for (int j = 0; j < towerRange; j++) {
  75.                     if (i - j >= 0) {
  76.                         citiesOnLight[i-j] = true;
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.         for (Boolean cityOnLight : citiesOnLight) {
  82.             if(!cityOnLight){
  83.                 return false;
  84.             }
  85.         }
  86.         return true;
  87.     }
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement