Есть два песочных часа: одни работают полностью за \(4\) минуты, другие за \(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.$$
Раньше измерение начиналось с первого витка. Это означает «без задержек»: каждая минута с момента старта имеет значение. С другой стороны, «с заранее» означает, что вы можете сначала подготовить часы, а желаемый период времени начнется позже. Например, мы запускаем оба часа и переворачиваем \(A\) на минуте \(4\) . Если \(B\) становится пустым на минуте \(7\) , начинается наше измерение. Если \(A\) становится пустым на минуте \(8\) , оно заканчивается. Мы измерили \(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\) единиц времени, второй — после \(b,2b,3b,\ldots\) . Мы ищем время \(mb\) вторых часов и более позднее время \(na\) первых, между которыми находится именно \(T\) . Лемма Безу гарантирует совпадение целых чисел \(n,m\) если \(T\) является положительным кратным \(g\) . Отношения, которые вы ищете::
$$na-mb=T.$$
Числа \(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\) Возможности: нет часов, только первые, только вторые или перевернуть оба. Затем он ждет до следующего раза, когда он опустошится. Значение \(-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}\), этот конечный целочисленный поиск не подходит.