Istnieją dwie klepsydry: jedna działa całkowicie w \(4\) minut, druga w \(7\) minut. Jak zmierzyć dokładnie \(9\) minut, skoro pomiar musi się rozpocząć przy pierwszym uruchomieniu zegarów? Niedopuszczalny jest inny zegar, odliczanie sekund i zgadywanie. Wystarczy odwrócić klepsydry i obserwować, kiedy górna komora będzie pusta. Zawrócenie nie powinno zająć dużo czasu. To, czego szukamy, to proces, w którym koniec pożądanego okresu czasu można rozpoznać jedynie po klepsydrach.
Nazywamy zegar z \(4\) minutami \(A\) i ten z \(7\) minutami \(B\) . Początkowo cały piasek znajduje się na dnie. Uruchamiamy oba zegary jednocześnie, przekręcając je; Od tego momentu liczy się przeszukane \(9\) minuty. Następnie zawsze możesz handlować, gdy zegar na górze stanie się pusty. Nie możesz przekręcić jednego, jednego lub obu zegarów, nawet tego, który jeszcze chodzi. Czekasz do następnego razu, kiedy się skończy. Zatrzymywanie i znakowanie jest niedozwolone; pusty zegar może pozostać. Rozwiązanie wygląda tak:
- W minucie \(0\) \(A\) i \(B\) rozpoczynają się.
- W minucie \(4\) \(A\) jest puste i zostaje odwrócone. \(B\) nadal działa bez zmian.
- W minucie \(7\) \(B\) jest puste i zostaje odwrócone. Pozostała jeszcze \(1\) minuta w \(A\) .
- W minucie \(8\) \(A\) jest puste. W \(B\) piasek spływał dokładnie przez \(1\) minutę; dlatego \(B\) jest natychmiast ponownie odwracane.
- W minucie \(9\) \(B\) jest puste. Czas, którego szukałeś, został osiągnięty.
W minucie \(8\) odwracamy zegar \(B\) który nadal chodzi. Od ich ponownego uruchomienia w minucie \(7\) spłynęło dokładnie tyle piasku, ile zmieściłoby się przez wąskie gardło w ciągu \(1\) minuty. Po przewróceniu na wierzch zostaje tylko ta niewielka ilość. Teraz potrzeba \(1\) minuty, aby ponownie spłynąć. Dlatego zegar staje się pusty w minucie \(9\) , a nie po kolejnym pełnym uruchomieniu. Dlatego ostatnią minutę odmierzamy piaskiem, który już przepłynął. Animacja pokazuje ten ruch:
W przypadku ogólnego rozwiązania przydatne jest również odwrócenie działającej klepsydry. Przez pozostały czas rozumiemy czas, w którym piasek musi jeszcze przepłynąć w górnej komorze. Jeśli pełny zegar ma czas działania \(c\) i pozostały czas działania wynosi \(r\) , wówczas ilość piasku na dole odpowiada czasowi trwania \(cr\) . Kiedy go odwrócisz, dokładnie ta ilość pojawi się na górze. Jeśli górna komora była wcześniej pełna, później będzie pusta i odwrotnie. W przypadku zegara częściowo pracującego nowy pozostały czas pracy wynosi \(r'\):
$$r'=c-r.$$
Poprzednio pomiar rozpoczynał się od pierwszego obrotu. Oznacza to „bez czasu realizacji”: liczy się każda minuta od startu. „Z wyprzedzeniem” oznacza natomiast, że można najpierw przygotować zegary, a żądany okres rozpoczyna się później. Na przykład uruchamiamy oba zegary i przekręcamy \(A\) o minucie \(4\) . Jeśli \(B\) stanie się pusty w minucie \(7\) , rozpoczyna się nasz pomiar. Jeśli \(A\) stanie się pusty w minucie \(8\) , zakończy się. Zmierzyliśmy \(1\) minutę; poprzednie \(7\) minuty nie liczą się.
Teraz rozważymy dowolne klepsydry z dodatnimi czasami całkowitymi \(a\) i \(b\) . Nazywamy żądany czas trwania \(T\) . Jakie czasy można za pomocą tego zmierzyć, jeśli dozwolone jest przygotowanie? Również w tym przypadku początek i koniec muszą być rozpoznawalne po pustej przestrzeni. Dlatego nie powinieneś zaczynać pomiaru w pewnym momencie, kierując się swoimi odczuciami. Uchwyty pozostają takie same jak w rzeczywistej układance. Najpierw pokazujemy, które czasy są wykluczone; następnie pokażemy Ci, jak właściwie zmierzyć całą resztę.
Najpierw weźmy zegary z \(6\) i \(10\) minutami. Oba czasy działania są podzielne przez \(2\) . Piasek można zatem mentalnie podzielić na porcje, których przebycie zajmuje \(2\) minuty. Kiedy go odwrócisz lub zaczekasz, aż następnym razem będzie pusty, ponownie powstaną tylko całe porcje. Dlatego wszystkie obserwowalne czasy puste są oddalone od siebie o parzystą liczbę minut. Nie można go używać do pomiaru czasu trwania \(3\) minut, nawet jeśli wcześniej przygotujesz zegary tak długo, jak chcesz.
Ogólnie rzecz biorąc, niech \(g=\gcd(a,b)\) będzie największym wspólnym dzielnikiem czasów działania. Początkowo oba pozostałe terminy są wielokrotnościami \(g\) . Po obróceniu \(r\) zmienia się w \(ar\) lub \(br\) ; oba pozostają podzielne przez \(g\) . Podczas oczekiwania upływa najmniejszy dodatni pozostały czas, który jest również wielokrotnością \(g\) . Oznacza to, że wszystkie puste czasy i ich odległości pozostają wielokrotnościami \(g\) . Mierzalny czas trwania musi zatem spełniać \(g\mid T\) : \(T\) musi być podzielny przez \(g\) . Czy to wystarczy, okaże się.
W tym celu pozwalamy obydwóm zegarom chodzić raz po raz całkowicie i przewracamy każdy z nich, gdy tylko będzie pusty. Pierwsza staje się pusta po \(a,2a,3a,\ldots\) jednostkach czasu, druga po \(b,2b,3b,\ldots\) . Szukamy czasu \(mb\) drugiego zegara i późniejszego czasu \(na\) pierwszego, pomiędzy którymi leży dokładnie \(T\) . Lemat Bézouta gwarantuje dopasowanie liczb całkowitych \(n,m\) jeśli \(T\) jest dodatnią wielokrotnością \(g\) . Związek, którego szukasz to::
$$na-mb=T.$$
Liczby \(n,m\) dostarczone przez Bézouta mogą początkowo być ujemne. Nie można przeprowadzić serii negatywnych. Można jednak zwiększyć obie liczby bez zmiany przedziału czasu: zastępujemy je \(n+kb/g\) i \(m+ka/g\) , gdzie \(k\) jest wystarczająco dużą dodatnią liczbą całkowitą. Obydwa czasy są zatem przesunięte o tę samą wielkość \(kab/g\) ; ich różnica pozostaje \(T\) . Zatem obie liczby stają się dodatnie, a wymagane czasy faktycznie następują po uruchomieniu zegarów.
Teraz policzysz pełne cykle każdego zegara. Kiedy \(m\) zegar się opróżni, rozpoczyna się pomiar; kończy się, gdy pierwszy zegar opróżni się po raz \(n\) -ty. Pomiędzy nimi są dokładnie \(T\) jednostki czasu. Przygotowanie może zająć dużo czasu. Dowód nie obiecuje szczególnie krótkiego procesu. Dla \(T=0\) początek i koniec pokrywają się. Dowodzi to dla wszystkich nieujemnych celów całkowitych: podczas przygotowania czas trwania można zmierzyć wtedy i tylko wtedy, gdy dzieli go największy wspólny dzielnik:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Zasada ta nie musi koniecznie dotyczyć pomiarów rozpoczynających się już przy pierwszym uruchomieniu. Na przykład z \(4\) i \(7\) minutami \(g=1\) , ale po \(1\) minucie żaden zegar nie jest pusty. Więc nie widać końca tej minuty. Opisany powyżej pomiar od minuty \(7\) do \(8\) działa tylko dlatego, że przygotowanie się nie liczy. Dowód odpowiada zatem na pytanie, co jest możliwe po przygotowaniu. Jeśli szukasz dozwolonego procesu z przygotowaniem lub bez, pomocne będzie następujące systematyczne wyszukiwanie.
Skrypt PHP pamięta zarówno pozostały czas działania, jak i czas, który upłynął od rozpoczęcia pomiaru. W przypadku każdego takiego warunku wypróbuj wszystko \(4\) Możliwości: brak zegara, tylko pierwszy, tylko drugi lub obrócić oba. Następnie czeka do następnego opróżnienia. Wartość \(-1\) wskazuje przygotowanie; wpis start ustawia czas pomiaru \(0\). Znane warunki nie będą ponownie badane. Znalezioną sekwencję uzyskuje się poprzez jej poprzedniki. wait odnosi się jedynie do odległości do następnego opróżnienia, a nie do dodatkowego pomiaru czasu:
<?php
declare(strict_types=1);
function hourglass(int $a, int $b, int $target, bool $prepare = false): ?array
{
if ($a <= 0 || $b <= 0 || $target < 0) {
throw new InvalidArgumentException('Positive capacities, nonnegative target required.');
}
$root = [0, 0, $prepare ? -1 : 0];
$key = static fn(array $s): string => implode(',', $s);
$queue = new SplQueue();
$queue->enqueue($root);
$previous = [$key($root) => null];
$enqueue = static function (array $next, array $from, array $action)
use ($queue, &$previous, $key): void {
$k = $key($next);
if (!array_key_exists($k, $previous)) {
$previous[$k] = [$key($from), $action];
$queue->enqueue($next);
}
};
while (!$queue->isEmpty()) {
$state = $queue->dequeue();
[$x, $y, $elapsed] = $state;
if ($elapsed === $target) {
$path = [];
for ($k = $key($state); $previous[$k] !== null;) {
[$k, $action] = $previous[$k];
$path[] = $action;
}
return array_reverse($path);
}
if ($elapsed === -1) {
$enqueue([$x, $y, 0], $state, ['start' => true]);
}
for ($mask = 0; $mask < 4; ++$mask) {
$u = ($mask & 1) ? $a - $x : $x;
$v = ($mask & 2) ? $b - $y : $y;
if ($u === 0 && $v === 0) {
continue;
}
$wait = $u === 0 ? $v : ($v === 0 ? $u : min($u, $v));
$nextTime = $elapsed < 0 ? -1 : $elapsed + $wait;
if ($nextTime > $target) {
continue;
}
$enqueue(
[max(0, $u - $wait), max(0, $v - $wait), $nextTime],
$state,
['flip' => $mask, 'wait' => $wait]
);
}
}
return null;
}
foreach ([[4, 7, 9, false], [4, 7, 1, false], [4, 7, 1, true],
[6, 10, 3, true], [5, 5, 10, false], [4, 7, 0, false]] as $case) {
echo json_encode($case), ': ', json_encode(hourglass(...$case)), PHP_EOL;
}
Wyszukiwanie pozwala znaleźć lub zwrócić dozwolony proces null, jeśli żaden nie istnieje. Obejmuje wszystkie dozwolone kontynuacje i wymaga maksymalnego przygotowania \((a+1)(b+1)(T+2)\) Stany. Dlatego duże dane wejściowe wymagają dużej ilości pamięci. Minimalizowana jest liczba przejść wyszukiwania, a nie czas przygotowania. Racjonalne czasy biegu i czasy docelowe są przeliczane na liczby całkowite przy użyciu wspólnego mianownika. Na przykład dla czasów wykonania bez wspólnej jednostki czasu \(1\) oraz \(\sqrt{2}\), to wyszukiwanie liczb całkowitych skończonych nie jest odpowiednie.