Zagadka o 25 koniach na początku wydaje się dość oczywista: na pewno nie da się znaleźć trzech najszybszych koni w jednym ani w dwóch wyścigach, ze względu na limit 10 koni na jeden wyścig. Na pewno da się prosto ustalić odpowiedź za pomocą czterech wyścigów: puszczamy dwa razy po dziesięć koni w wyścigach W1 i W2, dwie najszybsze trójki puszczamy z czterema końmi z pozostałej piątki w wyścigu W3, wreszcie w ostatnim wyścigu W4 puszczamy zwycięzców z W3 plus tego ostatniego, który jeszcze nie biegł.
Pytanie zatem, czy da się znaleźć trzy najszybsze konie w trzech wyścigach?
Najpierw puszczamy 10 koni w wyścigu W1. Oznaczamy najszybszą trójkę literami A, B, C (od najszybszego, czyli A wygrał, B był drugi a C - trzeci).
Następnie puszczamy konia B oraz 9 kolejnych (które jeszcze nie biegły) w wyścigu W2. Pozostałych sześć koni czeka.
I teraz tak: koń B mógł w wyścigu W2 zająć pierwsze, drugie, trzecie lub dalsze miejsce. W zależności od tego wybieramy kandydatów do ostatniego, trzeciego wyścigu:
- Jeżeli B zajął w W2 pierwsze miejsce, mamy czterech kandydatów do W3: A, B, C, oraz koń, który zajął drugie miejsce w W2 (jest on wolniejszy od B, ale może okazać się szybszy od C).
- Jeżeli B zajął w W2 drugie miejsce, mamy trzech kandydatów do W3: A, B, oraz koń, który wygrał W2 (był on szybszy od B, a więc również od C)
- Jeżeli B zajął w W2 trzecie miejsce, to mamy znów trzech kandydatów: A, oraz dwa konie, które przybiegły w W2 na metę przed B. Są one szybsze od B i C.
- Wreszcie jeżeli B zajął w W2 miejsce czwarte lub dalsze, mamy czterech kandydatów do W3: A, oraz trzy konie, które były w W2 szybsze od B (a tym samym od C).
Po wybraniu trzech lub czterech kandydatów na podstawie W2, puszczamy ich w ostatnim, trzecim wyścigu W3 wraz z sześcioma końmi, które jeszcze nie biegły. Trzy najszybsze konie z W3 są zarazem trzema najszybszymi z całej dwudziestkipiątki.
Wolisz obrazkowo? Proszę bardzo:
A jak Wam poszło?
1
Najpierw odezwał się Rozie, który był bardzo blisko poprawnej odpowiedzi:
Wyścig 1 biegną konie 1-10
-- Rozie, sobota
Wyścig 2 biegną konie 11-20 +trzecie miejsce z wyścigu 1 (w1m3)
Wyścig 3 biegną konie 21-25 oraz, w zależności od wyniku konia (w1m3):
a) w1m3 nie był w trójce: w2m3 + w2m2 + w2m1 + w1m2 + w1m1
b) w1m3 był trzeci lub lepiej: dodatkowo w1m3 + w1m2 + w1m1 + w2m2 + w2m1
Czyli w trzecim miejsca 1 i 2 z obu poprzednich wyścigów oraz trzecie miejsce z drugiego wyścigu.
Zajęło mi dobrą chwilę wykombinowanie co się tutaj nie zgadza: otóż Rozie w drugim wyścigu puścił 11 koni, a limit jest 10. Nie zaliczam.
2
Godzinę później odezwał się Cichy, który rozpracował zadanie bezbłędnie:
Pierwszy wyścig: dziesięć losowych koni; oznaczmy trzy najlepsze jako A, B i C.
Drugi wyścig: B i dziewięć koni, które nie biegły.
Trzeci wyścig: Pozostałe sześć nieśmiganych koni i A, plus w zależności od wyniku drugiego biegu:
- jeśli B wygrał: B, wicelider i C;
- jeśli B był drugi: B i zwycięzca;
- jeśli B był trzeci: dwa pierwsze konie;
- jeśli B nie załapał się na podium: trzy pierwsze.Trzy najlepsze konie w ostatnim wyścigu muszą być trzema najszybszymi w całej stawce.
-- Cichy, sobota
3, 4
Następnie nadeszły odpowiedzi od: Tacitgreg, Waldek. Obydwie błędne, bo z czwórką - nie zaliczam. Nadal jednak pełen jestem podziwu dla strony internetowej Tacitgrega, choć kompletnie nie wiem po co mu znaki końca linii w kodzie - po ich usunięciu strona powinna działać o jakieś 20% szybciej! 😀
5
Potem była chwila ciszy (i powietrze stało), aż we wtorek wczesnym popołudniem odezwał się Krzysiek i też pozamiatał:
1. 10 koni się ściga
Krzysiek, wtorek, wczesne popołudnie
2. 9 koni z puli jeszcze nie biegnących + drugi koń z #1 wyścigu (nazwijmy go Wojtek) się ściga
3. 6 koni jeszcze nie biegnących + zwycięzca #1 wyścigu +
a. jeśli w #2 wyścigu Wojtek był poza pudłem to pierwsze 3 konie
b. jeśli w #2 wyścigu Wojtek był trzeci to 2 pierwsze konie
c. jeśli w #2 wyścigu Wojtek był drugi to Wojtek + zwycięzca
c. jeśli w #2 wyścigu Wojtek był pierwszy to Wojtek + 3 koń z #1 wyścigu + 2 koń z #2 wyścigu
Trzeci wyścig wyłoni najszybszą trójkę
Chodzi oczywiście o przejrzystość kodu – w ten sposób jest łatwiejszy do analizy. Szybkość to nie wszystko!
P.S. postałej
Ech, człowiek za wyścigi konne się bierze, a tu okazuje się, że nie umie liczyć do 10.
suchar na dziś
10 koni to był race condition
Nieśmieszne.
😉