Ka dy orë rëre: njëra funksionon plotësisht për \(4\) minuta, tjetra për \(7\) minuta. Si i matni saktësisht \(9\) minutat kur matja duhet të fillojë herën e parë që nisin orët? Një orë tjetër, numërimi i sekondave dhe hamendja nuk lejohen. Gjithçka që duhet të bëni është të ktheni orët e rërës dhe të shikoni kur dhoma e sipërme të jetë bosh. Kthimi nuk duhet të marrë kohë. Ajo që ne po kërkojmë është një proces në të cilin fundi i periudhës së dëshiruar kohore mund të njihet vetëm nga orët e rërës.
Orën me \(4\) minuta e quajmë \(A\) dhe atë me \(7\) minuta \(B\) . Fillimisht e gjithë rëra është në fund. I nisim të dyja orët në të njëjtën kohë duke i kthyer nga ana e tyre; Nga ky moment e tutje llogariten \(9\) minutat e kërkuara. Pas kësaj, gjithmonë mund të tregtoni kur një orë në krye bëhet bosh. Ju nuk mund të ktheni njërën, njërën ose të dyja orët, madje edhe njërën që është ende në punë. Ju prisni deri herën tjetër që të mbarojë. Ndalimi dhe shënimi nuk lejohen; një orë bosh mund të qëndrojë në këmbë. Zgjidhja duket si kjo:
- Në minutën \(0\) \(A\) dhe \(B\) fillojnë.
- Në minutën \(4\) \(A\) është bosh dhe është kthyer. \(B\) vazhdon të funksionojë e pandryshuar.
- Në minutën \(7\) \(B\) është bosh dhe është kthyer. Ka mbetur ende \(1\) minutë në \(A\) .
- Në minutën \(8\) \(A\) është bosh. Në \(B\) rëra u rrëzua për saktësisht \(1\) minutë; prandaj \(B\) kthehet menjëherë përsëri.
- Në minutën \(9\) \(B\) është bosh. Koha që po kërkoni është arritur.
Në minutën \(8\) e kthejmë orën \(B\) e cila është ende në punë. Që nga rifillimi i tyre në minutën \(7\) , ka rrjedhur po aq rërë sa do të futej nëpër grykë të ngushtë në \(1\) minutë. Pas kthimit, vetëm kjo sasi e vogël është sipër. Tani duhet \(1\) minutë për të rrjedhur përsëri. Prandaj, ora zbrazet në minutën \(9\) , jo pas një ekzekutimi tjetër të plotë. Pra, ne matim minutën e fundit me rërë që tashmë ka kaluar. Animacioni tregon këtë lëvizje:
Rrotullimi i orës së rërës është gjithashtu i dobishëm për zgjidhjen e përgjithshme. Me kohë të mbetur nënkuptojmë kohën në të cilën rëra ende duhet të rrjedhë në dhomën e sipërme. Nëse ora e plotë ka kohën e funksionimit \(c\) dhe koha e mbetur e funksionimit është \(r\) , atëherë sasia e rërës në fund korrespondon me kohëzgjatjen \(cr\) . Kur e ktheni, kjo sasi e saktë vjen në krye. Nëse dhoma e sipërme është plot paraprakisht, ajo do të zbrazet më pas dhe anasjelltas. Për një orë të drejtuar pjesërisht, koha e re e mbetur e funksionimit është \(r'\):
$$r'=c-r.$$
Më parë, matja fillonte me kthesën e parë. Kjo do të thotë "pa kohë të parë": çdo minutë që nga fillimi vlen. "Me paradhënie" do të thotë, nga ana tjetër, që fillimisht mund të përgatisni orët dhe periudha e dëshiruar kohore fillon më vonë. Për shembull, ne i nisim të dy orët dhe e kthejmë \(A\) në minutën \(4\) . Nëse \(B\) bëhet bosh në minutën \(7\) , matja jonë fillon. Nëse \(A\) bëhet bosh në minutën \(8\) , ai përfundon. Ne matëm \(1\) minutë; minutat e mëparshme \(7\) nuk llogariten.
Tani marrim parasysh orë rëre arbitrare me kohë funksionimi me numra të plotë \(a\) dhe \(b\) . Ne e quajmë kohëzgjatjen e dëshiruar \(T\) . Sa kohë mund të maten me këtë nëse lejohet përgatitja? Edhe këtu fillimi dhe fundi duhet të dallohen nga një hapësirë boshe. Pra, nuk duhet të filloni të matni në një moment bazuar në ndjenjën tuaj. Dorezat mbeten të njëjta si në enigmën aktuale. Së pari tregojmë se cilat kohë janë të përjashtuara; atëherë ne do t'ju tregojmë se si të matni në të vërtetë gjithë pjesën tjetër.
Së pari, le të marrim orët me \(6\) dhe \(10\) minuta. Të dyja kohët e ekzekutimit janë të pjestueshme me \(2\) . Prandaj, rëra mund të ndahet mendërisht në pjesë, secila prej të cilave kërkon \(2\) minuta për t'u kaluar. Kur e ktheni ose prisni derisa herën tjetër të zbrazet, krijohen përsëri vetëm pjesë të tëra. Prandaj, të gjitha kohët boshe të vëzhgueshme janë një numër çift minutash larg njëra-tjetrës. Ju nuk mund ta përdorni atë për të matur një kohëzgjatje prej \(3\) minutash, edhe nëse i përgatitni orët për aq kohë sa të doni më parë.
Në përgjithësi, le të jetë \(g=\gcd(a,b)\) pjesëtuesi më i madh i përbashkët i kohërave të ekzekutimit. Fillimisht të dy termat e mbetur janë shumëfish të \(g\) . Kur rrotullohet \(r\) bëhet ose \(ar\) ose \(br\) ; të dyja mbeten të pjesëtueshme me \(g\) . Gjatë pritjes, kalon koha më e vogël pozitive e mbetur, e cila është gjithashtu një shumëfish i \(g\) . Kjo do të thotë që të gjitha kohët boshe dhe distancat e tyre mbeten shumëfish të \(g\) . Prandaj, një kohëzgjatje e matshme duhet të plotësojë \(g\mid T\) : \(T\) duhet të ndahet me \(g\) . Se a mjafton kjo mbetet për t'u parë.
Për ta bërë këtë, ne i lëmë të dy orët të punojnë përsëri dhe përsëri dhe e kthejmë secilën prej tyre sapo të zbrazet. E para pastaj bëhet bosh pas \(a,2a,3a,\ldots\) njësive kohore, e dyta pas \(b,2b,3b,\ldots\) . Ne po kërkojmë një kohë \(mb\) të orës së dytë dhe një kohë të mëvonshme \(na\) të së parës, midis së cilës ndodhet saktësisht \(T\) . Lema e Bézout garanton përputhjen e numrave të plotë \(n,m\) nëse \(T\) është një shumëfish pozitiv i \(g\) . Marrëdhënia që kërkoni është::
$$na-mb=T.$$
Numrat \(n,m\) të dhënë nga Bézout fillimisht mund të jenë negativë. Vrapimet negative nuk mund të kryhen. Megjithatë, mund të rriten të dy numrat pa ndryshuar intervalin kohor: i zëvendësojmë me \(n+kb/g\) dhe \(m+ka/g\) , ku \(k\) është një numër i plotë pozitiv mjaftueshëm i madh. Prandaj të dyja kohët zhvendosen me të njëjtën sasi \(kab/g\) ; dallimi i tyre mbetet \(T\) . Pra, të dy numrat bëhen pozitivë dhe kohët e kërkuara janë në fakt pas fillimit të orës.
Tani ju numëroni ciklet e plota të secilës orë. Kur ora e \(m\) zbrazet, fillon matja; përfundon kur ora e parë zbrazet për herën \(n\) -të. Ka saktësisht \(T\) njësi kohore në mes. Përgatitja mund të zgjasë shumë. Prova nuk premton një proces veçanërisht të shkurtër. Për \(T=0\) fillimi dhe fundi përkojnë. Kjo vërtetohet për të gjithë objektivat e numrave të plotë jo negativë: me përgatitjen, një kohëzgjatje mund të matet nëse dhe vetëm nëse pjesëtuesi më i madh i përbashkët e ndan atë:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Ky rregull nuk zbatohet domosdoshmërisht për fillimin e matjeve që në fillimin e parë. Për shembull, me \(4\) dhe \(7\) minuta \(g=1\) , por pas \(1\) minutë asnjë orë nuk është bosh. Kështu që ju nuk mund ta shihni fundin e kësaj minute. Matja nga minuta \(7\) në \(8\) e përshkruar më sipër funksionon vetëm sepse përgatitja nuk llogaritet. Pra, prova i përgjigjet pyetjes se çfarë është e mundur pas përgatitjes. Nëse jeni duke kërkuar për një proces të lejuar me ose pa përgatitje, kërkimi sistematik i mëposhtëm do t'ju ndihmojë.
Skripti PHP kujton kohët e mbetura të ekzekutimit dhe kohën që ka kaluar që nga fillimi i matjes. Për çdo kusht të tillë, provoni të gjitha \(4\) Mundësitë: pa orë, vetëm e para, vetëm e dyta ose ktheni të dyja. Më pas pret deri herën tjetër që të zbrazet. Vlera \(-1\) tregon përgatitjen; hyrjen start cakton kohën e matjes \(0\). Kushtet e njohura nuk do të rihetohen. Sekuenca e gjetur është marrë nëpërmjet paraardhësve të saj. wait i referohet vetëm distancës deri në zbrazjen tjetër, jo një matje shtesë të kohës:
<?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;
}
Kërkimi gjen ose kthen një proces të lejuar null, nëse asnjë nuk ekziston. Ai mbulon të gjitha vazhdimet e lejuara dhe kërkon një përgatitje maksimale \((a+1)(b+1)(T+2)\) Shtetet. Prandaj, hyrjet e mëdha kërkojnë shumë memorie. Numri i tranzicioneve të kërkimit është minimizuar, jo koha e përgatitjes. Vrapimi racional dhe koha e synuar konvertohen në numra të plotë duke përdorur një emërues të përbashkët. Për kohëzgjatje pa një njësi të përbashkët kohore, për shembull \(1\) dhe \(\sqrt{2}\), ky kërkim me numër të plotë të fundëm nuk është i përshtatshëm.