Kunezibuko zehora ezimbili: eyodwa igijima ngokuphelele emaminithini \(4\) , enye \(7\) amaminithi. Ulinganisa kanjani ngokunembile amaminithi \(9\) lapho ukulinganisa kufanele kuqale okokuqala ngqa amawashi? Elinye iwashi, ukubala imizuzwana nokuqagela akuvunyelwe. Okufanele ukwenze ukuvula izibuko zehora bese ubuka lapho igumbi eliphezulu lingenalutho. Ukuphenduka akufanele kuthathe noma nini. Esikufunayo yinqubo lapho ukuphela kwesikhathi esifiselekayo kungase kubonakale kuphela ngezibuko zehora.
Sibiza iwashi ngamaminithi \(4\) ngamaminithi \(A\) naleli elinamaminithi \(7\) \(B\) . Ekuqaleni sonke isihlabathi siphansi. Siqala womabili amawashi ngesikhathi esisodwa ngokuwaguqula; Kusukela kulo mzuzu kuya phambili \(9\) amaminithi okuseshwayo. Ngemuva kwalokho, ungahweba njalo lapho iwashi elingaphezulu lingenalutho. Akumele uvule iwashi elilodwa, elilodwa noma womabili, ngisho nelilodwa elisasebenza. Ulinda kuze kuphele isikhathi esilandelayo. Ukumisa nokumaka akuvunyelwe; iwashi elingenalutho lingahlala limile. Isixazululo sibukeka kanje:
- Ngomzuzu \(0\) \(A\) kanye \(B\) ziyaqalwa.
- Ngomzuzu \(4\) \(A\) ayinalutho futhi iyaphendukilwa. \(B\) iyaqhubeka nokusebenza ingashintshiwe.
- Ngomzuzu \(7\) \(B\) ayinalutho futhi iyaphendukilwa. Kuseneminithi \(1\) esele kokuthi \(A\) .
- Ngomzuzu \(8\) \(A\) ayinalutho. Ku \(B\) isihlabathi sehla isikhathi esiqondile \(1\) iminithi; ngakho-ke \(B\) iphendulwa ngokushesha futhi.
- Ngomzuzu \(9\) \(B\) ayinalutho. Isikhathi obusifuna sifinyelelwe.
Ngomzuzu \(8\) siphendulela iwashi \(B\) elisasebenza. Kusukela ziqale kabusha ngomzuzu \(7\) , ncamashi isihlabathi esiningi siye sagobhoza ngendlela esingangena ngayo ebhodleleni ngomzuzu \(1\) . Ngemva kokuphenduka, kuphela le mali encane engaphezulu. Manje kuthatha \(1\) iminithi ukuhlehlela phansi futhi. Ngakho-ke iwashi aliba nalutho ngomzuzu \(9\) , hhayi ngemva kokunye ukuqalisa okuphelele. Ngakho sikala umzuzu wokugcina ngesihlabathi esesivele sidlule. Opopayi bakhombisa lokhu mnyakazo:
Ukupheqa i-hourglass egijimayo nakho kuyasiza ngesixazululo esijwayelekile. Ngesikhathi esisele sisho isikhathi isihlabathi esadinga ukugeleza ngaso ekamelweni eliphezulu. Uma iwashi eligcwele linesikhathi sokusebenza \(c\) futhi isikhathi salo sokusebenza esisele sithi \(r\) , inani lesihlabathi esingezansi lihambisana nobude besikhathi \(cr\) . Uma uliphendula, leli nani lifika phezulu. Uma ikamelo eliphezulu ligcwele ngaphambili, lizoba lingenalutho kamuva futhi ngokuphambene nalokho. Ewashi eligijima kancane, isikhathi esisha esisele sokusebenza ngu \(r'\):
$$r'=c-r.$$
Ngaphambilini, ukulinganisa kwaqala ngejika lokuqala. Lokhu kusho ukuthi "ngaphandle kwesikhathi sokuhola": yonke iminithi kusukela ekuqaleni ibala. “Ngokuhamba kwesikhathi” kusho, ngakolunye uhlangothi, ukuthi ungalungisa amawashi kuqala futhi isikhathi osifunayo siqala kamuva. Isibonelo, siqala womabili amawashi futhi siphendule \(A\) ngaphezulu ngomzuzu \(4\) . Uma \(B\) iba ingenalutho ngomzuzu \(7\) , ukulinganisa kwethu kuyaqala. Uma \(A\) iba ingenalutho ngomzuzu \(8\) , iyaphela. Silinganise \(1\) iminithi; imizuzu \(7\) edlule ayibali.
Manje sicabangela izibuko zehora ezingafanele ezinenani eliphelele lezikhathi zokusebenza \(a\) kanye \(b\) . Sibiza ubude besikhathi esifunekayo \(T\) . Yiziphi izikhathi ezingakalwa ngalokhu uma ukulungiswa kuvunyelwe? Nalapha, isiqalo nesiphetho kumele sibonakale ngendawo engenalutho. Ngakho-ke akufanele uqale ukulinganisa ngesikhathi esithile ngokusekelwe emuzweni wakho. Izibambo zihlala zifana nephazili yangempela. Okokuqala sibonisa ukuthi yiziphi izikhathi ezingafakwanga; sizobe sesikukhombisa ukuthi ulinganisa kanjani konke okunye.
Okokuqala ake sithathe amawashi anemizuzu engu \(6\) kanye \(10\) ". Zombili izikhathi ezisebenzayo zihlukaniswa ngokuthi \(2\) . Ngakho-ke isihlabathi singahlukaniswa ngokwengqondo sibe izingxenye, ngayinye yazo ethatha \(2\) imizuzu ukudlula. Uma uyivula noma ulinda kuze kube yisikhathi esilandelayo lapho ingenalutho, izingxenye eziphelele kuphela ezidalekayo futhi. Ngakho-ke zonke izikhathi ezingenalutho ezibonakalayo ziyinani elilinganayo lemizuzu ngokwehlukana. Awukwazi ukuyisebenzisela ukukala ubude besikhathi \(3\) bamaminithi, noma ngabe ulungiselela amawashi isikhathi eside othanda ngaso ngaphambili.
Ngokuvamile, vumela \(g=\gcd(a,b)\) kube isahlukanisi esikhulu kunazo zonke sezikhathi ezisebenzayo. Ekuqaleni womabili amatemu asele ayiziphindaphinda ze \(g\) . Uma izungezisiwe \(r\) iba \(ar\) noma \(br\) ; kokubili kuhlala kuhlukaniswa ngu \(g\) . Uma ulindile, isikhathi esincane kunazo zonke esisele siyadlula, okuphinde kube ukuphindaphinda kokuthi \(g\) . Lokhu kusho ukuthi zonke izikhathi ezingenalutho namabanga azo kuhlala kuyiziphindaphinda ze \(g\) . Ngakho-ke ubude besikhathi obulinganisekayo kumelwe bunelise \(g\mid T\) : \(T\) kumelwe buhlukaniseke ngo \(g\) . Ukuthi sekwanele yini kusazobonakala.
Ukwenza lokhu, sivumela womabili amawashi ukuthi asebenze ngokuphindaphindiwe futhi siphendule ngalinye ngokushesha uma lingenalutho. Elokuqala libe selingenalutho ngemva kwamayunithi esikhathi \(a,2a,3a,\ldots\) , okwesibili ngemva kokuthi \(b,2b,3b,\ldots\) . Sibheke isikhathi \(mb\) sewashi lesibili nesikhathi sakamuva \(na\) esokuqala, okuphakathi kokuthi \(T\) elele khona. I-lemma ka-Bézout iqinisekisa izinombolo ezifanayo \(n,m\) uma \(T\) iyimpinda ephozithivu yokuthi \(g\) . Ubudlelwano obufunayo yibo::
$$na-mb=T.$$
Izinombolo \(n,m\) ezinikezwe i-Bézout zingaba negethivu ekuqaleni. Ukugijima okungalungile akukwazi ukwenziwa. Nokho, umuntu angakwazi ukwandisa zombili izinombolo ngaphandle kokushintsha isikhawu sesikhathi: sizishintsha ngo \(n+kb/g\) kanye nokuthi \(m+ka/g\) , lapho \(k\) iyinani elikhulu ngokwanele eliphozithivu. Ngakho-ke zombili izikhathi zishintshwa ngenani elifanayo \(kab/g\) ; umehluko wabo uhlala \(T\) . Ngakho-ke zombili izinombolo ziba phozithivu futhi izikhathi ezidingekayo empeleni zingemva kokuqala kwamawashi.
Manje ubala imijikelezo ephelele yewashi ngalinye. Lapho iwashi \(m\) liba lingenalutho isilinganiso siyaqala; liphela lapho iwashi lokuqala liba lingenalutho ngesikhathi \(n\) -th. Kukhona ncamashi \(T\) amayunithi esikhathi phakathi. Ukulungiselela kungathatha isikhathi eside. Ubufakazi abuthembisi inqubo emfushane kakhulu. Ku \(T=0\) isiqalo nesiphetho ziqondana. Lokhu kufakazela zonke izinhloso ezingezona ezimbi: Ngokulungiselela, ubude besikhathi bungalinganiswa uma futhi kuphela uma isihlukanisi esivamile sisehlukanisa.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Lo mthetho awusebenzi ekuqaliseni izilinganiso ekuqaleni nje. Isibonelo, ngamaminithi \(4\) kanye \(7\) \(g=1\) , kodwa ngemva \(1\) iminithi alikho iwashi elingenalutho. Ngakho awukwazi ukubona ukuphela kwalo mzuzu. Isilinganiso esisuka kuminithi \(7\) kuye kokuthi \(8\) esichazwe ngenhla sisebenza kuphela ngoba ukulungiswa akubalwa. Ngakho ubufakazi buphendula umbuzo wokuthi yini engenzeka ngemva kokulungiselela. Uma ufuna inqubo evunyelwe ngokulungiselela noma ngaphandle kwayo, ukusesha okuhlelekile okulandelayo kuzosiza.
Isikripthi se-PHP sikhumbula zombili izikhathi ezisele zokusebenza kanye nesikhathi esidlulile kusukela ekuqaleni kokulinganisa. Kuzo zonke izimo ezinjalo, zama konke \(4\) Amathuba: alikho iwashi, elokuqala kuphela, elesibili kuphela noma lijike zombili. Bese ilinda kuze kube yisikhathi esilandelayo lapho ithulula khona. Inani \(-1\) ikhombisa ukulungiselela; ukungena start usetha isikhathi sokulinganisa \(0\). Izimo ezaziwayo ngeke ziphinde ziphenywe. Ukulandelana okutholakele kutholwa ngabandulelayo. wait ibhekisela kuphela ebangeni lokuthulula okulandelayo, hhayi ukulinganisa isikhathi esengeziwe:
<?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;
}
Ukusesha kuthola noma kubuyisela inqubo evunyelwe null, uma engekho. Ihlanganisa konke ukuqhubeka okuvunyelwe futhi idinga ukulungiselelwa okuphezulu \((a+1)(b+1)(T+2)\) Amazwe. Ngakho-ke okokufaka okukhulu kudinga inkumbulo eningi. Inani loshintsho lokusesha lincishisiwe, hhayi isikhathi sokulungiselela. Ukusebenza okunengqondo nezikhathi eziqondiwe ziguqulwa zibe izinombolo eziphelele kusetshenziswa idinomineyitha efanayo. Okwezikhathi zokusebenza ngaphandle kweyunithi yesikhathi esivamile, isibonelo \(1\) futhi \(\sqrt{2}\), lolu sesho oluphelele alufanelekile.