Advertisement
arsovski

monsters

Oct 21st, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.88 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement