Guest User

Untitled

a guest
Jan 20th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  1. import java.io.*;
  2. import java.math.*;
  3. import java.security.*;
  4. import java.text.*;
  5. import java.util.*;
  6. import java.util.concurrent.*;
  7. import java.util.regex.*;
  8.  
  9. public class Solution {
  10. // Complete the minimumBribes function below.
  11. static void minimumBribes(int[] q) {
  12. int count = 0;
  13. // always keep track of min three values observed
  14. // Compare currently seeing value with this three values.
  15. int midOfThree = Integer.MAX_VALUE;
  16. int maxOfThree = Integer.MAX_VALUE;
  17. int minOfThree = Integer.MAX_VALUE;
  18.  
  19. // iterating from left to right
  20. for (int i = q.length - 1; i >= 0; i--) {
  21. // person has no way to move more than two positions -> wrong
  22. if ((q[i] - i) > 3) {
  23. System.out.println("Too chaotic");
  24. return;
  25. } else {
  26. // means current value has passed at least 3 values -> wrong
  27. if (q[i] > maxOfThree) {
  28. System.out.println("Too chaotic");
  29. return;
  30. } else if (q[i] > midOfThree) { // means -> current value has bribed 2 ppl
  31. count = count + 2;
  32. } else if (q[i] > minOfThree) { // means-> current value has bribed 1 person.
  33. count = count + 1;
  34. }
  35.  
  36. // Now adjust minThree values comparing, taking the current vlaue to account
  37. if (q[i] < minOfThree) {
  38. maxOfThree = midOfThree;
  39. midOfThree = minOfThree;
  40. minOfThree = q[i];
  41. } else if (q[i] < midOfThree) {
  42. maxOfThree = midOfThree;
  43. midOfThree = q[i];
  44. } else if (q[i] < maxOfThree) {
  45. maxOfThree = q[i];
  46. }
  47. }
  48. }
  49. System.out.println(count);
  50. }
  51.  
  52. private static final Scanner scanner = new Scanner(System.in);
  53.  
  54. public static void main(String[] args) {
  55. int t = scanner.nextInt();
  56. scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  57.  
  58. for (int tItr = 0; tItr < t; tItr++) {
  59. int n = scanner.nextInt();
  60. scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  61.  
  62. int[] q = new int[n];
  63.  
  64. String[] qItems = scanner.nextLine().split(" ");
  65. scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  66.  
  67. for (int i = 0; i < n; i++) {
  68. int qItem = Integer.parseInt(qItems[i]);
  69. q[i] = qItem;
  70. }
  71.  
  72. minimumBribes(q);
  73. }
  74.  
  75. scanner.close();
  76. }
  77. }
Add Comment
Please, Sign In to add comment