2 つの砂時計があります。1 つは完全に\(4\)分で実行され、もう 1 つは\(7\)分で実行されます。初めて時計を起動するときに測定を開始する必要がある場合、正確に\(9\)分を測定するにはどうすればよいでしょうか?別の時計、秒を数える、推測することは許可されていません。砂時計をひっくり返して、上部の部屋が空になるのを観察するだけです。方向転換に時間はかからないはずです。私たちが求めているのは、望ましい期間の終わりが砂時計だけで認識できるプロセスです。
\(4\)分の時計を\(A\) 、 \(7\)分の時計を\(B\)と呼びます。最初はすべての砂が底にあります。両方の時計を裏返すことで同時にスタートさせます。この時点から、検索された時間は\(9\)分となります。その後、上部の時計が空になったらいつでも取引できます。たとえまだ動作している時計であっても、一方、一方、または両方の時計を裏返すことはできません。次回なくなるまでお待ちください。停止したりマークしたりすることは許可されていません。空の時計はそのままでも構いません。解決策は次のようになります:
- 分\(0\) \(A\)と\(B\)が開始されます。
- 分で\(4\) \(A\)は空になり、反転されます。 \(B\)は変更せずに実行を続けます。
- 分で\(7\) \(B\)は空になり、反転されます。 \(A\)にはまだ\(1\)分あります。
- 分の時点では\(8\) \(A\)は空です。 \(B\)では、ちょうど\(1\)分間砂が流れ落ちました。したがって、 \(B\)はすぐに再び裏返されます。
- 分の時点では\(9\) \(B\)は空です。あなたが探していた時間に到達しました。
分\(8\)で時計\(B\)時計はまだ動いています。分\(7\)に再起動して以来、ボトルネックを\(1\)分で通過できる量とまったく同じ量の砂が流れてきました。回してみるとこれくらいしか上にありません。再び滴下するまでに\(1\)分かかります。したがって、時計は、別の完全な実行の後ではなく、分\(9\)で空になります。そこで、通過済みの砂でギリギリを計測します。アニメーションはこの動きを示しています:
ランニング砂時計をひっくり返すことも、一般的な解決策として役立ちます。残り時間とは、砂が上部チャンバー内をまだ通過する必要がある時間を意味します。フルクロックの実行時間が\(c\)で、残りの実行時間が\(r\)である場合、底にある砂の量は継続時間\(cr\)に対応します。ひっくり返すとちょうどこの量が一番上に出てきます。上部チャンバーが事前に満たされている場合、その後は空になります。またその逆も同様です。部分的に実行されているクロックの場合、新しい残り実行時間は\(r'\):
$$r'=c-r.$$
以前は、測定は最初のターンから始まりました。これは「リードタイムなし」を意味し、開始からすべての分がカウントされます。一方、「事前に」とは、時計を先に準備し、希望の時間帯が後で始まることを意味します。たとえば、両方の時計を開始し、分\(4\)で\(A\)を裏返します。 \(7\)分で\(B\)が空になると、測定が始まります。 \(8\)分で\(A\)が空になると終了します。 \(1\)分を測定しました。それまでの\(7\)分はカウントされません。
ここで、正の整数の実行時間\(a\)と\(b\)を持つ任意の砂時計を考えます。望ましい継続時間を\(T\)と呼びます。準備ができればこれでどのくらいのタイムが計測できるでしょうか？ここでも、始まりと終わりは何もない空間によって認識できる必要があります。したがって、自分の感覚に基づいて、ある時点から測定を開始するべきではありません。ハンドルは実際のパズルと同じままです。まず、どの時間が除外されるかを示します。次に、残りすべてを実際に測定する方法を説明します。
まず\(6\)分と\(10\)分の時計を考えてみましょう。どちらの実行時間も\(2\)で割り切れます。したがって、砂は頭の中でいくつかの部分に分割され、それぞれを通過するのに\(2\)分かかります。裏返すか、次に空になるまで待つと、全体の部分だけが再び作成されます。したがって、観察可能なすべての空き時間は偶数分の間隔になります。事前に好きなだけ時計を準備したとしても、 \(3\)分の継続時間を測定するために使用することはできません。
一般に、 \(g=\gcd(a,b)\)実行時間の最大公約数とします。最初は、残りの項は両方とも\(g\)の倍数です。回転すると\(r\)は\(ar\)または\(br\)になります。どちらも\(g\)で割り切れます。待機している場合、正の最小残り時間が経過します。これも\(g\)の倍数になります。これは、すべての空の時間とその距離が\(g\)の倍数のままであることを意味します。したがって、測定可能な期間は\(g\mid T\)を満たす必要があります。つまり、 \(T\) \(g\)で割り切れなければなりません。それが十分かどうかはまだ分からない。
これを行うには、両方の時計を何度も完全に実行させ、空になったらすぐにそれぞれを裏返します。最初のものは\(a,2a,3a,\ldots\)時間単位後に空になり、2 番目のもの\(b,2b,3b,\ldots\)後に空になります。 2 番目の時計の時刻\(mb\)と、最初の時計のそれ以降の時刻\(na\)を探しています。その間に正確に\(T\)あります。ベズーの補題は、 \(T\)が\(g\)の正の倍数である場合に、整数\(n,m\)が一致することを保証します。あなたが探している関係は次のとおりです。:
$$na-mb=T.$$
Bézout が提供する数値\(n,m\)は、最初は負の値になる可能性があります。ネガティブランは実行できません。ただし、時間間隔を変更せずに両方の数値を増やすことができます。これらを\(n+kb/g\)と\(m+ka/g\)に置き換えます。ここで\(k\)は十分に大きな正の整数です。したがって、どちらの時間も同じ量\(kab/g\)だけシフトされます。それらの差は\(T\)のままです。したがって、両方の数値が正になり、実際に必要な時間はクロックが開始した後になります。
ここで、各クロックの完全なサイクルを数えます。 \(m\)クロックが空になると、測定が開始されます。 \(n\)回目に最初のクロックが空になったときに終了します。間には正確に\(T\)時間単位があります。準備には長い時間がかかる場合があります。証明は特に短いプロセスを約束するものではありません。 \(T=0\)の場合、始まりと終わりは一致します。これは、すべての非負の整数目標に対して証明されます。準備があれば、最大公約数がそれを割る場合にのみ、期間を測定できます。:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
このルールは、最初の開始直後に測定を開始する場合には必ずしも適用されません。たとえば、 \(4\)分と\(7\)分\(g=1\)の場合、 \(1\)分を過ぎると空の時計はありません。したがって、この瞬間の終わりは見えません。上記の分\(7\)から\(8\)までの測定は、準備が考慮されていないため、機能するだけです。したがって、証明は、準備後に何が可能になるかという質問に答えます。準備の有無にかかわらず、許可されたプロセスを探している場合は、次の系統的な検索が役立ちます。
PHP スクリプトは、残りの実行時間と測定開始からの経過時間の両方を記憶します。そのようなあらゆる条件について、すべて試してください \(4\) 可能性: 時計なし、最初の時計のみ、2 番目の時計のみ、または両方を裏返す。その後、次回空になるまで待機します。値 \(-1\) 準備を示します。エントリー start 測定時間を設定します \(0\). 既知の状態は再調査されません。見つかったシーケンスは、その先行シーケンスを介して取得されます。 wait 追加の時間の測定ではなく、次の排泄までの距離のみを指します。:
<?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;
}
検索により、許可されたプロセスが見つかるか、返されます。 null, 何も存在しない場合。許可されているすべての継続をカバーしており、最大限の準備が必要です \((a+1)(b+1)(T+2)\) 州。したがって、大きな入力には大量のメモリが必要になります。準備時間ではなく、検索遷移の数が最小限に抑えられます。合理的な実行時間と目標時間は、共通の分母を使用して整数に変換されます。共通の時間単位のないランタイムの場合、たとえば \(1\) と \(\sqrt{2}\), この有限整数検索は適切ではありません。