هناك ساعتان رمليتان: تعمل إحداهما بالكامل خلال \(4\) دقائق، والأخرى خلال \(7\) دقائق. كيف يمكنك قياس \(9\) دقائق بالضبط عندما يجب أن يبدأ القياس في المرة الأولى التي تبدأ فيها الساعات؟ لا يُسمح بساعة أخرى وعد الثواني والتخمين. كل ما عليك فعله هو قلب الساعة الرملية ومراقبتها عندما تكون الغرفة العلوية فارغة. لا ينبغي أن يستغرق الالتفاف أي وقت. ما نبحث عنه هو عملية يمكن من خلالها التعرف على نهاية الفترة الزمنية المرغوبة فقط من خلال الساعة الرملية.
نسمي الساعة بـ \(4\) دقائق \(A\) والساعة بـ \(7\) دقائق \(B\) . في البداية كل الرمال في القاع. نبدأ تشغيل الساعتين في نفس الوقت عن طريق قلبهما؛ من هذه اللحظة فصاعدًا، يتم احتساب \(9\) دقائق البحث. بعد ذلك، يمكنك دائمًا التداول عندما تصبح الساعة في الأعلى فارغة. لا يجوز لك تسليم إحدى الساعتين أو إحداهما أو كلتيهما، حتى لو كانت لا تزال قيد التشغيل. عليك الانتظار حتى نفاد الكمية في المرة القادمة. لا يسمح بالتوقف ووضع العلامات؛ يمكن للساعة الفارغة أن تظل واقفة. الحل يبدو مثل هذا:
- في الدقيقة \(0\) \(A\) و \(B\) يتم بدء التشغيل.
- في الدقيقة \(4\) \(A\) يكون فارغًا ويتم قلبه. يستمر \(B\) في العمل دون تغيير.
- في الدقيقة \(7\) \(B\) يكون فارغًا ويتم قلبه. لا يزال هناك \(1\) دقيقة متبقية في \(A\) .
- في الدقيقة \(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\) . يضمن Lemma الخاص بـ Bézout مطابقة الأعداد الصحيحة \(n,m\) إذا كان \(T\) مضاعفًا موجبًا لـ \(g\) . العلاقة التي تبحث عنها هي::
$$na-mb=T.$$
الأرقام \(n,m\) التي يقدمها Bézout يمكن أن تكون سالبة في البداية. لا يمكن تنفيذ عمليات التشغيل السلبية. ومع ذلك، يمكن زيادة كلا الرقمين دون تغيير الفاصل الزمني: نستبدلهما بـ \(n+kb/g\) و \(m+ka/g\) حيث \(k\) عدد صحيح موجب كبير بما فيه الكفاية. وبالتالي يتم إزاحة المرتين بنفس المقدار \(kab/g\) ؛ ويبقى اختلافهم \(T\) . وبذلك يصبح كلا الرقمين موجبين والأوقات المطلوبة هي في الواقع بعد بدء الساعات.
الآن يمكنك حساب الدورات الكاملة لكل ساعة. عندما تصبح الساعة \(m\) فارغة يبدأ القياس؛ وينتهي عندما تصبح الساعة الأولى فارغة للمرة \(n\) -th. توجد بالضبط وحدات زمنية \(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}\), هذا البحث عن الأعداد الصحيحة المحدودة غير مناسب.