Waxa jira laba muraayadood: mid si buuxda ayuu u shaqeeyaa \(4\) daqiiqo, kan kalena \(7\) daqiiqo. Sideed u cabbirtaa sida saxda ah \(9\) daqiiqo marka cabbirku bilaabmo marka ugu horreysa ee saacadaha la bilaabo? Saacad kale, tirinta ilbiriqsi iyo qiyaas lama ogola. Waxa kaliya ee ay tahay inaad sameyso waa inaad rogtaa muraayadaha saacadaha oo aad daawato marka qolka sare uu madhan yahay. Soo-jeedinta waa inaysan qaadan waqti. Waxa aanu raadinayno waa hannaan kaas oo dhamaadka wakhtiga la rabo lagu aqoonsan karo oo keliya muraayadaha saacadaha.
Waxaan u yeernaa saacadda leh \(4\) daqiiqo \(A\) iyo tan leh \(7\) daqiiqo \(B\) . Ugu horrayn dhammaan ciiddu waxay taallaa xagga hoose. Labada saacadoodba isku mar ayaynu ku bilownaa anagoo rogaya; Laga bilaabo wakhtigan wixii ka dambeeya waxaa la tiriyaa daqiiqadaha la raadiyey \(9\) . Taas ka dib, waxaad had iyo jeer ka ganacsan kartaa marka saacadda ugu sareysa ay noqoto mid madhan. Waxaa laga yaabaa inaadan rogin hal, hal ama labadaba, xitaa mid weli socda. Waxaad sugaysaa ilaa wakhtiga xiga ee uu dhammaanayo. Lama ogola joojinta iyo calaamadaynta; saacad madhan ayaa taagnaan karta. Xalku wuxuu u egyahay sidan:
- Daqiiqada \(0\) \(A\) iyo \(B\) ayaa bilaabanaya.
- Daqiiqada \(4\) \(A\) waa madhan oo waa la rogrogay. \(B\) waxay ku socotaa socodsiinta isma bedelin.
- Daqiiqaddii \(7\) \(B\) way madhan tahay oo waa la rogrogay. Weli waxaa hadhay \(1\) daqiqo ee \(A\) .
- Daqiiqaddii \(8\) \(A\) way madhan tahay. Gudaha \(B\) ciid ayaa ku soo daadatay si sax ah \(1\) daqiiqo; sidaas darteed \(B\) isla markiiba waa la rogaa mar kale.
- Daqiiqaddii \(9\) \(B\) way madhan tahay. Wakhtigii aad raadinaysay waa la gaadhay.
Daqiiqada \(8\) waxaanu rogaynaa saacada \(B\) taas oo wali socota. Tan iyo markii ay dib u bilowdeen daqiiqada \(7\) , sida saxda ah inta ciid ah ayaa hoos u daadatay sidii ay ugu haboonaan lahayd dhalooyinka gudaha \(1\) daqiiqo. Ka dib marka la leexiyo, kaliya qadarkan yar ayaa korka yaal. Hadda waxay qaadanaysaa \(1\) daqiiqo inay mar kale hoos u dhacdo. Sidaa darteed saacadu waxay madhan noqotaa daqiiqada \(9\) , ma aha ka dib orod kale oo dhamaystiran. Markaa waxaan ku cabbirnaa daqiiqadda ugu dambeysa ciid hore u soo martay. Animation-ku wuxuu muujinayaa tallaabadan:
Rogrogmada muraayadda socda ayaa sidoo kale faa'iido u leh xalka guud. Waqtiga haray waxaan ula jeednaa waqtiga ay ciiddu weli u baahan tahay inay dhex socoto qolka sare. Haddii saacadda buuxda ay leedahay wakhtiga orodku \(c\) inta ka hartayna uu yahay \(r\) , markaas xadiga ciidda hoose waxay u dhigantaa muddada \(cr\) . Markaad rogto, lacagtan saxda ah waxay imaaneysaa meesha ugu sareysa. Haddii qolka sare uu buuxsamo ka hor, way madhnaan doontaa ka dib iyo beddelkeeda. Saacad qayb ahaan socota, wakhtiga cusub ee orodka ee hadhay waa \(r'\):
$$r'=c-r.$$
Markii hore, cabbirku wuxuu ku bilaabmay leexashada koowaad. Tani waxay la macno tahay "iyada oo aan lahayn wakhti "lead": daqiiqad kasta ilaa bilawga la tiriyo. "Horumar" macnaheedu waa, dhanka kale, inaad diyaarsan karto saacadaha marka hore oo wakhtiga la rabo uu bilaabmayo ka dib. Tusaale ahaan, waxaan bilownaa labada saacadood oo aan soo celinaa \(A\) daqiiqadda \(4\) . Haddii \(B\) ay madhan tahay daqiiqada \(7\) , cabbirkayagu wuxuu bilaabmayaa. Haddii \(A\) ay faaruq noqoto daqiiqada \(8\) , way dhammaanaysaa. Waxaan cabbirnay \(1\) daqiiqo; daqiiqadihii hore ee \(7\) lama xisaabinayo.
Hadda waxaan tixgalinaynaa muraayadaha saacadaha aan sabab lahayn oo leh waqtiyo is-dhexgal togan \(a\) iyo \(b\) . Waxaan u yeernaa muddada la rabo \(T\) . Imisa jeer ayaa tan lagu cabbiri karaa haddii diyaarinta la ogolaado? Halkan sidoo kale, bilowga iyo dhammaadka waa in lagu aqoonsan karaa meel bannaan. Markaa waa inaadan bilaabin cabirida mar uun iyadoo ku saleysan dareenkaaga. Gacanku waxa uu ahaanayaa isla sida xujada dhabta ah. Marka hore waxaynu tusinaynaa wakhtiyada laga saaray; markaa waxaan ku tusi doonaa sida loo cabbiro inta kale oo dhan.
Marka hore aan soo qaadno saacadaha \(6\) iyo \(10\) daqiiqo. Labada wakhti ee orodka waxa loo qaybiyaa \(2\) . Ciidda sidaas darteed maskax ahaan waxaa loo qaybin karaa qaybo, mid kasta oo ka mid ah waxay qaadanaysaa \(2\) daqiiqo in la dhex maro. Markaad rogto ama sugto ilaa wakhtiga xiga ee uu madhan yahay, kaliya qaybo dhan ayaa mar kale la abuurayaa. Dhammaan wakhtiyada madhan ee la arki karo ayaa sidaas darteed tiro daqiiqado ah isu jiraan. Ma isticmaali kartid si aad u cabbirto muddada \(3\) daqiiqo, xitaa haddii aad u diyaariso saacadaha ilaa inta aad rabto ka hor.
Guud ahaan, ha ahaato \(g=\gcd(a,b)\) qaybiyaha ugu wayn ee wakhtiyada orodka. Markii hore labada erey ee soo hadhay waa dhufashada \(g\) . Marka la wareego \(r\) waxay noqotaa midkood \(ar\) ama \(br\) ; Labaduba waxay ahaanayaan kuwo loo qaybin karo \(g\) . Marka la sugo, waqtiga ugu yar ee togan ayaa soo haray, kaas oo sidoo kale ah isku-dhufashada \(g\) . Tani waxay ka dhigan tahay in dhammaan wakhtiyada madhan iyo masaafadooda ay ahaanayaan tiro badan oo \(g\) . Muddada la qiyaasi karo waa in ay qancisaa \(g\mid T\) : \(T\) waa in loo qaybiyaa \(g\) . Hadday intaas ku filan tahay waa la arki doonaa.
Si tan loo sameeyo, waxaanu u ogolaanay labada saacadood inay si buuxda u socdaan mar labaad iyo mar kale oo mid kasta u rogo isla marka ay madhan tahay. Midka kowaad wuxuu markaas noqdaa mid madhan ka dib \(a,2a,3a,\ldots\) cutubyada waqtiga, kan labaadna ka dib \(b,2b,3b,\ldots\) . Waxaan raadineynaa waqti \(mb\) ee saacadda labaad iyo waqtiga dambe \(na\) ee hore, oo u dhexeeya sida saxda ah \(T\) been. Bézout's lemma waxa uu dammaanad qaadayaa isbarbardhigga isugeynta \(n,m\) haddii \(T\) ay tahay tiro togan oo ah \(g\) Xidhiidhka aad raadinayso waa::
$$na-mb=T.$$
Nambarada \(n,m\) ay bixiso Bézout waxay noqon karaan marka hore taban. Orodka xun lama fulin karo. Si kastaba ha ahaatee, mid ayaa kordhin kara labada lambar iyada oo aan la beddelin wakhtiga u dhexeeya: waxaan ku beddelnaa \(n+kb/g\) iyo \(m+ka/g\) , halkaasoo \(k\) ay tahay isugeyn ku filan oo togan. Labada wakhti sidaas darteed waxaa lagu beddelay isla qaddar isku mid ah \(kab/g\) ; kala duwanaanshuhu waa hadhaa \(T\) . Markaa labada lambarba waxay noqdaan kuwo togan, waqtiyada loo baahan yahayna waa ka dib markay saacadaha bilaabmaan.
Hadda waxaad tirisaa wareegyada dhamaystiran ee saacad kasta. Marka ay saacadda \(m\) noqoto mid faaruq ah ayaa cabbirku bilaabmayaa; waxay dhamaanaysaa marka saacada ugu horaysa ay madhan tahay \(n\) -th time. Waxa u dhexeeya sida saxda ah \(T\) cutubyo wakhti ah. Diyaarintu waxay qaadan kartaa waqti dheer. Caddeyntu ma ballan qaadayso habraac gaaban oo gaar ah. Waayo \(T=0\) bilawga iyo dhamaadku way isku beegmaan. Tani waxay caddaynaysaa dhammaan ujeedooyinka isugeynta aan xun ahayn: Diyaargarowga, muddada ayaa la qiyaasi karaa haddii iyo kaliya haddii qaybiyaha guud ee ugu weyn uu qaybiyo.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Xeerkani qasab maaha in lagu dabaqo cabbirada bilawga bilowga hore. Tusaale ahaan, iyadoo \(4\) iyo \(7\) daqiiqo \(g=1\) , laakiin ka dib \(1\) daqiiqo wax saacad ma madhan. Markaa ma arki kartid dhamaadka daqiiqada. Cabbirka laga bilaabo daqiqida \(7\) ilaa \(8\) ee lagu sifeeyay kor ayaa shaqeeya oo kaliya sababtoo ah diyaarinta lama xisaabinayo. Caddaynta ayaa markaa ka jawaabeysa su'aasha ah waxa suurtagal ah ka dib diyaarinta. Haddii aad raadinayso hab la oggol yahay oo leh ama la'aanteed, raadinta habaysan ee soo socota ayaa ku caawin doonta.
Qoraalka PHP wuxuu xusuustaa labadaba wakhtiyada orodka ee hadhay iyo wakhtiga ka soo wareegay tan iyo bilawgii cabbirka. Xaalad kasta oo noocaas ah, isku day dhammaan \(4\) Suurtagalnimada: ma jiro saacad, kaliya kan koowaad, kaliya kan labaad ama labada roji. Kadibna waxay sugaysaa ilaa marka xigta ay faaruqiso. Qiimaha \(-1\) waxay tilmaamaysaa diyaarinta; gelitaanka start wuxuu dejiyaa waqtiga cabbirka \(0\). Shuruudaha la og yahay dib looma baari doono. Tixda la helay waxaa lagu helaa kuwii ka horeeyay. wait kaliya waxa ay tilmaamaysaa masaafada soo socota faaruqinta, ma aha qiyaas wakhti dheeraad ah:
<?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;
}
Raadinta waxay soo saartaa ama soo celisaa nidaam la oggol yahay null, haddaan midna jirin. Waxay daboolaysaa dhammaan sii wadida la oggol yahay waxayna u baahan tahay ugu badnaan diyaargarow \((a+1)(b+1)(T+2)\) Gobolada Waxyaalaha waaweyni sidaas darteed waxay u baahan yihiin xasuus badan. Tirada beddelka raadinta waa la yareeyaa, maaha wakhtiga diyaarinta. Orodka macquulka ah iyo wakhtiyada la beegsanayo waxaa loo rogaa tiro dhan iyadoo la isticmaalayo qiimeeye guud. Waqtiyada runtime-yada oo aan lahayn halbeeg waqti wadaag ah, tusaale ahaan \(1\) iyo \(\sqrt{2}\), Baadhitaankan isugaynta kooban kuma habboona.