SHARE
TWEET

monsters

arsovski Oct 21st, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. import java.util.*;
  4.  
  5. //TODO this exercise without using Vector
  6. public class Monsters {
  7.  
  8.     public static void  main(String[] args){
  9.  
  10.         Scanner sc= new Scanner(System.in);
  11.         int numberOfMonsters=sc.nextInt();
  12.         int blasterStrength=sc.nextInt();
  13.  
  14.         int[] monsters=new int[numberOfMonsters];
  15.  
  16.         int k=0;
  17.         while(k<numberOfMonsters){
  18.  
  19.             int input=sc.nextInt();
  20.             monsters[k]=input;
  21.             k++;
  22.         }
  23.  
  24.         mergeSort(monsters,0,numberOfMonsters-1);
  25.  
  26.         //-1 is equal to dead monsters
  27.  
  28.         //Remove duplicates
  29.         for(int i=0;i<numberOfMonsters-1;i++){
  30.             if(monsters[i]==(monsters[i + 1]))
  31.                 monsters[i]=-1;
  32.         }
  33.  
  34.         int lastMonsterIndex=numberOfMonsters-1;
  35.         int numberOfBlasts=0;
  36.         while(lastMonsterIndex > 0){
  37.  
  38.             //Remove last element with blast
  39.             if(monsters[lastMonsterIndex] == -1){
  40.                 lastMonsterIndex--;
  41.                 continue;
  42.             }
  43.  
  44.             monsters[lastMonsterIndex]=-1;
  45.             lastMonsterIndex--;
  46.             numberOfBlasts++;
  47.  
  48.  
  49.             for(int j=0;j<numberOfMonsters;j++){
  50.  
  51.                 //Blast all of them
  52.                 if(monsters[j] == -1)
  53.                     continue;
  54.  
  55.                 monsters[j]=monsters[j] - blasterStrength;
  56.  
  57.                if(monsters[j] <= 0)
  58.                    monsters[j]=-1;
  59.             }
  60.  
  61.         }
  62.  
  63.         System.out.println(numberOfBlasts);
  64.  
  65.     }
  66.  
  67.     private static void mergeSort(int[] arr,int begin, int end){
  68.  
  69.         if(begin>=end)
  70.             return;
  71.  
  72.         int middle=(begin+end)/2;
  73.         mergeSort(arr,begin,middle);
  74.         mergeSort(arr,middle+1,end);
  75.         merge(arr,begin,middle,end);
  76.  
  77.     }
  78.  
  79.     private static void merge(int[] arr,int begin,int middle,int end){
  80.  
  81.         int firstContainerSize=middle-begin+1;
  82.         int[] firstContainer=new int[firstContainerSize];
  83.  
  84.         int secondContainerSize=end-middle;
  85.         int[] secondContainer=new int[secondContainerSize];
  86.  
  87.         for(int i=0;i<firstContainerSize;i++)
  88.             firstContainer[i]=arr[begin+i];
  89.  
  90.         for(int i=0;i<secondContainerSize;i++)
  91.             secondContainer[i]=arr[middle+1+i];
  92.  
  93.         int i=0,j=0;
  94.         int k=begin;
  95.  
  96.         while(i<firstContainerSize && j<secondContainerSize){
  97.  
  98.             if(firstContainer[i] < secondContainer[j]){
  99.                 arr[k]=firstContainer[i];
  100.                 i++;
  101.             }
  102.             else{
  103.                 arr[k]=secondContainer[j];
  104.                 j++;
  105.             }
  106.  
  107.             k++;
  108.         }
  109.  
  110.         while(i<firstContainerSize){
  111.             arr[k]=firstContainer[i];
  112.             k++;
  113.             i++;
  114.         }
  115.  
  116.         while(j<secondContainerSize){
  117.             arr[k]=secondContainer[j];
  118.             k++;
  119.             j++;
  120.         }
  121.     }
  122.  
  123.  
  124. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top