ʻO ka pilikia hola hola09
26

ʻElua mau aniani hola: holo holoʻokoʻa kekahi i loko o $4$ mau minuke, ʻo kekahi i loko o $7$ mau minuke. Pehea ʻoe e ana pono ai $9$ mau minuke ke hoʻomaka ke ana i ka manawa mua e hoʻomaka ai nā uaki? ʻAʻole ʻae ʻia ka uaki ʻē aʻe, ke helu kekona a me ka wānana. ʻO kāu mea e hana ai, ʻo ka huli ʻana i nā aniani hola a nānā i ka wā ʻole o ke keʻena luna. ʻAʻole pono ka huli ʻana i kekahi manawa. ʻO ka mea a mākou e ʻimi nei he hana ia e ʻike ʻia ai ka hopena o ka manawa i makemake ʻia e nā aniani hola.

Kāhea mākou i ka uaki me $4$ minuke $A$ a me ka mea me $7$ minuke $B$ . I ka mua aia ke one a pau ma lalo. Hoʻomaka mākou i nā uaki ʻelua i ka manawa like me ka hoʻohuli ʻana iā lākou; Mai kēia manawa mai ka helu ʻana o nā minuke $9$ . Ma hope o kēlā, hiki iā ʻoe ke kālepa i nā manawa a pau ke lilo ka uaki ma luna. ʻAʻole hiki iā ʻoe ke hoʻohuli i hoʻokahi, hoʻokahi a i ʻole nā uaki ʻelua, ʻoiai kekahi e holo mau ana. Kali ʻoe a hiki i ka wā e pau ai. ʻAʻole ʻae ʻia ka hoʻokuʻu ʻana a me ke kaha ʻana; hiki ke kū ka uaki kaʻawale. Ua like ke ano o keia:

I ka minuke $0$ $A$ a me $B$ hoʻomaka.
I ka minuke $4$ $A$ ua hakahaka a ua hoohuliia. $B$ e holo mau ana me ka loli ole.
I ka minuke $7$ $B$ ua hakahaka a ua hoohuliia. He $1$ minuke i koe ma $A$ .
I ka minuke $8$ $A$ kaawale. I $B$ ua holo ke one no $1$ minuke; nolaila ua hoohuli hou ia $B$ .
I ka minuke $9$ $B$ kaawale. Ua hiki i ka manawa āu e ʻimi nei.

I ka minuke $8$ huli mākou i ka uaki $B$ e holo mau ana. Mai ka hoʻomaka hou ʻana i ka minuke $7$ , e like me ka nui o ke one i kahe ʻia i lalo e like me ke komo ʻana ma ka bottleneck i $1$ minuke. Ma hope o ka hoʻohuli ʻana, aia kēia mea liʻiliʻi ma luna. He $1$ minuke e kahe hou i lalo. No laila, ua nele ka uaki i ka minuke $9$ , ʻaʻole ma hope o ka holo piha ʻana. No laila, ana mākou i ka minuke hope me ke one i hala. Hōʻike ka animation i kēia neʻe:

ʻO ka hoʻololi ʻana i ka hola hola holo he mea maikaʻi nō hoʻi no ka hoʻonā maʻamau. ʻO ka manawa i koe, ʻo ia ka manawa e pono ai ke kahe ʻana o ke one ma ke keʻena luna. Inā loaʻa i ka uaki piha ka manawa holo $c$ a ʻo kona manawa holo i koe ʻo $r$ , a laila pili ka nui o ke one ma lalo me ka lōʻihi $cr$ . Ke hoʻohuli ʻoe iā ia, hiki mai kēia nui pololei i luna. Inā piha ka keʻena luna ma mua, ʻaʻohe mea ma hope a me ka hope. No ka uaki holo hapa, ʻo ka manawa holo hou i koe ʻo $r'$:

$$r'=c-r.$$

Ma mua, ua hoʻomaka ke ana me ka huli mua. ʻO kēia ke ʻano "me ka ʻole o ka manawa alakaʻi": kēlā me kēia minuke mai ka helu ʻana o ka hoʻomaka. "Me ka mua", 'o ia hoʻi, hiki iā ʻoe ke hoʻomākaukau mua i nā wati a hoʻomaka ka manawa i makemake ʻia ma hope. No ka laʻana, hoʻomaka mākou i nā uaki ʻelua a huli i ka $A$ i ka minuke $4$ . Inā nele $B$ i ka minuke $7$ , hoʻomaka kā mākou ana. Inā nele $A$ i ka minuke $8$ , pau ia. Ua ana mākou i $1$ minuke; ʻaʻole helu nā minuke $7$ i hala.

I kēia manawa ke noʻonoʻo nei mākou i nā hola hola me nā manawa holo integer maikaʻi $a$ a me $b$ . Kāhea mākou i ka lōʻihi i makemake ʻia $T$ . He aha nā manawa e hiki ke ana me kēia inā ʻae ʻia ka hoʻomākaukau? Eia kekahi, pono e ʻike ʻia ka hoʻomaka a me ka hopena e kahi hakahaka. No laila ʻaʻole pono ʻoe e hoʻomaka e ana i kekahi manawa ma muli o kou manaʻo. Ua like nā lima me ka puzzle maoli. Hōʻike mua mākou i nā manawa i kāpae ʻia; a laila e hōʻike mākou iā ʻoe pehea e ana maoli ai i ke koena a pau.

E lawe mua kākou i nā uaki me $6$ a me $10$ mau minuke. Māhele ʻia nā manawa holo ʻelua e $2$ . No laila hiki ke hoʻokaʻawale ʻia ke one i mau ʻāpana, ʻo kēlā me kēia mea e lawe i $2$ mau minuke e hele ai. Ke hoʻohuli a kali ʻoe a hiki i ka manawa aʻe e kaʻawale, hana hou ʻia nā ʻāpana holoʻokoʻa. No laila, ʻo nā manawa hakahaka a pau i ʻike ʻia he mau minuke ke kaʻawale. ʻAʻole hiki iā ʻoe ke hoʻohana iā ia no ke ana ʻana i ka lōʻihi o $3$ mau minuke, ʻoiai inā ʻoe e hoʻomākaukau i nā uaki no ka lōʻihi āu e makemake ai ma mua.

Ma keʻano laulā, e ʻae ʻo $g=\gcd(a,b)$ ka mahele maʻamau nui loa o nā manawa holo. I ka hoʻomaka ʻana, ʻo nā huaʻōlelo ʻelua i koe he mau huahelu o $g$ . Ke hoʻololi ʻia $r$ i $ar$ a i ʻole $br$ ; mau puunaue laua e $g$ . I ke kali ʻana, ua hala ka manawa maikaʻi liʻiliʻi loa i koe, ʻo ia hoʻi ka helu o $g$ . ʻO ia ke ʻano o nā manawa kaʻawale a me ko lākou mau mamao he mau paʻa o $g$ . No laila, pono e ho'omā'ona ka lō'ihi hiki ke 'ike i $g\mid T$ : $T$ pono e puunaue 'ia e $g$ . Inā lawa paha ia e ʻike ʻia.

No ka hana ʻana i kēia, hoʻokuʻu mākou i nā uaki ʻelua e holo hou a hoʻohuli i kēlā me kēia i ka wā ʻole. A laila, lilo ka mea mua ma hope o $a,2a,3a,\ldots$ manawa, ʻo ka lua ma hope o $b,2b,3b,\ldots$ . Ke ʻimi nei mākou i ka manawa $mb$ o ka uaki ʻelua a me ka manawa hope $na$ o ka uaki mua, aia ma waena o ia ka $T$ . ʻO ka lemma o Bézout e hōʻoiaʻiʻo i nā helu helu like $n,m$ inā he huahelu maikaʻi ʻo $T$ o $g$ . ʻO ka pilina āu e ʻimi nei::

$$na-mb=T.$$

ʻO nā helu $n,m$ i hāʻawi ʻia e Bézout hiki ke hoʻohālikelike mua. ʻAʻole hiki ke hoʻokō ʻia nā holo ʻino. Eia nō naʻe, hiki i kekahi ke hoʻonui i nā helu ʻelua me ka hoʻololi ʻole ʻana i ka wā: hoʻololi mākou iā lākou me $n+kb/g$ a me $m+ka/g$ , kahi $k$ kahi huina kūpono nui. No laila ua hoʻololi ʻia nā manawa ʻelua e ka nui like $kab/g$ ; ko lakou like ole $T$ . No laila, lilo nā helu ʻelua i mea maikaʻi a ʻo nā manawa i koi ʻia ma hope o ka hoʻomaka ʻana o nā uaki.

I kēia manawa, helu ʻoe i nā pōʻai piha o kēlā me kēia uaki. Ke lilo ka uaki $m$ i ka hakahaka, hoʻomaka ke ana; e pau ana i ka wa e nele ai ka uaki mua no ka $n$ -ke manawa. Aia pololei $T$ nā ʻāpana manawa ma waena. Hiki ke lōʻihi ka hoʻomākaukau ʻana. ʻAʻole hoʻohiki ka hōʻoia i kahi kaʻina hana pōkole. No $T=0$ ua like ka hoʻomaka a me ka hopena. Hōʻike kēia i nā pahuhopu integer maikaʻi ʻole a pau: Me ka hoʻomākaukau ʻana, hiki ke ana ʻia ka lōʻihi inā a inā e puʻunaue ka mea puʻunaue nui loa.:

$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$

ʻAʻole pili kēia lula i ka hoʻomaka ʻana i nā ana ma ka hoʻomaka mua. No ka laʻana, me $4$ a me $7$ minuke $g=1$ , akā ma hope o $1$ minuke ʻaʻohe uaki kaʻawale. No laila ʻaʻole hiki iā ʻoe ke ʻike i ka hopena o kēia minuke. ʻO ke ana mai ka minuke $7$ a i $8$ i hōʻike ʻia ma luna wale nō ka hana no ka mea ʻaʻole helu ka hoʻomākaukau. Ke pane nei ka hōʻike i ka nīnau o ka mea hiki ma hope o ka hoʻomākaukau. Inā ʻoe e ʻimi nei i kahi kaʻina i ʻae ʻia me ka hoʻomākaukau ʻana a i ʻole ka hoʻomākaukau ʻana, e kōkua ka ʻimi ʻōnaehana ma lalo nei.

Hoʻomanaʻo ka palapala PHP i nā manawa holo ʻelua a me ka manawa i hala mai ka hoʻomaka ʻana o ke ana. No kēlā me kēia kūlana, e ho'āʻo i nā mea a pau $4$ Hiki: ʻaʻohe uaki, ʻo ka mua wale nō, ʻo ka lua wale nō a hoʻohuli paha i nā mea ʻelua. A laila kali ʻo ia a hiki i ka manawa aʻe e kahe ai. ʻO ka waiwai $-1$ hōʻike i ka hoʻomākaukau; ke komo ana start kau i ka manawa ana $0$. ʻAʻole e noiʻi hou ʻia nā kūlana i ʻike ʻia. Loaʻa ke kaʻina i loaʻa ma o kona mau mua. wait pili wale i ka mamao i ka hoʻokuʻu ʻana aʻe, ʻaʻole kahi ana manawa hou:

<?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;
}

Loaʻa a hoʻihoʻi paha ka ʻimi i kahi kaʻina hana i ʻae ʻia null, inā ʻaʻohe mea. Hoʻopili ia i nā hoʻomau a pau i ʻae ʻia a koi ʻia ka hoʻomākaukau kiʻekiʻe $(a+1)(b+1)(T+2)$ Mokuʻāina. No laila, makemake nui nā mea hoʻokomo nui i ka hoʻomanaʻo. Hoʻemi ʻia ka helu o ka huli ʻana, ʻaʻole ka manawa hoʻomākaukau. Hoʻololi ʻia nā manawa holo kūpono a me nā manawa kuhi i nā helu holoʻokoʻa me ka hoʻohana ʻana i ka denominator maʻamau. No nā manawa holo me ka ʻole o ka manawa maʻamau, no ka laʻana $1$ a $\sqrt{2}$, ʻAʻole kūpono kēia hulina integer palena.

Hope

ʻO ka pilikia hola hola0926

ʻO ka pilikia hola hola09
26