Ana rong jam: siji mlaku ing \(4\) menit, liyane ing \(7\) menit. Kepiye cara ngukur persis \(9\) menit nalika pangukuran kudu diwiwiti nalika jam diwiwiti? Jam liyane, ngetang detik lan guessing ora diijini. Sampeyan mung kudu nguripake kaca tingal jam lan nonton nalika kamar ndhuwur kosong. Nguripake kudu ora njupuk wektu. Apa sing kita goleki yaiku proses ing pungkasan wektu sing dikarepake bisa dingerteni mung dening kacamata jam.
Kita nelpon jam karo \(4\) menit \(A\) lan siji karo \(7\) menit \(B\) . Wiwitane kabeh pasir ana ing sisih ngisor. Kita miwiti jam loro ing wektu sing padha kanthi ngowahi; Wiwit saiki, jumlah menit sing digoleki \(9\) . Sawise iku, sampeyan bisa tansah perdagangan nalika jam ing ndhuwur dadi kosong. Sampeyan bisa uga ora nguripake siji, siji utawa loro jam, malah siji sing isih mlaku. Sampeyan ngenteni nganti wektu sabanjuré entek. Mungkasi lan menehi tandha ora diidini; jam kosong bisa tetep ngadeg. Solusi katon kaya iki:
- Ing menit \(0\) \(A\) lan \(B\) diwiwiti.
- Ing menit \(4\) \(A\) kosong lan dibalik. \(B\) terus mlaku ora owah.
- Ing menit \(7\) \(B\) kosong lan dibalik. Isih ana \(1\) menit ing \(A\) .
- Ing menit \(8\) \(A\) kosong. Ing \(B\) wedhi mudhun kanggo persis \(1\) menit; mulane \(B\) langsung dibalik maneh.
- Ing menit \(9\) \(B\) kosong. Wektu sing digoleki wis tekan.
Ing menit \(8\) kita nguripake jam \(B\) sing isih mlaku. Wiwit diwiwiti maneh ing menit \(7\) , persis kaya pasir sing mili mudhun kaya sing pas liwat kemacetan ing \(1\) menit. Sawise ngowahi, mung jumlah cilik iki ing ndhuwur. Saiki butuh \(1\) menit kanggo nyemprot maneh. Dadi jam dadi kosong ing menit \(9\) , ora sawise roto lengkap liyane. Dadi kita ngukur menit pungkasan karo wedhi sing wis liwati. Animasi nuduhake pamindhahan iki:
Flipping hourglass mlaku uga migunani kanggo solusi umum. Kanthi wektu sing isih ana, tegese wektu wedhi isih kudu mili ing kamar ndhuwur. Yen jam lengkap duwe wektu mlaku \(c\) lan wektu mlaku sing isih ana \(r\) , banjur jumlah pasir ing ngisor cocog karo durasi \(cr\) . Yen sampeyan nguripake, jumlah sing tepat iki bakal munggah ing ndhuwur. Yen kamar ndhuwur wis kebak sakdurunge, banjur bakal kosong lan kosok balene. Kanggo jam mlaku sebagian, wektu mlaku sing isih anyar yaiku \(r'\):
$$r'=c-r.$$
Sadurunge, pangukuran diwiwiti kanthi giliran pisanan. Iki tegese "tanpa wektu timbal": saben menit wiwit count wiwitan. "Kanthi advance" tegese, ing tangan liyane, sampeyan bisa nyiyapake jam dhisik lan periode wektu sing dikarepake diwiwiti mengko. Contone, kita miwiti loro jam lan nguripake \(A\) ing menit \(4\) . Yen \(B\) dadi kosong ing menit \(7\) , pangukuran kita diwiwiti. Yen \(A\) dadi kosong ing menit \(8\) , iku ends. Kita ngukur \(1\) menit; sadurungé \(7\) menit ora count.
Saiki kita nimbang jam weker kanthi wektu operasi integer positif \(a\) lan \(b\) . Kita nelpon durasi sing dikarepake \(T\) . Apa kaping bisa diukur karo iki yen preparation diijini? Ing kene uga, wiwitan lan pungkasan kudu dingerteni kanthi ruang kosong. Dadi sampeyan ora kudu miwiti ngukur ing sawetara titik adhedhasar perasaan sampeyan. Ngalahake tetep padha ing teka-teki nyata. Pisanan kita nuduhake wektu sing ora kalebu; banjur kita bakal nuduhake sampeyan carane bener ngukur kabeh liyane.
Pisanan ayo njupuk jam karo \(6\) lan \(10\) menit. Wektu mlaku loro-lorone bisa dibagi dening \(2\) . Mulane wedhi bisa dipérang dadi bagian mental, sing saben-saben njupuk \(2\) menit kanggo ngliwati. Yen sampeyan nguripake utawa ngenteni nganti sabanjure kosong, mung kabeh bagean sing digawe maneh. Kabeh wektu kosong sing bisa diamati dadi sawetara menit. Sampeyan ora bisa digunakake kanggo ngukur durasi \(3\) menit, sanajan sampeyan nyiyapake jam kanggo anggere sampeyan seneng sadurunge.
Umumé, supaya \(g=\gcd(a,b)\) dadi pembagi umum paling gedhe saka wektu mlaku. Kaping pisanan, istilah sing isih ana yaiku kelipatan \(g\) . Nalika diputer \(r\) dadi \(ar\) utawa \(br\) ; loro tetep bisa dibagi dening \(g\) . Nalika nunggu, wektu isih positif paling cilik, sing uga kelipatan saka \(g\) . Iki tegese kabeh wektu kosong lan jarake tetep kelipatan \(g\) . Dadi, durasi sing bisa diukur kudu nyukupi \(g\mid T\) : \(T\) kudu dibagi karo \(g\) . Apa sing cukup isih kudu dideleng.
Kanggo nindakake iki, kita supaya loro jam mbukak maneh lan maneh lan nguripake saben siji sanalika iku kosong. Pisanan banjur dadi kosong sawise \(a,2a,3a,\ldots\) unit wektu, kaloro sawise \(b,2b,3b,\ldots\) . We are looking for wektu \(mb\) saka jam kapindho lan wektu mengko \(na\) pisanan, antarane kang persis \(T\) dumunung. Lemma Bézout njamin wilangan bulat sing cocog \(n,m\) yen \(T\) minangka kelipatan positif saka \(g\) . Hubungan sing sampeyan goleki yaiku::
$$na-mb=T.$$
Angka \(n,m\) sing diwenehake dening Bézout bisa wiwitane negatif. Mlaku negatif ora bisa ditindakake. Nanging, siji bisa nambah nomer loro tanpa ngganti interval wektu: kita ngganti karo \(n+kb/g\) lan \(m+ka/g\) , ngendi \(k\) iku wilangan bulat positif cukup gedhe. Kaloro kaping mulane dipindhah kanthi jumlah sing padha \(kab/g\) ; bedane tetep \(T\) . Dadi nomer loro dadi positif lan wektu sing dibutuhake bener-bener sawise jam diwiwiti.
Saiki sampeyan ngetung siklus lengkap saben jam. Nalika jam \(m\) dadi kosong, pangukuran diwiwiti; iku ends nalika jam pisanan dadi kosong kanggo \(n\) -th wektu. Ana persis \(T\) unit wektu ing antarane. Preparation bisa njupuk wektu dawa. Bukti kasebut ora njanjeni proses sing cendhak. Kanggo \(T=0\) wiwitan lan pungkasan pas. Iki mbuktekake kanggo kabeh tujuan integer non-negatif: Kanthi persiapan, durasi bisa diukur yen lan mung yen pembagi umum paling gedhe dibagi.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Aturan iki ora kudu ditrapake kanggo miwiti pangukuran ing wiwitan wiwitan. Contone, karo \(4\) lan \(7\) menit \(g=1\) , nanging sawise \(1\) menit ora jam kosong. Dadi sampeyan ora bisa ndeleng pungkasan menit iki. Pangukuran saka menit \(7\) nganti \(8\) sing diterangake ing ndhuwur mung bisa digunakake amarga persiapan ora diitung. Bukti kasebut mangsuli pitakon apa sing bisa ditindakake sawise persiapan. Yen sampeyan nggoleki proses sing diidini kanthi utawa tanpa persiapan, telusuran sistematis ing ngisor iki bakal mbantu.
Skrip PHP ngelingi wektu sing isih ana lan wektu sing wis kelakon wiwit wiwitan pangukuran. Kanggo saben kondisi kasebut, coba kabeh \(4\) Kemungkinan: ora ana jam, mung pisanan, mung kaloro utawa nguripake loro-lorone. Banjur ngenteni nganti wektu sabanjuré kosong. Nilai \(-1\) nuduhake preparation; entri start nyetel wektu pangukuran \(0\). Kondisi sing dikenal ora bakal diselidiki maneh. Urutan sing ditemokake dipikolehi liwat para pendahulu. wait mung nuduhake jarak menyang kosongan sabanjure, dudu pangukuran wektu tambahan:
<?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;
}
Panelusuran nemokake utawa ngasilake proses sing diidini null, yen ora ana. Isine kabeh tutugan sing diidini lan mbutuhake persiapan maksimal \((a+1)(b+1)(T+2)\) Negara. Mulane input gedhe mbutuhake akeh memori. Jumlah transisi telusuran diminimalisir, dudu wektu persiapan. Wektu mlaku lan target sing rasional diowahi dadi nomer wutuh kanthi nggunakake denominator umum. Kanggo runtime tanpa unit wektu umum, contone \(1\) lan \(\sqrt{2}\), panelusuran integer winates iki ora cocok.