Є два пісочних годинника: один повністю пробігає за \(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}\), цей кінцевий цілочисельний пошук не підходить.