W razie czego przepiszę go na C. Póki co daje jednak błędną odpowiedź, więc jestem dobrej myśli, że zmieści się w czasie.
Dodam jeszcze kilka testów, które sam wymyśliłem i odpowiedzi, które uważam za poprawne:
100_000 1_000_000
1_000_000 1_000_000 ... 1_000_000
Odpowiedź
NIE
100_000 499_999
1_000_000 1_000_000 ... 1_000_000
Odpowiedź
12
100_000 500_000
1_000_000 1_000_000 ... 1_000_000
Odpowiedź
NIE
11 10
6, 0, 5, 2, 9, 21, 19, 18, 17, 0, 16
Odpowiedź
9
Ostatni przykład zakładając, że 0 jest liczbą naturalną.
import java.util.OptionalInt;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int numberOfTests = scanner.nextInt();
Al_28_07 controller = Al_28_07.withMaxStopDuration(1_000_000);
for (int i = 0; i < numberOfTests; i++) {
int numberOfStops = scanner.nextInt();
int numberOfCars = scanner.nextInt();
int[] stopsDurations = new int[numberOfStops];
for (int j = 0; j < numberOfStops; j++) {
int stopDuration = scanner.nextInt();
stopsDurations[j] = stopDuration;
}
OptionalInt smallestNumberOfStops = controller.findSmallestNumberOfStops(numberOfCars, stopsDurations);
if (smallestNumberOfStops.isPresent()) {
System.out.println(smallestNumberOfStops.getAsInt());
} else {
System.out.println("NIE");
}
}
}
}
class Al_28_07 {
private static final int WALK_DURATION = 2;
private static final int TIME_TO_CHECK_A_CAR = 1;
private final boolean[] carsChecked;
private final int maxStopDuration;
static Al_28_07 withMaxStopDuration(int maxStopDuration) {
return new Al_28_07(maxStopDuration);
}
private Al_28_07(int maxStopDuration) {
carsChecked = new boolean[lastCarThatCanBeReached(maxStopDuration)];
this.maxStopDuration = maxStopDuration;
}
OptionalInt findSmallestNumberOfStops(int numberOfCars, int[] stopsDurations) {
if (lastCarThatCanBeReached(maxStopDuration) < numberOfCars) {
return OptionalInt.empty();
}
for (int i = 0; i < numberOfCars; i++) {
carsChecked[i] = false;
}
int numberOfCarsLeft = numberOfCars;
int numberOfStops = 0;
for (int stopDuration : stopsDurations) {
++numberOfStops;
int lastCarThatCanBeReached = lastCarThatCanBeReached(stopDuration);
if (0 < lastCarThatCanBeReached) {
int additionalCarsThatCanBeChecked = (stopDuration - TIME_TO_CHECK_A_CAR) % WALK_DURATION;
if (numberOfCarsLeft < lastCarThatCanBeReached) {
additionalCarsThatCanBeChecked += (lastCarThatCanBeReached - numberOfCarsLeft) * WALK_DURATION;
lastCarThatCanBeReached -= lastCarThatCanBeReached - numberOfCarsLeft;
}
carsChecked[indexOf(lastCarThatCanBeReached)] = true;
for (int i = indexOf(lastCarThatCanBeReached) - 1; 0 <= i && 0 < additionalCarsThatCanBeChecked; i--) {
if (!carsChecked[i]) {
carsChecked[i] = true;
--additionalCarsThatCanBeChecked;
}
}
if (lastCarThatCanBeReached == numberOfCarsLeft) {
--numberOfCarsLeft;
for (int i = numberOfCarsLeft - 1; i >= 0; i--) {
if (carsChecked[i]) {
--numberOfCarsLeft;
} else {
break;
}
}
}
}
if (numberOfCarsLeft == 0) {
return OptionalInt.of(numberOfStops);
}
}
return OptionalInt.empty();
}
private int lastCarThatCanBeReached(int stopDuration) {
return (stopDuration - TIME_TO_CHECK_A_CAR) / WALK_DURATION;
}
private static int indexOf(int value) {
return value - 1;
}
}
