তোমরা সবাই "The Tower of Hanoi" গেমটা খেলেছ হয়তোবা। ২০০০ সালে মুক্তি পাওয়া ZTE কোম্পানির গ্রামীণফোন মোবাইল গুলোতে এই গেম ছিল। এতে তিনটা টাওয়ার থাকতো। আটটা ডিস্ককে বাম থেকে ডানের টাওয়ারে সরাতে হত নানান নিয়ম মেনে। এটার জন্য সূত্রও ছিল, n
টা ডিস্ককে সরাতে (2n-1) বার সরাতে হত।
থাকুক ঐসব কথা। এখন আমরা খেলব লাঠির টাওয়ার খেলা। এটি হ্যানই গেমের চেয়ে লাখো গুণে সোজা। এই খেলায় দুইটা লাঠির টাওয়ার A আর B তে কিছু ডিস্ক থাকবে। A টাওয়ার থেকে একবারে কিছু ডিস্ক নিয়ে B টাওয়ারে রাখতে হবে (কিংবা এর উল্টা ঘটনা) যাতে করে দুই টাওয়ারে থাকা ডিস্কের সংখ্যা সমান হয়।
ইনপুট হিসেবে প্রতি লাইনে দুইটি করে অ-ঋণাত্মক পূর্ণসংখ্যা দেওয়া হবে। এই সংখ্যা দুটি যথাক্রমে A ও B টাওয়ারের ডিস্কের সংখ্যা প্রকাশ করবে। সংখ্যা দুটি স্পেস দ্বারা আলাদা করা থাকবে। ইনপুটের সংখ্যা দুটি সমান হলে প্রোগ্রাম শেষ হবে।
কতটি ডিস্ক সরালে উভয় টাওয়ারে ডিস্কের সংখ্যা সমান হবে তা প্রিন্ট কর। কোনোভাবেও যদি সরানোর পর ডিস্কের সংখ্যা সমান না হয় তবে impossible
কথাটি প্রিন্ট কর।
Input | Output |
---|---|
10 6 4 6 7 6 22 10 36 36 | 2 1 impossible 6 |
Problemsetter: Mushfiqur Rahman (mdvirus)