Задача следующая:
Есть 25 лошадей. На ипподроме 5 дорожек. Надо определить 3 самые быстрые лошади за минимальное число заездов. Время замерять нельзя. Мы только знаем, кто в каком порядке финиширует. Можно считать, что время за которое каждая лошадь пробегает дистанцию не меняется от заезда к заезду.
Решение
Это можно сделать за 7 забегов.
Разбиваем на 5 групп по пять лошадей. Проводим 5 забегов (по одному на группу).
Из победителей в каждой группе формируем шестой забег. Победитель шестого забега - топ 1.
Формируем седьмой забег из:
1) Второго и третьего места из шестого забега.
2) Второго и третьего места из группы (группа в числе изначальных 5 забегов), из которой победитель шестого забега.
3) Второго места из группы (группа в числе изначальных 5 забегов), из которой лошадь, занявшая второе место в шестом забеге.
Победитель седьмего забега - топ 2, второе место в седьмом забеге - топ 3.
Код проверки
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
boolean debugMode = false;
int numberOfSimulations = 1000_000;
for (int simulation = 0; simulation < numberOfSimulations; simulation++) {
if (simulation % 100000 == 0) {
System.out.println("Simulation number " + simulation);
}
simulate(debugMode);
}
System.out.println("No mismatches found, all " + numberOfSimulations + " passed!");
}
private static void simulate(boolean debugMode) {
List<Horse> horses = Horses.init();
if (debugMode) {
System.out.println("Initial horses:" + horses);
}
List<HorseRace> horseRaces = Horses.splitIntoFiveGroups(horses);
if (debugMode) {
System.out.println("Five Groups: " + horseRaces);
}
horseRaces.forEach(HorseRace::race);
if (debugMode) {
System.out.println("Five Groups After Five Races: " + horseRaces);
}
HorseRace sixRace = Horses.getWinnersToFormSixRace(horseRaces);
if (debugMode) {
System.out.println("Six Race Before: " + sixRace);
}
sixRace.race();
if (debugMode) {
System.out.println("Six Race After: " + sixRace);
}
Map<Horse, HorseRace> horsesToInitialFiveRaces = Horses.indexHorsesToInitialFiveRaces(horseRaces);
HorseRace sevenRace = new HorseRace();
sevenRace.add(sixRace.getSecond());
sevenRace.add(sixRace.getThird());
HorseRace raceOfWinnerOfSixRace = horsesToInitialFiveRaces.get(sixRace.getWinner());
sevenRace.add(raceOfWinnerOfSixRace.getSecond());
sevenRace.add(raceOfWinnerOfSixRace.getThird());
HorseRace raceOfSecondOfSixRace = horsesToInitialFiveRaces.get(sixRace.getSecond());
sevenRace.add(raceOfSecondOfSixRace.getSecond());
if (debugMode) {
System.out.println("Seven Race Before: " + sevenRace);
}
sevenRace.race();
if (debugMode) {
System.out.println("Seven Race After: " + sevenRace);
}
List<Horse> identifiedTopThreeBySevenRaces = new ArrayList<>();
identifiedTopThreeBySevenRaces.add(sixRace.getWinner());
identifiedTopThreeBySevenRaces.add(sevenRace.getWinner());
identifiedTopThreeBySevenRaces.add(sevenRace.getSecond());
List<Horse> expectedTopThree = Horses.copySortAndGetTopThree(horses);
if (debugMode) {
System.out.println("Expected top three horses:" + expectedTopThree);
}
if (debugMode) {
System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
}
if (!identifiedTopThreeBySevenRaces.equals(expectedTopThree)) {
System.out.println("Mismatch found!");
System.out.println("Expected top three horses:" + expectedTopThree);
System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
throw new RuntimeException("Mismatch found!");
}
}
}
class Horses {
public static List<Horse> init() {
List<Integer> raceTimes = new ArrayList<>(
IntStream.range(0, 25)
.map(index -> index * 100)
.boxed()
.toList());
Collections.shuffle(raceTimes);
return IntStream.range(0, 25)
.mapToObj(index -> new Horse(index, raceTimes.get(index)))
.collect(Collectors.toList());
}
public static List<Horse> copySortAndGetTopThree(List<Horse> horses) {
return horses.stream()
.map(Horse::new)
.sorted()
.limit(3)
.toList();
}
public static List<HorseRace> splitIntoFiveGroups(List<Horse> horses) {
List<HorseRace> horseRaces = new ArrayList<>();
for (int i = 0; i < horses.size(); i += 5) {
HorseRace race = new HorseRace();
for (int j = i; j < i + 5; j++) {
race.add(horses.get(j));
}
horseRaces.add(race);
}
return horseRaces;
}
public static HorseRace getWinnersToFormSixRace(List<HorseRace> horseRaces) {
return new HorseRace(
horseRaces.stream()
.map(HorseRace::getWinner)
.collect(Collectors.toList()));
}
public static Map<Horse, HorseRace> indexHorsesToInitialFiveRaces(List<HorseRace> horseRaces) {
Map<Horse, HorseRace> index = new HashMap<>();
for (HorseRace horseRace : horseRaces) {
for (Horse horse : horseRace.getHorses()) {
index.put(horse, horseRace);
}
}
return index;
}
}
class Horse implements Comparable<Horse> {
private final int index;
private final int raceTime;
public Horse(int index, int raceTime) {
this.index = index;
this.raceTime = raceTime;
}
public Horse(Horse horse) {
this.index = horse.index;
this.raceTime = horse.raceTime;
}
@Override
public String toString() {
return "Horse{" +
"index=" + index +
", raceTime=" + raceTime +
'}';
}
@Override
public int compareTo(Horse horse) {
return this.raceTime - horse.raceTime;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Horse horse = (Horse) o;
return index == horse.index && raceTime == horse.raceTime;
}
@Override
public int hashCode() {
return Objects.hash(index, raceTime);
}
}
class HorseRace {
private final List<Horse> horses;
public HorseRace() {
this.horses = new ArrayList<>();
}
public HorseRace(List<Horse> horses) {
this.horses = horses;
}
public void add(Horse horse) {
if (this.horses.size() >= 5) {
throw new IllegalArgumentException("Number of horses in a race is limited by 5");
}
this.horses.add(horse);
}
public List<Horse> getHorses() {
return this.horses;
}
public void race() {
Collections.sort(horses);
}
public Horse getWinner() {
return horses.getFirst();
}
public Horse getSecond() {
return horses.get(1);
}
public Horse getThird() {
return horses.get(2);
}
@Override
public String toString() {
return "HorseRace{" +
"horses=" + horses +
'}';
}
}
Второй, немного измененный, вариант, где время забега не целое уникальное число, а случайное вещественное число:
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
boolean debugMode = false;
int numberOfSimulations = 1000_000;
for (int simulation = 0; simulation < numberOfSimulations; simulation++) {
if (simulation % 100000 == 0) {
System.out.println("Simulation number " + simulation);
}
simulate(debugMode);
}
System.out.println("No mismatches found, all " + numberOfSimulations + " passed!");
}
private static void simulate(boolean debugMode) {
List<Horse> horses = Horses.init();
if (debugMode) {
System.out.println("Initial horses:" + horses);
}
List<HorseRace> horseRaces = Horses.splitIntoFiveGroups(horses);
if (debugMode) {
System.out.println("Five Groups: " + horseRaces);
}
horseRaces.forEach(HorseRace::race);
if (debugMode) {
System.out.println("Five Groups After Five Races: " + horseRaces);
}
HorseRace sixRace = Horses.getWinnersToFormSixRace(horseRaces);
if (debugMode) {
System.out.println("Six Race Before: " + sixRace);
}
sixRace.race();
if (debugMode) {
System.out.println("Six Race After: " + sixRace);
}
Map<Horse, HorseRace> horsesToInitialFiveRaces = Horses.indexHorsesToInitialFiveRaces(horseRaces);
HorseRace sevenRace = new HorseRace();
sevenRace.add(sixRace.getSecond());
sevenRace.add(sixRace.getThird());
HorseRace raceOfWinnerOfSixRace = horsesToInitialFiveRaces.get(sixRace.getWinner());
sevenRace.add(raceOfWinnerOfSixRace.getSecond());
sevenRace.add(raceOfWinnerOfSixRace.getThird());
HorseRace raceOfSecondOfSixRace = horsesToInitialFiveRaces.get(sixRace.getSecond());
sevenRace.add(raceOfSecondOfSixRace.getSecond());
if (debugMode) {
System.out.println("Seven Race Before: " + sevenRace);
}
sevenRace.race();
if (debugMode) {
System.out.println("Seven Race After: " + sevenRace);
}
List<Horse> identifiedTopThreeBySevenRaces = new ArrayList<>();
identifiedTopThreeBySevenRaces.add(sixRace.getWinner());
identifiedTopThreeBySevenRaces.add(sevenRace.getWinner());
identifiedTopThreeBySevenRaces.add(sevenRace.getSecond());
List<Horse> expectedTopThree = Horses.copySortAndGetTopThree(horses);
if (debugMode) {
System.out.println("Expected top three horses:" + expectedTopThree);
}
if (debugMode) {
System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
}
if (!identifiedTopThreeBySevenRaces.equals(expectedTopThree)) {
System.out.println("Mismatch found!");
System.out.println("Expected top three horses:" + expectedTopThree);
System.out.println("identifiedTopThreeBySevenRaces: " + identifiedTopThreeBySevenRaces);
throw new RuntimeException("Mismatch found!");
}
}
}
class Horses {
public static List<Horse> init() {
Random random = new Random();
return IntStream.range(0, 25)
.mapToObj(index -> new Horse(index, random.nextDouble()))
.collect(Collectors.toList());
}
public static List<Horse> copySortAndGetTopThree(List<Horse> horses) {
return horses.stream()
.map(Horse::new)
.sorted()
.limit(3)
.toList();
}
public static List<HorseRace> splitIntoFiveGroups(List<Horse> horses) {
List<HorseRace> horseRaces = new ArrayList<>();
for (int i = 0; i < horses.size(); i += 5) {
HorseRace race = new HorseRace();
for (int j = i; j < i + 5; j++) {
race.add(horses.get(j));
}
horseRaces.add(race);
}
return horseRaces;
}
public static HorseRace getWinnersToFormSixRace(List<HorseRace> horseRaces) {
return new HorseRace(
horseRaces.stream()
.map(HorseRace::getWinner)
.collect(Collectors.toList()));
}
public static Map<Horse, HorseRace> indexHorsesToInitialFiveRaces(List<HorseRace> horseRaces) {
Map<Horse, HorseRace> index = new HashMap<>();
for (HorseRace horseRace : horseRaces) {
for (Horse horse : horseRace.getHorses()) {
index.put(horse, horseRace);
}
}
return index;
}
}
class Horse implements Comparable<Horse> {
private final int index;
private final double raceTime;
public Horse(int index, double raceTime) {
this.index = index;
this.raceTime = raceTime;
}
public Horse(Horse horse) {
this.index = horse.index;
this.raceTime = horse.raceTime;
}
@Override
public String toString() {
return "Horse{" +
"index=" + index +
", raceTime=" + raceTime +
'}';
}
@Override
public int compareTo(Horse horse) {
return Double.compare(this.raceTime, horse.raceTime);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Horse horse = (Horse) o;
return index == horse.index;
}
@Override
public int hashCode() {
return Objects.hash(index);
}
}
class HorseRace {
private final List<Horse> horses;
public HorseRace() {
this.horses = new ArrayList<>();
}
public HorseRace(List<Horse> horses) {
this.horses = horses;
}
public void add(Horse horse) {
if (this.horses.size() >= 5) {
throw new IllegalArgumentException("Number of horses in a race is limited by 5");
}
this.horses.add(horse);
}
public List<Horse> getHorses() {
return this.horses;
}
public void race() {
Collections.sort(horses);
}
public Horse getWinner() {
return horses.getFirst();
}
public Horse getSecond() {
return horses.get(1);
}
public Horse getThird() {
return horses.get(2);
}
@Override
public String toString() {
return "HorseRace{" +
"horses=" + horses +
'}';
}
}
Top comments (0)