Կան երկու ավազի ժամացույցներ. մեկը ամբողջությամբ աշխատում է \(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.$$
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}\), այս վերջավոր ամբողջ թվի որոնումը հարմար չէ: