இரண்டு மணிநேர கண்ணாடிகள் உள்ளன: ஒன்று முழுமையாக \(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\) உள்ளது. \(T\) என்பது \(g\) இன் நேர்மறை மடங்காக இருந்தால் \(n,m\) பொருந்தக்கூடிய முழு எண்களுக்கு Bézout இன் லெம்மா உத்தரவாதம் அளிக்கிறது. நீங்கள் தேடும் உறவு::
$$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}\), இந்த வரையறுக்கப்பட்ட முழு எண் தேடல் பொருத்தமானது அல்ல.