Ada dua jam pasir: yang satu berjalan penuh dalam \(4\) menit, yang lain dalam \(7\) menit. Bagaimana Anda mengukur tepat \(9\) menit ketika pengukuran harus dimulai saat jam dimulai pertama kali? Jam lain, menghitung detik dan menebak tidak diperbolehkan. Yang harus Anda lakukan adalah membalikkan jam pasir dan melihat apakah ruang atas kosong. Berbalik tidak akan memakan waktu lama. Apa yang kami cari adalah sebuah proses di mana akhir periode waktu yang diinginkan hanya dapat dikenali oleh jam pasir.
Kita menyebut jam dengan \(4\) menit \(A\) dan jam dengan \(7\) menit \(B\) . Awalnya semua pasir ada di dasar. Kami memulai kedua jam secara bersamaan dengan memutarnya; Mulai saat ini dan seterusnya \(9\) menit yang dicari dihitung. Setelah itu, Anda selalu dapat berdagang ketika jam di atas kosong. Anda tidak boleh membalik salah satu, salah satu atau kedua jam, bahkan jam yang masih berjalan. Anda menunggu sampai waktu berikutnya habis. Berhenti dan menandai tidak diperbolehkan; jam kosong bisa tetap berdiri. Solusinya terlihat seperti ini:
- Pada menit \(0\) \(A\) dan \(B\) dimulai.
- Pada menit \(4\) \(A\) kosong dan dibalik. \(B\) terus berjalan tanpa perubahan.
- Pada menit \(7\) \(B\) kosong dan dibalik. Masih ada \(1\) menit tersisa di \(A\) .
- Pada menit \(8\) \(A\) kosong. Di \(B\) pasir mengalir tepat \(1\) menit; oleh karena itu \(B\) segera dibalik lagi.
- Pada menit \(9\) \(B\) kosong. Waktu yang Anda cari telah tercapai.
Pada menit \(8\) kita putar jam \(B\) yang masih berjalan. Sejak dimulai kembali pada menit \(7\) , pasir yang mengalir ke bawah sama banyaknya dengan jumlah pasir yang dapat masuk melalui kemacetan dalam \(1\) menit. Setelah dibalik, hanya sedikit saja yang berada di atasnya. Kini diperlukan waktu \(1\) menit untuk menetes kembali. Oleh karena itu jam menjadi kosong pada menit \(9\) , bukan setelah proses selesai lainnya. Jadi menit terakhir kita ukur dengan pasir yang sudah lewat. Animasi menunjukkan gerakan ini:
Membalik jam pasir yang sedang berjalan juga berguna untuk solusi umum. Yang dimaksud dengan waktu tersisa adalah waktu yang masih dibutuhkan pasir untuk mengalir melalui ruang atas. Jika jam penuh memiliki waktu berjalan \(c\) dan waktu berjalan yang tersisa adalah \(r\) , maka jumlah pasir di bagian bawah sesuai dengan durasi \(cr\) . Saat Anda membaliknya, jumlah persisnya akan muncul di bagian atas. Jika ruang atas sebelumnya penuh, maka akan kosong setelahnya dan sebaliknya. Untuk jam yang berjalan sebagian, sisa waktu berjalan yang baru adalah \(r'\):
$$r'=c-r.$$
Sebelumnya pengukuran dimulai dengan putaran pertama. Artinya “tanpa waktu tunggu”: setiap menit sejak permulaan dihitung. Sebaliknya, “Dengan terlebih dahulu” berarti Anda dapat menyiapkan jam terlebih dahulu dan periode waktu yang diinginkan dimulai kemudian. Misalnya, kita memulai kedua jam dan memutar \(A\) pada menit \(4\) . Jika \(B\) menjadi kosong pada menit \(7\) , pengukuran kita dimulai. Jika \(A\) menjadi kosong pada menit \(8\) , itu berakhir. Kami mengukur \(1\) menit; \(7\) menit sebelumnya tidak dihitung.
Sekarang kita pertimbangkan jam pasir sembarang dengan waktu berjalan bilangan bulat positif \(a\) dan \(b\) . Kami menyebut durasi yang diinginkan \(T\) . Jam berapa yang bisa diukur dengan ini jika persiapan diperbolehkan? Di sini juga, awal dan akhir harus dapat dikenali melalui ruang kosong. Jadi sebaiknya Anda tidak mulai mengukur pada titik tertentu berdasarkan perasaan Anda. Pegangannya tetap sama seperti pada puzzle sebenarnya. Pertama kami menunjukkan waktu mana yang dikecualikan; lalu kami akan menunjukkan cara mengukur sisanya.
Pertama mari kita ambil jam dengan \(6\) dan \(10\) menit. Kedua waktu berjalan habis dibagi \(2\) . Oleh karena itu, pasir secara mental dapat dibagi menjadi beberapa bagian, yang masing-masing memerlukan waktu \(2\) menit untuk melewatinya. Saat Anda membaliknya atau menunggu hingga kosong lagi, hanya sebagian utuh yang dibuat lagi. Oleh karena itu, semua waktu kosong yang dapat diamati memiliki jarak beberapa menit yang genap. Anda tidak dapat menggunakannya untuk mengukur durasi \(3\) menit, meskipun Anda telah menyiapkan jam selama yang Anda inginkan sebelumnya.
Secara umum, misalkan \(g=\gcd(a,b)\) adalah pembagi persekutuan terbesar dari waktu berjalan. Awalnya kedua suku yang tersisa adalah kelipatan \(g\) . Saat diputar \(r\) menjadi \(ar\) atau \(br\) ; keduanya tetap habis dibagi \(g\) . Saat menunggu, sisa waktu positif terkecil telah berlalu, yang juga merupakan kelipatan \(g\) . Artinya semua waktu kosong dan jaraknya tetap kelipatan \(g\) . Oleh karena itu, durasi yang dapat diukur harus memenuhi \(g\mid T\) : \(T\) harus habis dibagi \(g\) . Apakah itu cukup masih harus dilihat.
Untuk melakukan hal ini, kita membiarkan kedua jam berjalan sepenuhnya berulang kali dan memutar masing-masing jam segera setelah jam kosong. Yang pertama kemudian menjadi kosong setelah \(a,2a,3a,\ldots\) satuan waktu, yang kedua setelah \(b,2b,3b,\ldots\) . Kita mencari waktu \(mb\) pada jam kedua dan waktu selanjutnya \(na\) pada jam pertama, yang di antaranya terletak tepat \(T\) . Lemma Bézout menjamin pencocokan bilangan bulat \(n,m\) jika \(T\) adalah kelipatan positif dari \(g\) . Hubungan yang Anda cari adalah::
$$na-mb=T.$$
Angka \(n,m\) yang diberikan oleh Bézout awalnya bisa negatif. Proses negatif tidak dapat dilakukan. Namun, seseorang dapat menambah kedua angka tersebut tanpa mengubah interval waktu: kita menggantinya dengan \(n+kb/g\) dan \(m+ka/g\) , di mana \(k\) adalah bilangan bulat positif yang cukup besar. Oleh karena itu, kedua waktu digeser dengan jumlah yang sama \(kab/g\) ; perbedaannya tetap \(T\) . Jadi kedua angka tersebut menjadi positif dan waktu yang diperlukan sebenarnya adalah setelah jam dimulai.
Sekarang Anda menghitung siklus lengkap setiap jam. Ketika jam \(m\) menjadi kosong, pengukuran dimulai; itu berakhir ketika jam pertama menjadi kosong untuk yang ke \(n\) kalinya. Tepatnya terdapat \(T\) satuan waktu di antaranya. Persiapannya bisa memakan waktu lama. Buktinya tidak menjanjikan proses yang singkat. Untuk \(T=0\) awal dan akhir bertepatan. Hal ini terbukti untuk semua tujuan bilangan bulat non-negatif: Dengan persiapan, suatu durasi dapat diukur jika dan hanya jika pembagi persekutuan terbesar membaginya:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Aturan ini tidak serta merta berlaku untuk memulai pengukuran tepat pada permulaan pertama. Misalnya, dengan \(4\) dan \(7\) menit \(g=1\) , tetapi setelah \(1\) menit tidak ada jam yang kosong. Jadi Anda tidak dapat melihat akhir dari menit ini. Pengukuran dari menit \(7\) hingga \(8\) yang dijelaskan di atas hanya berfungsi karena persiapannya tidak dihitung. Dengan demikian, bukti tersebut menjawab pertanyaan tentang apa yang mungkin terjadi setelah persiapan. Jika Anda mencari proses yang diizinkan dengan atau tanpa persiapan, pencarian sistematis berikut akan membantu.
Skrip PHP mengingat sisa waktu berjalan dan waktu yang telah berlalu sejak awal pengukuran. Untuk setiap kondisi seperti itu, cobalah semuanya \(4\) Kemungkinan: tidak ada jam, hanya jam pertama, hanya jam kedua, atau balikkan keduanya. Kemudian menunggu sampai waktu berikutnya kosong. Nilainya \(-1\) menunjukkan persiapan; entri start mengatur waktu pengukuran \(0\). Kondisi yang diketahui tidak akan diselidiki ulang. Urutan yang ditemukan diperoleh melalui pendahulunya. wait hanya mengacu pada jarak ke pengosongan berikutnya, bukan pengukuran waktu 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;
}
Pencarian menemukan atau mengembalikan proses yang diizinkan null, jika tidak ada. Ini mencakup semua kelanjutan yang diizinkan dan membutuhkan persiapan yang maksimal \((a+1)(b+1)(T+2)\) Amerika. Oleh karena itu, input yang besar memerlukan banyak memori. Jumlah transisi pencarian diminimalkan, bukan waktu persiapan. Waktu lari dan target yang rasional diubah menjadi bilangan bulat menggunakan penyebut yang sama. Untuk runtime tanpa satuan waktu yang sama, misalnya \(1\) dan \(\sqrt{2}\), pencarian bilangan bulat terbatas ini tidak cocok.