Эки кум саат бар: бири толугу менен \(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.$$
Мурда өлчөө биринчи кезек менен башталган. Бул "жеткирүү убактысы жок" дегенди билдирет: башталгандан бери ар бир мүнөт эсептелет. «Алдын ала» дегени, экинчи жагынан, сиз алгач сааттарды даярдай аласыз жана каалаган убакыт аралыгы кийинчерээк башталат. Мисалы, биз эки саатты тең баштап, \ \(4\) мүнөттө \(A\) бурабыз. Эгерде \(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\) жатат. Безоуттун леммасы, эгерде \(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\) Мүмкүнчүлүктөр: саат жок, биринчиси гана, экинчиси гана же экөөнү тең буруңуз. Андан кийин ал кийинки жолу бошогончо күтөт. Наркы \(-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}\), бул чектүү бүтүн издөө ылайыктуу эмес.