Uva 12050 – Palindrome Numbers

Problem Link

প্রবলেমটা একবার পড়ে আসো । তারপর দেখো :-
নরমাল ওয়েতে তুমি ২*১০ তম পেলিন্ড্রম সংখ্যা যদি বের করতে চাও তবে প্রিন্টতো দূরের কথা জেনারেটই করতে পারবে নাহ । এটা অনেক লং প্রসেস এই লং প্রসেসকে কিভাবে শর্ট করা যাই সেটা নিয়েই আমার এ লেখা ।

এই পোস্টের PDF Download করে নিতে পারো এখান থেকে পড়তে সুবিধা হবে । 
 
আমরা আগে একটা রেঞ্জ পর্যন্ত পেলিন্ড্রম কিভাবে থাকে সেটা একটু দেখি । ১-৯ পর্যন্ত পেলিন্ড্রম আছে ৯টা এর মধ্যে সবগুলো পেলিন্ড্রম সংখ্যাই ১ ডিজিটের । ১০-৯৯ পর্যন্ত পেলিন্ড্রম আছে ৯টা এর মধ্যে সবগুলো পেলিন্ড্রম সংখ্যাই ২ ডিজিটের । ১০০-৯৯৯ পর্যন্ত পেলিন্ড্রম আছে ৯০টা এর মধ্যে সবগুলো পেলিন্ড্রম সংখ্যাই ৩ ডিজিটের । তুমি কোন ডিজিটের low রেঞ্জ থেকে upper রেঞ্জ পর্যন্ত পেলিন্ড্রম জেনারেট করে এমন একটা কোড লিখ এবং সেখানে Cout++ করে দাও । পেলিন্ড্রম জেনারেট এর শেষে Cout প্রিন্ট করে দাও । রেঞ্জ অবশ্যই ডিজিট হিসাব করে দিবে। তখন তুমি দেখবে সংখ্যাগুলো এমন আসছে :-

রেঞ্জ
পেলিন্ড্রম
টোটাল পেলিন্ড্রম
ডিজিট
১-৯
১০-৯৯
১৮
১০০-৯৯৯
৯০
১০৮
১০০০-৯৯৯৯
৯০
১৯৮
১০০০০-৯৯৯৯৯
৯০০
১০৯৮
১০০০০০-৯৯৯৯৯৯
৯০০
১৯৯৮
১০০০০০০-৯৯৯৯৯৯৯
৯০০০
১০৯৯৮
১০০০০০০০-৯৯৯৯৯৯৯৯
৯০০০
১৯৯৯৮
১০০০০০০০০-৯৯৯৯৯৯৯৯৯
৯০০০০
১০৯৯৯৮
১০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯
৯০০০০
১৯৯৯৯৮
১০
১০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০
১০৯৯৯৯৮
১১
১০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০
১৯৯৯৯৯৮
১২
১০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০
১০৯৯৯৯৯৮
১৩
১০০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০
১৯৯৯৯৯৯৮
১৪
১০০০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০০
১০৯৯৯৯৯৯৮
১৫
১০০০০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০০
১৯৯৯৯৯৯৯৮
১৬
১০০০০০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০০০
১০৯৯৯৯৯৯৯৮
১৭
১০০০০০০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০০০
১৯৯৯৯৯৯৯৯৮
১৮
১০০০০০০০০০০০০০০০০০০-৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯৯
৯০০০০০০০০০
১০৯৯৯৯৯৯৯৯৮
১৯
Total Sum of palindrome
১০৯৯৯৯৯৯৯৯৮
   রেঞ্জ কলাম এর কোন কাজ নাই তবে এটা দ্বারা বুজাতছি যে সংখ্যাটার লিমিট কত হতে পারে । তার মানে ওই লিমিটের যতগুলা ডিজিট ততগুলা ডিজিটই হবে আমার পেলিন্ড্রমের । আবার ভেবো নাহ যে আমার পারসোনাল পেলিন্ড্রম । যাই হোক আমাদের দরকার ২*১০ তার মানে ১৮ ডিজিটের পেলিন্ড্রমের পর আর দরকার নাই কারণ আমাদের লিমিটের প্রায় খুব কাছে চলে আসছি (টোটাল পেলিন্ড্রম ১৮ নাম্বার কলাম দেখো) । কিন্তু জাজ তোহ আর বুজবে নাহ সেটা । কাছাকাছি আসলে তো আর হবে নাহ একুরেট হতে হবে । ২*১০ হতে কিন্তু এখনো ২ বাকি আছে (চার্টটা দেখো) আর  এই ২টা পেলিন্ড্রম খুজতে আমাকে আবার ১৯ ডিজিটের বিশাল সংখ্যা পাড়ি দিতে হবে এখন সেটা ২টা বা ১০০টা পেলিন্ড্রমই হোক নাহ কেনো ১৯ ডিজিটের সংখ্যা থেকে খুজতে আমাকে হবেই ।

যাই হোক আমরা বুজতে পারছি ২*১০পেলিন্ড্রমটি ১৯ ডিজিটের একটি বিশাল সংখ্যা যেটা বের করা আমাদের একটা চ্যালেঞ্জ (বাংলা ছবির ডাইলগ)। আমরা এখন জানি ২*১০ সংখাটি কত বড় হতে পারে তার মানে আমরা প্রবলেমের প্রায় ৫০% কাজ করে ফেলেছি (বোঝার ৫০% …কোডিং-এ এখনো হাত দেই নাই )।

এখন তুমি যেটা করবে সেটা হল একটা অ্যারের মধ্যে কত ডিজিটের কতগুলো পেলিন্ড্রম আছে সেটা সেভ রাখবে । ভাল করে পড় কত ডিজিটের কতগুলো পেলিন্ড্রম আছে সেটা ।  কিভাবে ? ওকে একটা উদাহরণ দেই :-


চার্ট দেখো আরো ভাল বুজতে পারবে । আর range নামে একটা ভেরিয়াবল রাখবে যার মাধ্যমে তুমি জানতে পারবে শুরু থেকে টোটাল পেলিন্ড্রম কত (Cumulative sum ) । এখন প্রশ্ন করতে পার এটা রাখার কি দরকার ? এটা রাখবে এই কারণেই যে ফাংশনে তুমি কাজ করছো সেটা কখন শেষ হবে । মানে ফাংশন থেকে বের হতে এটা সাহায্য করবে । আরেকবার দেখো চার্টের ডিজিট এবং পেলিন্ড্রম কলামটা দেখো একটা জিনিস বুজতে পারবে আমি আর বললাম নাহ নিজে বের কর ।

 
এখন মনে হয় বুজতে পারছো কিভাবে সেভ রাখবে । ধর আমি তোমাকে বললাম ৫ ডিজিটের কয়টা পেলিন্ড্রম আছে সেটা বের কর । এখন ঝটপট কোড করে ফেল । এমন ভাবে কোডটা করবে যেন সাথে সাথে উত্তর দিতে পারে আগেই যেন জেনারেট করা থাকে । তো বললাম ৫ ডিজিটের কি হবে pal [ 5 ] = 900 । কোড নাহ করে নিচে পড়া বা কোড দেখার কোন দরকার নাই নিজে চেষ্টা কর ।
 
কোডটা করে ফেলেছো নিশ্চয়ই । তাহলে এখন আমাকে বল যে পেলিন্ড্রম দেখতে কেমন ? এখন ভাবতে পার এটা আবার কেমন প্রশ্ন পেলিন্ড্রম কোনগুলা সেটা জিজ্ঞাস করতে পারি কিন্তু দেখতে কেমন এটা কিভাবে বলি । হুম দেখতে অনেক সুন্দর !!! ওকে ওকে বাদ দাও বলো যে পেলিন্ড্রম কি ?
 
আমরা কি জানি পেলিন্ড্রম সেগুলাই যেগুলা বামদিক থেকে এবং ডানদিক থেকে দেখতে একি রকম । আর কি জানি কোন সংখ্যাকে রিভার্স করলে যদি ওই সংখ্যাটাই থাকে তাহলে সেগুলা হল পেলিন্ড্রম । ঠিক আছে তবে এখন আমরা সেটা ভুলে যাব এবং এখন জানব যেটা সেটা হল পেলিন্ড্রম দেখতে এমন  বা পেলিন্ড্রম হল যে সংখ্যাগুলাকে দুইভাগে ভাগ করলে দুইটা পার্টই সমান হবে যদি প্রথম পার্টটাকে আমি উল্টা করে সাজাই । যেমন  ধর N তম পেলিন্ড্রম হল ২৪৪২ । আমি বুজলাম আমার N তম পেলিন্ড্রমের সংখ্যা ৪ ডিজিটের তাকে দুই ভাগে ভাগ করলাম তাহলে এখন হল ২ ডিজিট । কোন ভাবে আমি বের করলাম যে ২ টা ডিজিট হল ২৪ । এবার আমার কথা অনুযায়ী রিভার্স কর কি আসে ৪২ । এবার প্রথমটার সাথে এড করে দাও (এড মানে যোগ নাহ পিছনে যুক্ত করা ) । কি আসবে ? ২৪৪২ । হুম হয়ে গেছে আমার পেলিন্ড্রম । তার মানে প্রথম পার্টটা যদি আমরা বের করতে পারি আর সেটা প্রিন্টের করার পর প্রথম পার্টের উল্টাটা প্রিন্ট করে দেই তো আমরা আমাদের মূল পেলিন্ড্রমটা পেয়ে যাব । তাহলে আমরা ২*১০কে কনভার্ট করে কোথায় নিয়ে আসলাম দেখ ২*১০ তম পেলিন্ড্রমটা যদি ১৯ ডিজিটের হয় তবে তাকে ১৯+১/২ =১০ ডিজিট নিয়ে আসতে পারি । ১ বেশি ক্যান যোগ করলাম কারণ এটা বেজোড় সংখ্যা । জোড় হলে ১ যোগ করতাম নাহ ।

শেষ প্রবলেম সল্ভ করে ফেলেছি । এখন মনে মনে ভাবতে পার কিছুই বুজলাম নাহ প্রবলেম সল্ভ । যদি কিছুই নাহ বুঝে থাক তবে প্রথম থেকে আবার পরে আসো । আর যদি আল্কা কিছু বুজে থাক তো সামনে পড়তে পার নাহ হলে পড়ো নাহ কোন লাভ নাই সময়টা নষ্ট হবে শুধু শুধু ।
ধর N তম পেলিন্ড্রমটা বের করতে চাও । কিভাবে করবে ?

পার্ট বাই পার্ট যাব আস্তে আস্তে বুঝে বুঝে পড় । N তম পেলিন্ড্রমটা কত ডিজিটের সেটা বের করবে । তারপর তত ডিজিটকে দুই ভাগে ভাগ করবে প্রথম পার্টটা বের করে প্রিন্ট করবে তারপর প্রথম পার্টটা উল্টা করে প্রিন্ট করে দিবে ।

এখন N তম পেলিন্ড্রমটা কত ডিজিটের এবং কয়টা পেলিন্ড্রম আছে তা তুমি সহজেই বের করতে পারবে । ওই যে তুমি সেভ রেখে ছিলে pal অ্যারেতে ওইটার মাধ্যমে । এখন আমি বললাম ৯৫ তম পেলিন্ড্রম কোনটা । এখন আমাকে বলো ৯৫ তম পেলিন্ড্রমটা কয় ডিজিটের । হাতে কলমে যদি নাহ পার তবে তুমি যে প্রোগ্রামটি লিখেছো তাকে জিজ্ঞাস কর ৯৫ তম পেলিন্ড্রমটা কয় ডিজিটের । উপরের চার্টের টোটাল পেলিন্ড্রম কলাম দেখে বের কর কয় ডিজিটের এবং মিলাও ঠিক আছে কি নাহ । ওকে আমি বলে দিচ্ছি সংখ্যাটি ৩ ডিজিটের । কিভাবে করলাম ? তুমি যদি পার তো আর বলার দরকার নাই যদি নাহ পার তো দেখ :

৯ তম পেলিন্ড্রম + ৯ তম পেলিন্ড্রম = ১৮ তম পেলিন্ড্রম ।

১৮ তম পেলিন্ড্রমটা কয় ডিজিটের ২ ডিজিটের রাইট ?

ওকে এখন ১৯ থেকে ১০৮ পর্যন্ত তোহ ৩ ডিজিটের পেলিন্ড্রম । তো আমরা বুজতে পারছি ৯৫ অবশ্যই এই রেঞ্জের মধ্যে আছে । ওই রেঞ্জ যদি ৩ ডিজিটের হয় তো ৯৫ও  ৩ ডিজিটের ।
ডিজিট বের করে ফেললাম এখন ৩ ডিজিটের তোহ ৯০টা পেলিন্ড্রম আছে এর মধ্যে কোনটা ৯৫ তম পেলিন্ড্রম । সেটা বের করবে কিভাবে ?

৯ + ৯ + ৯০ = ১০৮ তাই নাহ । এখন ৯৫ তম পেলিন্ড্রম ১-১০৮ টা পেলিন্ড্রমের মধ্যে আছে আমরা জানি । Digit এর মান যখন ৩ তখন pal [ 3 ] = ৯০ কিন্তু  N < pal[ 3 ] থেকে ছোট । যতক্ষন N এর মান pal এর মান এর চেয়ে বড় হবে ততক্ষন বিয়োগ করতে থাকব । তোহ দেখি কিভাবে বের হয় :

N = ৯৫ ;
৯৫-৯ = ৮৬ কারণ N এর মান pal [ 1 ] এর থেকে বড় বিয়োগ করে দিব । এখন N = ৮৬ ।

আবার ৮৬-৯ = ৭৭ কারণ N এর মান pal [ 2 ] এর থেকে বড় বিয়োগ করে দিব । এখন N = ৭৭ ।

নেক্সটে যখন বিয়োগ করতে যাব দেখলাম pal [ 3 ] মানের চেয়ে N ছোট । আর বিয়োগ করব নাহ ।
এখন হয়ত তুমি বুঝে ফেলেছ যে ৯৫ তম পেলিন্ড্রমটা ৩ ডিজিটের । এবার যেটা করতে হবে সেটা হল ওই ৩ ডিজিটের যতগুলা পেলিন্ড্রম আছে তার মধ্যে থেকে পেলিন্ড্রম বের করা । ৩ ডিজিটের পেলিন্ড্রম কয়টা ৯০টা । এখন N এর লাস্ট মান কত ছিল ৭৭ । তো ৩ ডিজিটের ৯০টা পেলিন্ড্রমের ৭৭ তম পেলিন্ড্রমটাই আমার রেজাল্ট ।  

এখন আমাদের কাজ ৩ ডিজিটের ৭৭ তম পেলিন্ড্রমটা খুজে বের করা । খেয়াল কর প্রবলেমটা কিন্তু আস্তে আস্তে ছোট হয়ে আসছে । ৯৫ তম পেলিন্ড্রমটা খুজতে যেয়ে এখন আমার খোজা লাগছে ৩ ডিজিটের ৭৭ তম পেলিন্ড্রমটা ।
এখন আমরা পেলিন্ড্রম বানানো শুরু করব । পেলিন্ড্রমের প্রথম ডিজিটটা তো শূন্য কখনোই হবে নাহ । প্রথম ডিজিটটা বাদে বাকি সব ডিজিটই শূন্য হতে পারে । যেমন ৩ ডিজিটের  শুরু থেকে পেলিন্ড্রম গুলা হতে পারে :-  
প্রথম পেলিন্ড্রমটা খেয়াল কর ১০১ । এর পরবর্তী পেলিন্ড্রম হল ১১১, তারপরের ৩ পেলিন্ড্রমটা হল ১২১ , তার মানে মাঝে যেটা আছে সেটা চেঞ্জ হতছে । কিভাবে চেঞ্জ হতছে ০-৯ পর্যন্ত । একি ভাবে ২০২ হবে ৩০৩ এভাবে ৯০৯ পর্যন্ত চলবে । যখন মাঝে ৯ হচ্ছে তখন ১৯১ থেকে ২০২ এ চলে যায় মানে ১০১ (১ এর কাজ শেষ) থেকে ২০২ (২ এর কাজ শুরু) এ যাতছে । ১-এ ১০টা পেলিন্ড্রম ২-এ ১০টা পেলিন্ড্রম এভাবে ১-৯ পর্যন্ত ৯*১০ = ৯০ টা  পেলিন্ড্রম । ১ মানে বুঝাতছি ১০১ ,২ মানে ২০২ ।
এখন ১৯ তম পেলিন্ড্রমটা ১০১ যেটা ৩ ডিজিটের প্রথম পেলিন্ড্রম । উপরে যেহেতু দেখেছি ১০ করে যেহেতু বাড়ছে তো ২৯ তোম পেলিন্ড্রমটা ২০২ । ৩৯ তম পেলিন্ড্রমটা ৩০৩ , ৪৯ তম পেলিন্ড্রমটা ৪০৪ , ৫৯ তম পেলিন্ড্রমটা ৫০৫ , ৬৯ তম পেলিন্ড্রমটা ৬০৬ , ৭৯ তম পেলিন্ড্রমটা ৭০৭ , ৮৯ তম পেলিন্ড্রমটা ৮০৮ , ৯৯ তম পেলিন্ড্রমটা ৯০৯ । তাহলে ৯৫তম পেলিন্ড্রমটা মানে ৩ ডিজিটে ৭৭ তম পেলিন্ড্রমটা অবশ্যই ৮৯ এবং ৯৯ তম পেলিন্ড্রম এর ভিতরে । ৮৯ তম পেলিন্ড্রমটা কি ছিল ৮০৮ ,৯০ তম পেলিন্ড্রমটা হবে ৮১৮ , এভাবে ৯৫ হবে ৮৬৮ । বুঝতে ভুল কর নাহ ৯৫ তম পেলিন্ড্রম মানে টোটাল পেলিন্ড্রম আর ৭৭ পেলিন্ড্রম মানে ৩ ডিজিটের পেলিন্ড্রম গুলার মধ্যে ৭৭ নাম্বার পেলিন্ড্রম ।
৭৭ তম পেলিন্ড্রমের প্রথম ডিজিট তৈরি করার জন্য ৭৭তম পেলিন্ড্রম কোন ঘরে আছে সেটা বের করতে হবে । ১-৯ পর্যন্ত প্রত্যেক ডিজিটে ১০ টা পেলিন্ড্রম আছে ১০১,১১১,১২১,১৩১,১৪১,১৫১,১৬১,১৭১,১৮১,১৯১ এরকম । ১০১ -৩ ডিজিট থেকে কনভার্ট ৩+১/২=২ ডিজিটে । মানে ১০১ –এ ১০(১০১ এর ২ ডিজিট) হবে তাহলে ২০১ এর কি হবে ২০ । ১ ক্যান যোগ করলাম কারণ ৩ একটা বেজোড় সংখ্যা
এখন ২ ডিজিটের প্রথম সংখ্যাটা বানাব । N ছিল ৭৭ । ভাল করে দেখ :
স্টেপ ৮ তো ৮ কে আমরা একটা অ্যারেতে সেভ রাখব কারণ আমরা প্রথম ডিজিট পেয়ে গেছি । এখন ১০ ক্যান বিয়োগ করলাম । ২ ডিজিটের সবচেয়ে ছোট ভেলু যেটা সেটা দিয়ে বিয়োগ করব । এখন যদি (ডিজিট+১)/২ = ৩ হয় তখন কি করব ১০ দিয়ে বিয়োগ করব নাহ ১০ কি ৩ ডিজিটের সবচেয়ে ছোট ভেলু ? আমরা তখন ১০০ দিয়ে বিয়োগ করব । কোডটা কেমন হবে একটু দেখি –
যখন ১০ বা ১০০ যাই আসুক P এর মান সেটা ডিপেন্ড করবে ডিজিটের উপর । ডিজিট যদি ১ হয়  P হবে ১, ডিজিট যদি ২ হয়  P হবে ১০ আর ডিজিট যদি ৩ হয়  P হবে ১০০ এভাবেই বাকি গুলা ।P থেকে N ছোট অথবা সমান হলে স্টেপটা অ্যারেতে সেভ রাখব এবং প্রথম ডিজিট আমরা পেয়ে যাব ।  
এবার ২ নাম্বার ডিজিট :-   
২ ডিজিট ছিল ১ ডিজিট পেয়ে গেছি বাকি থাকল ১ টা ডিজিট । এবার

P এর মান ১ কেন হল এটা প্রথম ডিজিট তৈরি করার সময় বলেছি । আর কি বলেছি N এর মান P এর থেকে ছোট অথবা সমান হলে অ্যারেতে আমরা স্টেপটা সেভ রাখব এবং পরের ডিজিট খোজার জন্য চলে যাব । P এর মান ১ ছিল N এর মানও ১ তাই ৬ টা আমদের স্টেপ ৬ কে অ্যারেতে সেভ রাখব । 

পরের ডিজিট যেই খুজতে যাব দেখলাম ২টা ডিজিটই আমার দরকার ছিল । এখন পেলিন্ড্রম তৈরি করা শেষ এবার প্রিন্ট করব ।

অ্যারেতে কি কি আছে
ইনডেক্স হল ০ আর ১ । আগে অ্যারেতে যেটা সেভ আছে সেগুলা প্রিন্ট করি । তারপর ডিজিট যদি বেজোড় সংখ্যা হয় তবে অ্যারে লাস্টের এক ঘর সামনে থেকে প্রিন্ট করা শুরু করব । আর যদি জোড় হয় তবে লাস্টের থেকে প্রিন্ট করব । ৩ ডিজিট বেজোড় সংখ্যা অ্যারে লাস্টের এক ঘর সামনে কি আছে ৮ । তাহলে আমরা অবশেষে পেয়ে গেলাম ৯৫ তম পেলিন্ড্রমটি হতছে ৮৬৮ ।
কিভাবে প্রিন্টটা করবে এখানে যদি বুঝতে সমস্যা থাকে তবে একটা উদাহরণ দিলেই বুজতে পারবে :-  
 
ধর একটা পেলিন্ড্রমের ৫ টা ডিজিট আছে । আমাদের কন্ডিশন কি ছিল সংখ্যাটি যদি বেজোড় হয় তবে ডিজিট+১/২= ৩ । আমরা পেলাম ৩টা ডিজিট । ডিজিট গুলা সাপোস বের করলাম 253  তাই নাহ ? সবগুলা অ্যারেতে সেভ আছে  0 1 2 নাম্বার ইনডেক্স অনুযায়ী । আগে সেভ অ্যারেটা প্রিন্ট করে দেই । তারপর লাস্টের ইনডেক্স কি আছে ২ এর এক ঘর সামনের ইনডেক্স কি আছে ১ থেকে প্রিন্ট করা শুরু করব জির পর্যন্ত । ১ নাম্বার ইনডেক্সে আছে → 5 , ০ নাম্বার ইনডেক্সে আছে → 2 । তাহলে আমার পেলিন্ড্রমটা কি হল ২৫৩২৫ ।     
আমি অনেক অনেক অনেক ধন্যবাদ দিব আনিন্দ ভাইকে যে এত সুন্দর ভাবে প্রবলেমটা আমাকে বুঝানোর জন্য । আর সেটাই বিস্তারিত তোমাদের বললাম । আমি খুব ভাল পারি তা নাহ আমিও ভুল করতে পারি তো কোনো জাইগায় ভুল হলে একটু জানাবে । আমি অনেক ক্লান্ত । তুমি কি বুঝলা আমি জানি নাহ তবে যদি নাহ বুঝে থাক কোথায় বুঝো নাই সেটা একটু কমেন্টে জানিও অথবা আমাকে মেইল করতে পার । ভাল থাক খুব তাড়াতাড়ি আবার লিখব আরো একটা ইন্টারেস্টিং প্রবলেম নিয়ে ।

Code :-

Posted by Shipu Ahamed

Leave a Reply