fork(2) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7.  
  8. public class Main {
  9.     public static void main(String[] args) {
  10.         Scanner scanner = new Scanner(System.in);
  11.         int numberOfTests = scanner.nextInt();
  12.         Al_28_07 controller = Al_28_07.withMaxStopDuration(1_000_000);
  13.         for (int i = 0; i < numberOfTests; i++) {
  14.         int numberOfStops = scanner.nextInt();
  15.         int numberOfCars = scanner.nextInt();
  16.  
  17.         int[] stopsDurations = new int[numberOfStops];
  18.  
  19.         for (int j = 0; j < numberOfStops; j++) {
  20.             int stopDuration = scanner.nextInt();
  21.             stopsDurations[j] = stopDuration;
  22.         }
  23.         OptionalInt smallestNumberOfStops = controller.findSmallestNumberOfStops(numberOfCars, stopsDurations);
  24.  
  25.         if (smallestNumberOfStops.isPresent()) {
  26.             System.out.println(smallestNumberOfStops.getAsInt());
  27.         } else {
  28.             System.out.println("NIE");
  29.         }
  30.     }
  31. }
  32. }
  33. class Al_28_07 {
  34.     private static final int WALK_DURATION = 2;
  35. private static final int TIME_TO_CHECK_A_CAR = 1;
  36. private final boolean[] carsChecked;
  37. private final int maxStopDuration;
  38.  
  39. static Al_28_07 withMaxStopDuration(int maxStopDuration) {
  40.     return new Al_28_07(maxStopDuration);
  41. }
  42.  
  43. private Al_28_07(int maxStopDuration) {
  44.     carsChecked = new boolean[lastCarThatCanBeReached(maxStopDuration)];
  45.     this.maxStopDuration = maxStopDuration;
  46. }
  47.  
  48. OptionalInt findSmallestNumberOfStops(int numberOfCars, int[] stopsDurations) {
  49.     if (lastCarThatCanBeReached(maxStopDuration) < numberOfCars) {
  50.         return OptionalInt.empty();
  51.     }
  52.     for (int i = 0; i < numberOfCars; i++) {
  53.         carsChecked[i] = false;
  54.     }
  55.     int numberOfCarsLeft = numberOfCars;
  56.     int numberOfStops = 0;
  57.  
  58.     for (int stopDuration : stopsDurations) {
  59.         ++numberOfStops;
  60.  
  61.         int lastCarThatCanBeReached = lastCarThatCanBeReached(stopDuration);
  62.  
  63.         if (0 < lastCarThatCanBeReached) {
  64.             int additionalCarsThatCanBeChecked = (stopDuration - TIME_TO_CHECK_A_CAR) % WALK_DURATION;
  65.  
  66.             if (numberOfCarsLeft < lastCarThatCanBeReached) {
  67.                 additionalCarsThatCanBeChecked += (lastCarThatCanBeReached - numberOfCarsLeft) * WALK_DURATION;
  68.                 lastCarThatCanBeReached -= lastCarThatCanBeReached - numberOfCarsLeft;
  69.             }
  70.             carsChecked[indexOf(lastCarThatCanBeReached)] = true;
  71.  
  72.             for (int i = indexOf(lastCarThatCanBeReached) - 1; 0 <= i && 0 < additionalCarsThatCanBeChecked; i--) {
  73.                 if (!carsChecked[i]) {
  74.                     carsChecked[i] = true;
  75.                     --additionalCarsThatCanBeChecked;
  76.                 }
  77.             }
  78.             if (lastCarThatCanBeReached == numberOfCarsLeft) {
  79.                 --numberOfCarsLeft;
  80.  
  81.                 for (int i = numberOfCarsLeft - 1; i >= 0; i--) {
  82.                     if (carsChecked[i]) {
  83.                         --numberOfCarsLeft;
  84.                     } else {
  85.                         break;
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.         if (numberOfCarsLeft == 0) {
  91.             return OptionalInt.of(numberOfStops);
  92.         }
  93.     }
  94.     return OptionalInt.empty();
  95. }
  96.  
  97. private int lastCarThatCanBeReached(int stopDuration) {
  98.     return (stopDuration - TIME_TO_CHECK_A_CAR) / WALK_DURATION;
  99. }
  100.  
  101. private static int indexOf(int value) {
  102.     return value - 1;
  103. }
  104. }
Success #stdin #stdout 0.06s 711680KB
comments (?)
stdin
copy 
2
10 7
2 2 16 2 2 2 2 15 2 2
10 7
2 2 2 15 2 2 2 2 16 2
stdout
copy 
8
NIE
https://ideone.com/QLEavf
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!