Duae clepsydrae sunt: una in minutis \(4\) \(7\) currit, altera in minutis. Quomodo metiaris minutas \(9\) minutas cum mensurae initium habet primum horologiorum? Horologium aliud, secundis computatis et coniecturare non licet. Omnia quae facienda sunt, in gyros convertunt et speculantur ubi cenaculum vacuum est. Conversus nullum tempus capere debet. Quod quaerimus est processus, quo finis desiderati temporis spatium solum per clepsydras agnosci potest.
Horologium vocamus cum minutis \(4\) \(A\) et unum cum minutis \(B\) \(7\) . Initio omnis arena in fundo est. Horologiorum simul utrosque incipimus vertendo; Ex hoc momento deinceps minuta computata \(9\) numerant. Post hoc semper mercari potes cum horologium in summo fit vacuum. Non licet unam, alteramque horologiorum, etiam currentem. Expectas donec iterum absumitur. Obstare et notare non licet; horologium inane stare potest. Solutio similis est:
- Minutatim incipiunt \(0\) \(A\) et \(B\) .
- Minutatim \(4\) \(A\) vacua est et flipped. \(B\) immota pergit currere.
- Minuta \(7\) \(B\) vacua est et flipped. Est \(1\) minute relicto in \(A\) .
- Minuta \(8\) \(A\) vacua est. in \(B\) arena decurrit pro exacte \(1\) momento; ergo \(B\) statim iterum retorquetur.
- Minuta \(9\) \(B\) vacua est. Tempus petebas ventum.
In momento horologii \(B\) \(8\) quod adhuc currit. Cum eorum sileo minutos \(7\) , tantumdem arenae defluxisse quam per bottleneck in momento \(1\) aptaret. Post haec tantum parva superne est. Nunc minutum \(1\) accipit ut iterum manare. Itaque horologium \(9\) tempore vacuum fit, non post aliud spatium temporis. Extremum igitur minutum metimur arena quae iam pertransiit. Animatio hoc ostendit motum:
Ad solutionem generalem quoque utilis est flipping per clepsydram currens. Remanendo tempus significamus tempus quo arena etiamnum in superiori conclavi transfluat. Si horologium plenum tempus currit \(c\) et reliquum tempus currit \(r\) habet, tunc quantitas arenae in fundo respondet durationi \(cr\) . Cum verteris, haec simplum ad cacumen venit. Si cenaculum ante plenum fuerit, postea et e converso erit vacuum. Ex parte horologii currit, novum tempus currens reliquum est \(r'\):
$$r'=c-r.$$
Antea mensuræ incepit a primo tractu. Hoc significat “sine plumbo tempus”: omne momentum ex quo initium duco. "Procede" significat e contra, quod horologia prius parare possis, et tempus optatum postea incipit. Exempli causa, horologiorum tam \(A\) quam minutatim \(4\) incipiunt . Si minuto \(7\) \(B\) vacet, incipit mensura nostra. Si minuto \(8\) \(A\) , finitur. Nos metiri \(1\) minute; prior \(7\) minuta non computat.
Nunc clepsydras arbitrarias positivis integris temporibus \(a\) et \(b\) consideramus. Desideratam vocamus durationem \(T\) . Qualia tempora metiri possunt, si praeparatio conceditur? Hic quoque principium et finis cognoscibilia debent spatio vacuo. Ita non debes metiri in aliquo loco secundum affectum tuum. Auriculae manent eadem quae in ipsa aenigmate. Primo ostendit quae tempora excluduntur. tunc tibi demonstrabimus quomodo reliqua omnia metiaris.
Primum cum horologiis \(6\) et minutis \(10\) sumamus. Utraque tempora cursus divisibilia sunt per \(2\) . Harena igitur mentis dividi potest in partes, quarum singulae minutae \(2\) attingunt. Cum convertas vel expecta postero tempore vacuum est, solum integrae partes iterum creantur. Omnia tempora vacua observata sunt ergo par minutarum numerorum. Non potes ea uti durationem minutorum \(3\) metiri, etiam si horologia tamdiu praeparaveris quamdiu voles ante.
\(g=\gcd(a,b)\) in communi divisor maximus temporum cursus. Initio et reliqui termini multiplicati sunt \(g\) . Quando rotatur \(r\) fit vel \(ar\) vel \(br\) ; utrumque manent divisibile per \(g\) . Cum expectatur, minimum temporis positivum reliquum intercedit, quod etiam multiplex est \(g\) . Hoc significat omnia tempora vacua et earum intervalla multiplicationes \(g\) . Duratio igitur mensurabilis \(g\mid T\) satisfacere debet : \(T\) divisibilis per \(g\) . Id satis videndum an.
Ad hoc faciendum horologiorum tam identidem curritur, quamque quamprimum vacuum est, singula vertamus. Prima igitur post \(a,2a,3a,\ldots\) temporis unitates vacua fit, secunda post \(b,2b,3b,\ldots\) . Quaerimus tempus secundae horologii et posterioris temporis \(mb\) \(na\) primae, inter quod \(T\) iacet. Lemma Bezout spondet congruentes integri \(n,m\) si \(T\) multiplex positivus est e \(g\) . In relatione quam quaeritis est::
$$na-mb=T.$$
Numeri \(n,m\) suppleti a Bézout initio negativi possunt esse. Negans fugit expleri non potest. Potest tamen utrumque numerum augere sine temporis intervallo mutato: substituimus eos \(n+kb/g\) et \(m+ka/g\) , ubi \(k\) satis magnum est integrum affirmativum. Moventur ergo utraque tempora tantundem \(kab/g\) ; earum differentia manet \(T\) . Itaque ambo numeri positivi facti sunt et tempora requisita actu post horologiorum incipiunt.
Nunc integros cuiusque horologii cyclos numeras. Ubi \(m\) horologium evacuatur, incipit mensura; desinit cum primum horologium vacuum fit ad tempus \(n\) -th. Unitates temporis interpositae sunt exacte \(T\) . Praeparatio diu potest capere. Probatio non promittit processum brevem particularem. \(T=0\) principium et finis coincidunt. Hoc probat pro omnibus propositis integris non negativis: Praeparatione, duratio metiri potest si et solum si maximus divisor communis dividit eam.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Haec regula non necessario applicatur ad mensuras incipiendas ab initio primo. Exempli gratia, minutis \(4\) et \(7\) \(g=1\) , sed post \(1\) minutis horologium nullum vacuum est. Finem igitur huius minuti videre non potes. Mensura a minute \(7\) ad \(8\) supra scripta opera tantum est, quia praeparatio non numerat. Probatur sic: respondet quaestioni de possibili post praeparationem. Si processum licitum cum vel sine praeparatione quaerimus, sequens systematica inquisitio adiuvabit.
Scriptum PHP meminit tam reliquorum temporum cursus quam temporis elapsum ab initio mensurae. Pro omni conditione, experire omnia \(4\) Facultates: horologium nullum, modo primum, modo secundum, vel utrumque super. Hoc deinde expectat, donec iterum exinaniat. Valor \(-1\) praeparationem indicat; ingressum start mensurae tempus \(0\). Notae condiciones non erunt re-investigatae. Consequentia inventa habetur via praedecessorum suorum. wait tantum spatium ad proximum exinanitionem, non addito tempore mensurae:
<?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;
}
Investigatio invenit vel redit permissam processum null, si nulla sit. Omnes continuationes permissas contegit ac maximam praeparationis requirit \((a+1)(b+1)(T+2)\) Civitas. Magnae igitur inputationes multum memoriam requirunt. Numerus transitus quaerendi minimus est, non tempus praeparationis. Rationalis cursus et scopum tempora convertuntur in numeros integros utentes denominatore communi. Pro runtime sine tempore communi, e.g \(1\) et \(\sqrt{2}\), hic finitus numerus integer inquisitionis non convenit.