Kukho iiglasi ezimbini zeyure: enye ibaleka ngokupheleleyo kwi \(4\) imizuzu, enye kwi \(7\) imizuzu. Umejarisha njani ngokuchanekileyo \(9\) imizuzu xa umlinganiselo kufuneka uqale kwixesha lokuqala iiwotshi ziqaliswa? Enye iwotshi, ukubala imizuzwana kunye nokuqikelela akuvumelekanga. Konke okufuneka ukwenze kukuguqula iiglasi zeyure kwaye ujonge xa igumbi eliphezulu lingenanto. Ukujika akufuneki kuthathe naliphi na ixesha. Into esiyifunayo yinkqubo apho ukuphela kwexesha elifunwayo kunokuqatshelwa kuphela ngeehourglasses.
Sibiza iwotshi ngemizuzu \(4\) ngemizuzu \(A\) kunye nale enemizuzu \(7\) yemizuzu \(B\) . Ekuqaleni yonke isanti isezantsi. Siqala zombini iiwotshi ngaxeshanye ngokuzijika; Ukususela kulo mzuzu ukuya phambili \(9\) imizuzu ephendliweyo. Emva koko, unokuhlala uthengisa xa iwotshi ephezulu ingenanto. Awunakujika iwotshi enye, enye okanye zombini, kwananye esasebenzayo. Ulinda de kube lixesha elizayo iphelile. Ukumisa nokumakishwa akuvumelekanga; iwotshi engenanto inokuhlala imile. Isisombululo sijongeka ngolu hlobo:
- Ngomzuzu \(0\) \(A\) kunye \(B\) ziqalisiwe.
- Ngomzuzu \(4\) \(A\) ayinanto kwaye ijingiwe. \(B\) iyaqhubeka ukubaleka ingatshintshanga.
- Ngomzuzu \(7\) \(B\) ayinanto kwaye ijingiwe. Kusekho \(1\) umzuzu oseleyo ku \(A\) .
- Ngomzuzu \(8\) \(A\) ayinanto. Kwi- \(B\) isanti yayiqengqeleka ngokuthe ngqo \(1\) umzuzu; ngoko ke \(B\) ijikwa kwakhona ngokukhawuleza.
- Ngomzuzu \(9\) \(B\) ayinanto. Ixesha ubulifuna lifikile.
Ngomzuzu \(8\) sijika iwotshi \(B\) esaqhubayo. Ukusukela ekuqaliseni kwazo kwakhona ngomzuzu \(7\) , ininzi intlabathi equkuqelayo ehlayo njengoko ibiya kungena kumbhobho ngomzuzu \(1\) . Emva kokuguquka, kuphela le mali encinci iphezulu. Ngoku ithatha \(1\) umzuzu ukuhla kwakhona. Iwotshi ke ngoko iba empty ngomzuzu \(9\) , hayi emva kolunye usebenziso olupheleleyo. Ngoko silinganisa umzuzu wokugqibela ngesanti esele idlulile. Oopopayi babonisa le ntshukumo:
Ukupeyinta ihourglass ebalekayo kukwaluncedo kwisisombululo ngokubanzi. Ngexesha eliseleyo sithetha ixesha esadinga ukuba isanti iqukuqele kwigumbi eliphezulu. Ukuba iwotshi epheleleyo inexesha elisebenzayo \(c\) kunye nexesha eliseleyo lokubaleka ngu \(r\) , ngoko isixa sesanti esezantsi sihambelana nobude bexesha \(cr\) . Xa uyijika, le mali ichanekileyo iza phezulu. Ukuba igumbi eliphezulu ligcwele ngaphambili, liya kuba lingenanto emva koko kwaye ngokuphambeneyo. Kwiwotshi eqhutywa ngokungagqibelelanga, ixesha elitsha eliseleyo lokubaleka ngu \(r'\):
$$r'=c-r.$$
Ngaphambili, umlinganiselo uqale ngejiko lokuqala. Oku kuthetha "ngaphandle kwexesha lokukhokela": yonke imzuzu ukususela ekuqaleni ibala. “Ngokuhamba kwangaphambili” kuthetha, kwelinye icala, ukuba unokulungiselela iiwotshi kuqala kwaye ixesha olifunayo liqala kamva. Umzekelo, siqala zombini iiwotshi kwaye sijika \(A\) ngaphezulu ngomzuzu \(4\) . Ukuba \(B\) iba empty ngomzuzu \(7\) , umlinganiselo wethu uqala. Ukuba \(A\) iba engenanto ngomzuzu \(8\) , iyaphela. Silinganise \(1\) umzuzu; eyedlulileyo \(7\) imizuzu ayibali.
Ngoku sithathela ingqalelo iiglasi zehourglass ezinenani elipheleleyo lamaxesha okubaleka \(a\) kunye \(b\) . Sibiza ixesha elifunekayo \(T\) . Ngawaphi amaxesha anokulinganiswa ngoku ukuba amalungiselelo avunyelwe? Apha kwakhona, isiqalo kunye nesiphelo kufuneka sibonakale ngesithuba esingenanto. Ngoko akufanele uqalise ukulinganisa ngexesha elithile ngokusekelwe kwimvakalelo yakho. Izibambo zihlala zifana nephazili yokwenyani. Okokuqala sibonisa ukuba ngawaphi amaxesha angabandakanywanga; emva koko siza kukubonisa indlela yokulinganisa zonke ezinye.
Okokuqala makhe sithathe iiwotshi ezine \(6\) kunye \(10\) nemizuzu. Omabini amaxesha asebenzayo ahlulwa nge \(2\) . Isanti ke ngoko ingqondo inokwahlulwa ibe ngamacandelo, ngalinye lithatha \(2\) imizuzu ukudlula. Xa uyijika okanye ulinde de kube lixesha elizayo ingenanto, kuphela izahlulo ezipheleleyo zidalwe kwakhona. Onke amaxesha abonakalayo angenanto ke ngoko alinani elilinganayo lemizuzu ngokwahlukeneyo. Awunakuyisebenzisa ukulinganisa ubude bexesha \(3\) imizuzu, nokuba ulungiselela iiwotshi ixesha elide njengoko uthanda ngaphambili.
Ngokubanzi, mayeke \(g=\gcd(a,b)\) ibe ngoyena mahluli uqhelekileyo wamaxesha okuqhuba. Ekuqaleni yomibini imigaqo eseleyo ziziphindaphindo ze \(g\) . Xa ijikeleziswa \(r\) iba yi \(ar\) okanye \(br\) ; zombini zihlala zahlulwa ngu \(g\) . Xa ulindile, elona xesha lincinci eliseleyo elilungileyo liyadlula, eliphinda-phinda-phinda \(g\) . Oku kuthetha ukuba onke amaxesha angenanto kunye nemigama yabo ihlala iziphindaphindo ze \(g\) . Ubude bexesha elinokulinganiswa kufuneka ke ngoko lanelise \(g\mid T\) : \(T\) kufuneka lahlulwe ngo \(g\) . Ukuba oko kwanele kusaza kubonakala.
Ukwenza oku, sivumela iiwotshi zombini ziqhube ngokupheleleyo kwaye kwakhona kwaye siguqule nganye nganye ngokukhawuleza ukuba ingenanto. Eyokuqala ke ingabi nanto emva kweeyunithi zexesha \(a,2a,3a,\ldots\) , eyesibini emva \(b,2b,3b,\ldots\) . Sijonge ixesha \(mb\) lewotshi yesibini nexesha lamva \(na\) elokuqala, apho kanye \(T\) elele phakathi kwayo. I-lemma ka-Bézout iqinisekisa amanani apheleleyo \(n,m\) ukuba \(T\) isiphinda-phinda esivumayo sika \(g\) . Ubudlelwane obukhangelayo bu::
$$na-mb=T.$$
Amanani \(n,m\) anikezelwe ngu Bézout anokuba negative ekuqaleni. Ubaleko olubi alunakuqhutywa. Nangona kunjalo, umntu unokuwanyusa omabini amanani ngaphandle kokutshintsha isithuba sexesha: sibeka endaweni yawo \(n+kb/g\) kunye \(m+ka/g\) , apho \(k\) iyinani elikhulu ngokwaneleyo elidibanisayo. Omabini amaxesha ke ngoko ashenxiswa ngesixa esifanayo \(kab/g\) ; umahluko wabo uhlala \(T\) . Ngoko ke omabini la manani ahamba kakuhle kwaye amaxesha afunekayo asemva kokuba iiwotshi ziqalile.
Ngoku ubala imijikelo epheleleyo yewotshi nganye. Xa iwotshi \(m\) ingenamntu umlinganiselo uyaqala; iyaphela xa iwotshi yokuqala ingenanto ye \(n\) -th ixesha. Kukho kanye \(T\) iiyunithi zexesha phakathi. Ukulungiselela kunokuthatha ixesha elide. Ubungqina abuthembisi inkqubo emfutshane ngokukodwa. Kuba \(T=0\) isiqalo nesiphelo ziyangqinelana. Oku kungqina kuzo zonke iinjongo ezipheleleyo ezingezizo ezigxekayo: Ngokulungiselela, ubude bexesha bunokulinganiswa ukuba kwaye kuphela ukuba elona candelo liqhelekileyo liyahlulahlula.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Lo mgaqo awusebenzi ekuqaliseni imilinganiselo kanye ekuqaleni kokuqala. Umzekelo, kunye \(4\) kunye \(7\) imizuzu \(g=1\) , kodwa emva komzuzu \(1\) akukho iwotshi ingenanto. Ngoko awukwazi ukubona ukuphela kwalo mzuzu. Umlinganiselo ukusuka kumzuzu \(7\) ukuya ku \(8\) ochazwe ngasentla usebenza kuphela kuba ulungiselelo alubali. Ubungqina ke buphendula umbuzo wento enokwenzeka emva kolungiselelo. Ukuba ukhangela inkqubo evunyelweyo kunye okanye ngaphandle kwamalungiselelo, olu phando lulandelayo luya kunceda.
Iskripthi se-PHP sikhumbula omabini amaxesha aseleyo asebenzayo kunye nexesha eligqithileyo ukususela ekuqaleni komlinganiselo. Kuyo yonke imeko enjalo, zama konke \(4\) Amathuba: akukho wotshi, eyokuqala kuphela, eyesibini kuphela okanye ijike zombini. Ithi ke ilinde kude kube lixesha elizayo xa ikhupha. Ixabiso \(-1\) ibonisa ukulungiselela; ukungena start ibeka ixesha lomlinganiselo \(0\). Iimeko ezaziwayo aziyi kuphinda ziphandwe. Ulandelelwano olufunyenweyo lufunyanwa ngokusebenzisa abandulelayo. wait ibhekisa kuphela kumgama wokukhupha okulandelayo, hayi umlinganiselo wexesha elongezelelweyo:
<?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;
}
Uphendlo lufumana okanye lubuyisela inkqubo evunyelweyo null, ukuba akukho nanye. Iquka konke ukuqhubeka okuvunyelweyo kwaye ifuna ubuninzi bamalungiselelo \((a+1)(b+1)(T+2)\) States. Amagalelo amakhulu ke ngoko afuna inkumbulo eninzi. Inani lotshintsho lokukhangela lincitshisiwe, hayi ixesha lokulungiselela. Ukubaleka okusengqiqweni kunye namaxesha ekujoliswe kuwo aguqulwa abe ngamanani apheleleyo kusetyenziswa idinomineyitha efanayo. Ngamaxesha okuqhuba ngaphandle kweyunithi yexesha eliqhelekileyo, umzekelo \(1\) kwaye \(\sqrt{2}\), olu khangelo lupheleleyo alufanelekanga.