Există două clepsidre: una rulează complet în \(4\) minute, cealaltă în \(7\) minute. Cum măsori exact \(9\) minute când măsurarea trebuie să înceapă prima dată când ceasurile sunt pornite? Alt ceas, numărarea secundelor și ghicitul nu sunt permise. Tot ce trebuie să faci este să întorci clepsidrile și să urmărești când camera superioară este goală. Întoarcerea nu ar trebui să dureze. Ceea ce căutăm este un proces în care sfârșitul perioadei de timp dorite să poată fi recunoscut doar după clepsidre.
Numim ceasul cu \(4\) minute \(A\) iar pe cel cu \(7\) minute \(B\) . Inițial tot nisipul este în partea de jos. Pornim ambele ceasuri în același timp, răsturnându-le; Din acest moment se numără \(9\) minute căutate. După aceea, puteți tranzacționa oricând când un ceas din partea de sus devine gol. Nu puteți întoarce unul, unul sau ambele ceasuri, chiar și unul care încă funcționează. Așteptați până data viitoare când se epuizează. Oprirea și marcarea nu sunt permise; un ceas gol poate rămâne în picioare. Soluția arată așa:
- La minutul \(0\) \(A\) și \(B\) sunt pornite.
- La minutul \(4\) \(A\) este gol și este răsturnat. \(B\) continuă să ruleze neschimbat.
- La minutul \(7\) \(B\) este gol și este răsturnat. Mai este \(1\) minut rămas în \(A\) .
- La minutul \(8\) \(A\) este gol. În \(B\) nisipul a coborât exact pentru \(1\) minut; prin urmare \(B\) este imediat răsturnat din nou.
- La minutul \(9\) \(B\) este gol. Ora pe care o căutați a fost atinsă.
La minutul \(8\) întoarcem ceasul \(B\) care încă funcționează. De la repornirea lor la minutul \(7\) , a trecut exact la fel de mult nisip cât ar putea trece prin blocaj în \(1\) minut. După întoarcere, numai această cantitate mică este deasupra. Acum durează \(1\) minut pentru a se scurge din nou. Prin urmare, ceasul devine gol la minutul \(9\) , nu după o altă rulare completă. Deci măsurăm ultimul minut cu nisip care a trecut deja. Animația arată această mișcare:
Răsturnarea unei clepsidre care rulează este, de asemenea, utilă pentru soluția generală. Prin timpul rămas ne referim la timpul prin care nisipul mai trebuie să curgă în camera superioară. Dacă ceasul complet are timpul de funcționare \(c\) și timpul de funcționare rămas este \(r\) , atunci cantitatea de nisip din partea de jos corespunde duratei \(cr\) . Când îl întorci, această sumă exactă ajunge în vârf. Dacă camera superioară este plină în prealabil, aceasta va fi goală după aceea și invers. Pentru un ceas care rulează parțial, noul timp de rulare rămas este \(r'\):
$$r'=c-r.$$
Anterior, măsurarea începea cu prima viraj. Aceasta înseamnă „fără timp de livrare”: fiecare minut de la început contează. „Cu avans” înseamnă, pe de altă parte, că puteți pregăti mai întâi ceasurile și perioada de timp dorită începe mai târziu. De exemplu, pornim ambele ceasuri și întoarcem \(A\) la minutul \(4\) . Dacă \(B\) devine gol în minutul \(7\) , începe măsurarea noastră. Dacă \(A\) devine gol în minutul \(8\) , se termină. Am măsurat \(1\) minut; minutele anterioare \(7\) nu se iau în calcul.
Acum luăm în considerare clepsidrele arbitrare cu timpi de rulare întregi pozitivi \(a\) și \(b\) . Numim durata dorită \(T\) . Ce timpi pot fi măsurați cu aceasta dacă pregătirea este permisă? Și aici, începutul și sfârșitul trebuie să fie recunoscute după un spațiu gol. Deci nu ar trebui să începi să măsori la un moment dat pe baza sentimentelor tale. Mânerele rămân aceleași ca în puzzle-ul real. Mai întâi arătăm ce timpuri sunt excluse; apoi vă vom arăta cum să măsurați de fapt toate celelalte.
Mai întâi să luăm ceasuri cu \(6\) și \(10\) minute. Ambii timpi de rulare sunt divizibili cu \(2\) . Prin urmare, nisipul poate fi împărțit mental în porțiuni, fiecare dintre ele durează \(2\) minute pentru a trece. Când îl întoarceți sau așteptați până data viitoare când este gol, sunt create din nou doar porțiuni întregi. Toți timpii goali observabili sunt, prin urmare, la un număr par de minute. Nu îl puteți folosi pentru a măsura o durată de \(3\) minute, chiar dacă pregătiți ceasurile atât timp cât doriți în prealabil.
În general, fie \(g=\gcd(a,b)\) cel mai mare divizor comun al timpilor de rulare. Inițial, ambii termeni rămași sunt multipli ai \(g\) . Când este rotit \(r\) devine fie \(ar\) fie \(br\) ; ambele rămân divizibile cu \(g\) . În timpul așteptării, trece cel mai mic timp pozitiv rămas, care este, de asemenea, un multiplu al \(g\) . Aceasta înseamnă că toți timpii liberi și distanțele lor rămân multipli de \(g\) . O durată măsurabilă trebuie deci să satisfacă \(g\mid T\) : \(T\) trebuie să fie divizibil cu \(g\) . Rămâne de văzut dacă este suficient.
Pentru a face acest lucru, lăsăm ambele ceasuri să funcționeze complet iar și iar și le întoarcem pe fiecare de îndată ce este gol. Primul devine apoi gol după \(a,2a,3a,\ldots\) unități de timp, al doilea după \(b,2b,3b,\ldots\) . Căutăm un timp \(mb\) al celui de-al doilea ceas și un timp ulterior \(na\) al primului, între care exact \(T\) se află. Lema lui Bézout garantează potrivirea numerelor întregi \(n,m\) dacă \(T\) este un multiplu pozitiv al \(g\) . Relația pe care o cauți este::
$$na-mb=T.$$
Numerele \(n,m\) furnizate de Bézout pot fi inițial negative. Execuțiile negative nu pot fi efectuate. Totuși, se pot crește ambele numere fără a modifica intervalul de timp: le înlocuim cu \(n+kb/g\) și \(m+ka/g\) , unde \(k\) este un număr întreg pozitiv suficient de mare. Ambii timpi sunt deci deplasați cu aceeași cantitate \(kab/g\) ; diferența lor rămâne \(T\) . Deci ambele numere devin pozitive și timpii necesari sunt de fapt după pornirea ceasurilor.
Acum numărați ciclurile complete ale fiecărui ceas. Când al \(m\) ceas devine gol, începe măsurarea; se termină când primul ceas devine gol pentru a \(n\) -a oară. Există exact \(T\) unități de timp între ele. Pregătirea poate dura mult timp. Dovada nu promite un proces deosebit de scurt. Pentru \(T=0\) începutul și sfârșitul coincid. Acest lucru se dovedește pentru toate obiectivele întregi nenegative: cu pregătire, o durată poate fi măsurată dacă și numai dacă cel mai mare divizor comun o împarte:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Această regulă nu se aplică neapărat măsurătorilor de pornire chiar de la prima pornire. De exemplu, cu \(4\) și \(7\) minute \(g=1\) , dar după \(1\) minut niciun ceas nu este gol. Deci nu poți vedea sfârșitul acestui minut. Măsurătoarea de la minutul \(7\) la \(8\) descrisă mai sus funcționează doar pentru că preparatul nu contează. Dovada răspunde astfel la întrebarea ce este posibil după pregătire. Dacă sunteți în căutarea unui proces permis, cu sau fără pregătire, următoarea căutare sistematică vă va ajuta.
Scriptul PHP își amintește atât timpul de rulare rămas, cât și timpul scurs de la începutul măsurării. Pentru fiecare astfel de condiție, încercați totul \(4\) Posibilitati: fara ceas, doar primul, doar al doilea sau intoarceti ambele. Apoi așteaptă până data viitoare când se golește. Valoarea \(-1\) indică pregătire; intrarea start setează timpul de măsurare \(0\). Condițiile cunoscute nu vor fi re-investigate. Secvența găsită este obținută prin predecesorii săi. wait se referă doar la distanța până la următoarea golire, nu la o măsurare suplimentară a timpului:
<?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;
}
Căutarea găsește sau returnează un proces permis null, dacă nu există. Acoperă toate continuările permise și necesită un maxim de pregătire \((a+1)(b+1)(T+2)\) State. Prin urmare, intrările mari necesită multă memorie. Numărul de tranziții de căutare este minimizat, nu timpul de pregătire. Timpii raționali de rulare și țintă sunt convertiți în numere întregi folosind un numitor comun. Pentru durate fără o unitate de timp comună, de exemplu \(1\) și \(\sqrt{2}\), această căutare cu numere întregi finite nu este potrivită.