Terdapat dua jam pasir: satu berjalan sepenuhnya dalam \(4\) minit, satu lagi dalam \(7\) minit. Bagaimanakah anda mengukur dengan tepat \(9\) minit apabila pengukuran perlu dimulakan pada kali pertama jam dimulakan? Jam lain, mengira saat dan meneka tidak dibenarkan. Apa yang anda perlu lakukan ialah memusingkan jam pasir dan menonton apabila ruang atas kosong. Berpusing tidak sepatutnya mengambil masa. Apa yang kami cari ialah proses di mana penghujung tempoh masa yang diingini boleh diiktiraf semata-mata oleh jam pasir.
Kami memanggil jam dengan \(4\) minit \(A\) dan satu dengan \(7\) minit \(B\) . Pada mulanya semua pasir berada di bahagian bawah. Kami memulakan kedua-dua jam pada masa yang sama dengan membalikkannya; Mulai saat ini dan seterusnya kiraan \(9\) minit yang dicari. Selepas itu, anda sentiasa boleh berdagang apabila jam di bahagian atas menjadi kosong. Anda tidak boleh menghidupkan satu, satu atau kedua-dua jam, walaupun satu jam yang masih berjalan. Anda tunggu sehingga masa berikutnya ia habis. Berhenti dan menandakan tidak dibenarkan; jam kosong boleh kekal berdiri. Penyelesaiannya kelihatan seperti ini:
- Pada minit \(0\) \(A\) dan \(B\) dimulakan.
- Pada minit \(4\) \(A\) kosong dan terbalik. \(B\) terus berjalan tidak berubah.
- Pada minit \(7\) \(B\) kosong dan terbalik. Masih ada \(1\) minit lagi dalam \(A\) .
- Pada minit \(8\) \(A\) kosong. Dalam \(B\) pasir mengalir ke bawah selama tepat \(1\) minit; oleh itu \(B\) segera terbalik semula.
- Pada minit \(9\) \(B\) kosong. Masa yang anda cari telah sampai.
Pada minit \(8\) kami menghidupkan jam \(B\) yang masih berjalan. Memandangkan mereka dimulakan semula pada minit \(7\) sama banyak pasir yang telah mengalir ke bawah seperti yang akan dimuatkan melalui kesesakan dalam masa \(1\) minit. Selepas berpusing, hanya jumlah kecil ini di atas. Ia kini mengambil masa \(1\) minit untuk mengalir semula. Oleh itu jam menjadi kosong pada minit \(9\) , bukan selepas satu lagi larian lengkap. Jadi kita mengukur minit terakhir dengan pasir yang telah berlalu. Animasi menunjukkan langkah ini:
Membalikkan jam pasir yang sedang berjalan juga berguna untuk penyelesaian umum. Dengan baki masa yang kami maksudkan adalah masa yang pasir masih perlu mengalir di ruang atas. Jika jam penuh mempunyai masa berjalan \(c\) dan baki masa berjalannya ialah \(r\) , maka jumlah pasir di bahagian bawah sepadan dengan tempoh \(cr\) . Apabila anda membalikkannya, jumlah yang tepat ini akan berada di bahagian atas. Jika ruang atas penuh terlebih dahulu, ia akan kosong selepas itu dan sebaliknya. Untuk jam berjalan separa, baki masa berjalan baharu ialah \(r'\):
$$r'=c-r.$$
Sebelum ini, pengukuran bermula dengan pusingan pertama. Ini bermaksud "tanpa masa pendahuluan": setiap minit sejak permulaan dikira. "Dengan pendahuluan" bermakna, sebaliknya, anda boleh menyediakan jam terlebih dahulu dan tempoh masa yang dikehendaki bermula kemudian. Sebagai contoh, kita mulakan kedua-dua jam dan pusingkan \(A\) pada minit \(4\) . Jika \(B\) menjadi kosong pada minit \(7\) , pengukuran kami bermula. Jika \(A\) menjadi kosong pada minit \(8\) , ia tamat. Kami mengukur \(1\) minit; minit \(7\) sebelumnya tidak dikira.
Sekarang kita mempertimbangkan jam pasir arbitrari dengan masa berjalan integer positif \(a\) dan \(b\) . Kami memanggil tempoh yang dikehendaki \(T\) . Apakah masa yang boleh diukur dengan ini jika penyediaan dibenarkan? Di sini juga, permulaan dan penghujung mesti dikenali oleh ruang kosong. Oleh itu, anda tidak sepatutnya mula mengukur pada satu ketika berdasarkan perasaan anda. Pemegang tetap sama seperti dalam teka-teki sebenar. Mula-mula kami menunjukkan masa yang dikecualikan; kemudian kami akan menunjukkan kepada anda bagaimana untuk mengukur semua yang lain.
Mula-mula mari kita ambil jam dengan \(6\) dan \(10\) minit. Kedua-dua masa berjalan boleh dibahagikan dengan \(2\) . Oleh itu, pasir boleh dibahagikan secara mental kepada beberapa bahagian, setiap satunya mengambil masa \(2\) minit untuk dilalui. Apabila anda membalikkannya atau menunggu sehingga masa berikutnya ia kosong, hanya keseluruhan bahagian dibuat semula. Oleh itu, semua masa kosong yang boleh diperhatikan adalah bilangan minit yang genap. Anda tidak boleh mengukur tempoh \(3\) minit dengannya, walaupun anda menyediakan jam selama yang anda suka sebelum ini.
Secara umum, biarkan \(g=\gcd(a,b)\) menjadi pembahagi sepunya terbesar bagi masa larian. Pada mulanya kedua-dua sebutan yang tinggal ialah gandaan bagi \(g\) . Apabila diputar \(r\) menjadi sama ada \(ar\) atau \(br\) ; kedua-duanya kekal boleh dibahagikan dengan \(g\) . Apabila menunggu, masa baki positif terkecil berlalu, yang juga merupakan gandaan bagi \(g\) . Ini bermakna semua masa kosong dan jaraknya kekal gandaan bagi \(g\) . Oleh itu, tempoh yang boleh diukur mesti memenuhi \(g\mid T\) : \(T\) mesti boleh dibahagi dengan \(g\) . Sama ada itu sudah mencukupi masih perlu dilihat.
Untuk melakukan ini, kami membiarkan kedua-dua jam berjalan sepenuhnya dan sekali lagi dan membalikkan setiap jam sebaik sahaja ia kosong. Yang pertama kemudian menjadi kosong selepas \(a,2a,3a,\ldots\) unit masa, yang kedua selepas \(b,2b,3b,\ldots\) . Kami sedang mencari masa \(mb\) pada jam kedua dan masa kemudian \(na\) pada jam pertama, di antaranya tepat \(T\) terletak. Lemma Bézout menjamin padanan integer \(n,m\) jika \(T\) ialah gandaan positif bagi \(g\) . Hubungan yang anda cari ialah::
$$na-mb=T.$$
Nombor \(n,m\) yang dibekalkan oleh Bézout pada mulanya boleh menjadi negatif. Larian negatif tidak boleh dijalankan. Walau bagaimanapun, seseorang boleh meningkatkan kedua-dua nombor tanpa mengubah selang masa: kami menggantikannya dengan \(n+kb/g\) dan \(m+ka/g\) , dengan \(k\) ialah integer positif yang cukup besar. Oleh itu, kedua-dua masa dianjakkan dengan jumlah yang sama \(kab/g\) ; perbezaan mereka kekal \(T\) . Jadi kedua-dua nombor menjadi positif dan masa yang diperlukan sebenarnya selepas jam bermula.
Sekarang anda mengira kitaran lengkap setiap jam. Apabila jam \(m\) menjadi kosong pengukuran bermula; ia tamat apabila jam pertama menjadi kosong untuk masa \(n\) -ke. Terdapat betul-betul \(T\) unit masa di antaranya. Penyediaan boleh mengambil masa yang lama. Buktinya tidak menjanjikan proses yang sangat singkat. Untuk \(T=0\) permulaan dan penghujung bertepatan. Ini membuktikan untuk semua objektif integer bukan negatif: Dengan penyediaan, tempoh boleh diukur jika dan hanya jika pembahagi sepunya terbesar membahagikannya:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Peraturan ini tidak semestinya digunakan untuk memulakan pengukuran tepat pada permulaan pertama. Contohnya, dengan \(4\) dan \(7\) minit \(g=1\) , tetapi selepas \(1\) minit tiada jam kosong. Jadi anda tidak dapat melihat penghujung minit ini. Pengukuran dari minit \(7\) hingga \(8\) yang diterangkan di atas hanya berfungsi kerana penyediaan tidak dikira. Bukti itu menjawab persoalan tentang apa yang mungkin selepas penyediaan. Jika anda sedang mencari proses yang dibenarkan dengan atau tanpa persediaan, carian sistematik berikut akan membantu.
Skrip PHP mengingati kedua-dua baki masa berjalan dan masa yang telah berlalu sejak permulaan pengukuran. Untuk setiap keadaan sedemikian, cuba semuanya \(4\) Kemungkinan: tiada jam, hanya yang pertama, hanya yang kedua atau terbalik kedua-duanya. Ia kemudian menunggu sehingga kali berikutnya ia dikosongkan. Nilai \(-1\) menunjukkan penyediaan; entri tersebut start menetapkan masa pengukuran \(0\). Keadaan yang diketahui tidak akan disiasat semula. Urutan yang ditemui diperolehi melalui pendahulunya. wait hanya merujuk kepada jarak ke pengosongan seterusnya, bukan ukuran masa 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;
}
Carian menemui atau mengembalikan proses yang dibenarkan null, jika tiada. Ia meliputi semua sambungan yang dibenarkan dan memerlukan persediaan maksimum \((a+1)(b+1)(T+2)\) Negeri. Oleh itu, input yang besar memerlukan banyak memori. Bilangan peralihan carian diminimumkan, bukan masa penyediaan. Masa larian dan sasaran yang rasional ditukar kepada nombor bulat menggunakan penyebut biasa. Untuk masa jalan tanpa unit masa biasa, sebagai contoh \(1\) dan \(\sqrt{2}\), carian integer terhingga ini tidak sesuai.