দুটি ঘন্টার চশমা আছে: একটি সম্পূর্ণভাবে \(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\) রয়েছে। Bézout-এর লেমা গ্যারান্টি দেয় যে পূর্ণসংখ্যা মিলছে \(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\) পর্যন্ত পরিমাপ শুধুমাত্র কাজ করে কারণ প্রস্তুতি গণনা করা হয় না। প্রমাণটি এইভাবে প্রস্তুতির পরে কী সম্ভব সেই প্রশ্নের উত্তর দেয়। আপনি যদি প্রস্তুতি সহ বা ছাড়া একটি অনুমোদিত প্রক্রিয়া খুঁজছেন, নিম্নলিখিত পদ্ধতিগত অনুসন্ধান সাহায্য করবে.
পিএইচপি স্ক্রিপ্ট পরিমাপ শুরু হওয়ার পর থেকে চলমান অবশিষ্ট সময় এবং যে সময় অতিবাহিত হয়েছে উভয়ই মনে রাখে। এই ধরনের প্রতিটি অবস্থার জন্য, এটি সব চেষ্টা করুন \(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}\), এই সসীম পূর্ণসংখ্যা অনুসন্ধান উপযুক্ত নয়.