Estas du sablohorloĝoj: unu funkcias tute en \(4\) minutoj, la alia en \(7\) minutoj. Kiel oni mezuras precize \(9\) minutojn kiam la mezurado devas komenciĝi la unuan fojon kiam la horloĝoj estas komencitaj? Alia horloĝo, kalkulado de sekundoj kaj divenado ne estas permesitaj. Vi nur devas turni la sablohorloĝojn kaj rigardi kiam la supra ĉambro estas malplena. Turniĝi ne devus preni ajnan tempon. Kion ni serĉas estas procezo, en kiu la fino de la dezirata tempodaŭro povas esti rekonita nur per la sablohorloĝoj.
Ni nomas la horloĝon kun \(4\) minutoj \(A\) kaj tiun kun \(7\) minutoj \(B\) . Komence la tuta sablo estas ĉe la fundo. Ni startigas ambaŭ horloĝojn samtempe renversante ilin; Ekde ĉi tiu momento la serĉataj \(9\) minutoj kalkulas. Post tio, vi ĉiam povas komerci kiam horloĝo ĉe la supro malplenas. Vi eble ne turnas unu, unu aŭ ambaŭ horloĝojn, eĉ unu, kiu ankoraŭ funkcias. Vi atendu ĝis la venonta fojo, kiam ĝi finiĝos. Halti kaj marki ne estas permesitaj; malplena horloĝo povas resti staranta. La solvo aspektas tiel:
- Je la minuto \(0\) \(A\) kaj \(B\) estas komencitaj.
- Je la minuto \(4\) \(A\) estas malplena kaj estas renversita. \(B\) daŭre funkcias senŝanĝe.
- Je la minuto \(7\) \(B\) estas malplena kaj estas renversita. Restas ankoraŭ \(1\) minuto en \(A\) .
- Je minuto \(8\) \(A\) estas malplena. En \(B\) sablo kuris malsupren ekzakte \(1\) minuto; tial \(B\) tuj denove turniĝas.
- Je la minuto \(9\) \(B\) estas malplena. La tempo, kiun vi serĉis, estas atingita.
Je la minuto \(8\) ni turnas la horloĝon \(B\) kiu ankoraŭ funkcias. Ekde ilia rekomenco je minuto \(7\) , ekzakte tiom da sablo fluis malsupren, kiom taŭgus tra la botelkolo en \(1\) minuto. Post turniĝo, nur ĉi tiu malgranda kvanto estas supre. Nun necesas \(1\) minuto por flui denove. La horloĝo do malplenas je la minuto \(9\) , ne post alia kompleta kuro. Do ni mezuras la lastan minuton per sablo, kiu jam trapasis. La animacio montras ĉi tiun movon:
Ŝanĝi kurantan sablohorloĝon ankaŭ estas utila por la ĝenerala solvo. Per restanta tempo ni celas la tempon, kiun la sablo ankoraŭ bezonas traflui en la supra ĉambro. Se la plena horloĝo havas la rultempon \(c\) kaj ĝia restanta rultempo estas \(r\) , tiam la kvanto da sablo ĉe la fundo respondas al la daŭro \(cr\) . Kiam vi turnas ĝin, ĉi tiu ĝusta kvanto venas al la supro. Se la supra ĉambro estas plena antaŭe, ĝi estos malplena poste kaj inverse. Por parte funkciiga horloĝo, la nova restanta rultempo estas \(r'\):
$$r'=c-r.$$
Antaŭe, la mezurado komenciĝis per la unua turno. Ĉi tio signifas "sen plumbotempo": ĉiu minuto ekde la komenco kalkulas. "Kun anticipo" signifas, aliflanke, ke vi povas prepari la horloĝojn unue kaj la dezirata tempoperiodo komenciĝas poste. Ekzemple, ni startas ambaŭ horloĝojn kaj turnas \(A\) je la minuto \(4\) . Se \(B\) malplenas je la minuto \(7\) , nia mezurado komenciĝas. Se \(A\) malplenas je minuto \(8\) , ĝi finiĝas. Ni mezuris \(1\) minuton; la antaŭaj \(7\) minutoj ne kalkulas.
Nun ni konsideras arbitrajn sablohorloĝojn kun pozitivaj entjeraj kurantaj tempoj \(a\) kaj \(b\) . Ni nomas la deziratan daŭron \(T\) . Kiujn tempojn oni povas mezuri per ĉi tio se preparo estas permesita? Ankaŭ ĉi tie la komenco kaj fino devas esti rekoneblaj per malplena spaco. Do vi ne devus komenci mezuri iam laŭ via sento. La teniloj restas la samaj kiel en la fakta enigmo. Unue ni montras, kiuj tempoj estas ekskluditaj; tiam ni montros al vi kiel efektive mezuri la tutan ceterajn.
Unue ni prenu horloĝojn kun \(6\) kaj \(10\) minutoj. Ambaŭ rultempoj estas divideblaj per \(2\) . La sablo do povas esti mense dividita en partojn, el kiuj ĉiu bezonas \(2\) minutojn por trairi. Kiam vi turnas ĝin aŭ atendas ĝis la venonta tempo ĝi estas malplena, nur tutaj partoj estas kreitaj denove. Ĉiuj observeblaj malplenaj tempoj estas do para nombro da minutoj dise. Vi ne povas uzi ĝin por mezuri daŭron de \(3\) minutoj, eĉ se vi preparas la horloĝojn tiom longe kiom vi volas antaŭe.
Ĝenerale, estu \(g=\gcd(a,b)\) la plej granda komuna dividanto de la kurantaj tempoj. Komence ambaŭ ceteraj terminoj estas multobloj de \(g\) . Kiam oni turnas \(r\) fariĝas aŭ \(ar\) aŭ \(br\) ; ambaŭ restas divideblaj per \(g\) . Atendante, la plej malgranda pozitiva restanta tempo pasas, kiu ankaŭ estas oblo de \(g\) . Ĉi tio signifas, ke ĉiuj malplenaj tempoj kaj iliaj distancoj restas multobloj de \(g\) . Mezurebla daŭro devas do kontentigi \(g\mid T\) : \(T\) devas esti dividebla per \(g\) . Ĉu tio sufiĉas, restas por vidi.
Por fari tion, ni lasas ambaŭ horloĝojn plene funkcii denove kaj denove kaj turnas ĉiun tuj kiam ĝi estas malplena. La unua tiam iĝas malplena post \(a,2a,3a,\ldots\) tempounuoj, la dua post \(b,2b,3b,\ldots\) . Ni serĉas tempon \(mb\) de la dua horloĝo kaj postan tempon \(na\) de la unua, inter kiuj ĝuste \(T\) kuŝas. La lemo de Bézout garantias kongruajn entjerojn \(n,m\) se \(T\) estas pozitiva oblo de \(g\) . La rilato, kiun vi serĉas, estas::
$$na-mb=T.$$
La nombroj \(n,m\) provizitaj de Bézout povas komence esti negativaj. Negativaj kuroj ne povas esti faritaj. Tamen oni povas pliigi ambaŭ nombrojn sen ŝanĝi la tempintervalon: ni anstataŭigas ilin per \(n+kb/g\) kaj \(m+ka/g\) , kie \(k\) estas sufiĉe granda pozitiva entjero. Ambaŭ tempoj estas do movataj je la sama kvanto \(kab/g\) ; ilia diferenco restas \(T\) . Do ambaŭ nombroj iĝas pozitivaj kaj la bezonataj tempoj estas fakte post kiam la horloĝoj komenciĝas.
Nun vi kalkulas la kompletajn ciklojn de ĉiu horloĝo. Kiam la \(m\) horloĝo malplenas la mezurado komenciĝas; ĝi finiĝas kiam la unua horloĝo malplenas por la \(n\) -a fojo. Estas ĝuste \(T\) tempounuoj intere. La preparado povas daŭri longan tempon. La pruvo ne promesas precipe mallongan procezon. Por \(T=0\) la komenco kaj fino koincidas. Tio pruvas por ĉiuj nenegativaj entjerceloj: Kun preparo, daŭro povas esti mezurita se kaj nur se la plej granda komuna dividanto dividas ĝin:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Ĉi tiu regulo ne nepre validas por komenci mezuradojn ĝuste ĉe la unua komenco. Ekzemple, kun \(4\) kaj \(7\) minutoj \(g=1\) , sed post \(1\) minuto neniu horloĝo estas malplena. Do vi ne povas vidi la finon de ĉi tiu minuto. La mezurado de minuto \(7\) ĝis \(8\) priskribita supre funkcias nur ĉar la preparo ne kalkulas. La pruvo tiel respondas la demandon, kio eblas post preparado. Se vi serĉas permesitan procezon kun aŭ sen preparo, la sekva sistema serĉo helpos.
La PHP-skripto memoras ambaŭ ceterajn rultempojn kaj la tempon, kiu pasis ekde la komenco de la mezurado. Por ĉiu tia kondiĉo, provu ĉion \(4\) Ebloj: neniu horloĝo, nur la unua, nur la dua aŭ turni ambaŭ. Ĝi tiam atendas ĝis la venonta tempo kiam ĝi malpleniĝos. La valoro \(-1\) indikas preparon; la eniro start fiksas la mezuran tempon \(0\). Konataj kondiĉoj ne estos denove esploritaj. La sekvenco trovita estas akirita per siaj antaŭuloj. wait nur rilatas al la distanco al la sekva malplenigo, ne aldona tempomezurado:
<?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;
}
La serĉo trovas aŭ resendas permesitan procezon null, se neniu ekzistas. Ĝi kovras ĉiujn permesitajn daŭrigojn kaj postulas maksimumon de preparado \((a+1)(b+1)(T+2)\) Ŝtatoj. Grandaj enigaĵoj do postulas multan memoron. La nombro da serĉaj transiroj estas minimumigita, ne la prepartempo. Racia kurado kaj celtempoj estas konvertitaj en tutajn nombrojn uzante komunan denominatoron. Por rultempoj sen komuna tempounuo, ekzemple \(1\) kaj \(\sqrt{2}\), tiu ĉi finia entjerserĉo ne taŭgas.