কম্পিউটার বিজ্ঞান

এই সমস্যা তে আমাদের গ্রাফে যদিগুলি সাইকেল আছে প্রত্যেক টা সাইকেলে যে edge আছে তাদের মধ্যে ম্যাক্স ওয়েট ধারি এজ এর ওয়েট গুলিকে প্রিন্ট করেত হবে । অর্থাৎ আমাদের গ্রাফে যদি ২ টা সাইকেল থাকে তবে ঐ ২ সাইকেল এজ গুলির মধ্যে ম্যাক্স ২ টা প্রিন্ট করতে হবে । [ ২য় ইনপুট লক্ষণীয় ]    আমরা যদি Kruskal Algorithm ব্যাবহার করি তবে খুব সহজেই এই সমস্যার সমাধান করতে পারব ।  Kruskal এ প্রত্যেক বার যখন নতুন কোন এজ আমাদের Spanning Tree তে যোগ করতে যাব তখন  দেখব তাদের Node দুইটির ফাদার একই কি না ?  যদি ফাদার একই হয় তার মানে এই এজটা নিলে আমাদের সাইকেল তৈরি হবে । আর আমাদের এই এজের ওয়েট ই দরকার ।  ওয়েট গুলো কে আমরা অন্য একটা ভেক্টরে জমা করা রাখব ।  শেষে যদি দেখা যায় আমাদের ভেক্টর টি ফাকা রয়ে গেছে তার মানে আমাদের গ্রাফে কোন সাইকেল নেই । এই অবস্থায় আমাদের কে forest প্রিন্ট করতে হবে ।  কোড : হ্যাপি কোডিং :D

Given a forest you are to write a program that counts the number of trees and acorns. কোন একটা গ্রাফে Number of Connected Component = মোট Edge সংখ্যা - মোট ভারটেক্স সংখ্যা ।  আমরা যদি Adjacent List বানায় তবে যে Node এর Adjacent List এর সাইজ শূন্য সেটা একটা Acorns.  আর সাইজ শূন্য থেকে বড় হলে সেটা একটা ট্রি ।  কোড : হ্যাপি কোডিং ;)

এই সমস্যা তে আমাদের কে minimum number of neighbours প্রিন্ট করতে হবে । যদি মিনিমাম একাধিক থাকে তবে তাদের সবাইকে প্রিন্ট করতে হবে ।  এটা করার জন্য আমরা একটা Adjacent List বানাতে পারি । এবং এই লিস্টের যেটা মিনিমাম সেটা বের করতে হবে  ।  পরে দেখব এই মিনিমাম টা কয়টার সাথে মিলে যায় । তাদের সবাই কে প্রিন্ট করে দিব ;) কোড : হ্যাপি কোডিং :)

এই সমস্যা তে আমাদের কে n এর যে ভিন্ন ভিন্ন মান দেয়া থাকবে তাদের কে নিয়ে আমাদেকে এমন ভাবে Adjacent List বানাতে হবে যেখানে n এর ভালুর সাথে সাথে ওই ভালুটার ইনডেক্স ও জমা রাখা যাবে ।  এখন আমাদের কে দেখতে হবে k এর মানটা v এর যে Adjacent List আছে সেটার থেকে ছোট নাকি বড় ।  যদি যদি ছোট হয় বা সমান হয় তবে আমরা সেটার v এর  ইনডেক্স প্রিন্ট করে দিব । আর যদি বড় হয় তবে ওই ইনডেক্স টা আমাদের Adjacent লিস্ট এ নাই । তাই আমাকের কে শূন্য প্রিন্ট করতে হবে ।  সমস্যা তে যে ইনপুট দেয়া আছে সেটা দিয়ে আমরা যদি Adjacent List বানায় তবে সেটা দেখতে এই রকম হবে 1  1 2  2  2 3  3 4 কোড : হ্যাপি কোডিং :)

এই সমস্যা তে আমাদের ফ্রেন্ডদের মাঝে যতগুলি আলাদা আলাদা গ্রুপ আছে সেই গ্রুপ গুলোর সবগুলির যোগফল যদি আলাদা আলাদা ভাবে শূন্য হয় তবে POSSIBLE প্রিন্ট করেত হবে । না হলে IMPOSSIBLE প্রিন্ট করত হবে ।  যেমন ধরে নিলাম আমাদের ৪ টা ফ্রেন্ডেদের গ্রুপ আছে এবং প্রত্যেক গ্রুপে ২/৩ জন করে ফ্রেন্ড আছে । এখন যদি এই ৪ টা গ্রুপের Individually খরচ এর যোগফল যদি শূন্য হয় তবেই কেবল  POSSIBLE হবে ।  যদি m = 0 হয় এবং সবার খরচ যদি ০ হয় তবে কিন্তু POSSIBLE প্রিন্ট করতে হবে :)  কোড : হ্যাপি কোডিং :)

যে ক্রিয়েচারের এর সেট সব থেকে বড় সেটার মোট ক্রিয়েচার সংখ্যা প্রিন্ট করতে হবে :)  Union-Find Disjoint Sets ব্যাবহার করলে খুব সহজেই এই কাজটা করা যাবে ।  কোড :  হ্যাপি কোডিং :D

হ্যাপি কোডিং :)

প্রথমে আমাদের কে বের করতে হবে Byteland এর রাস্তা গুলোর বর্তমান লাইটিং খরচ কত । এরপর আমাদের কে Byteland এর রাস্তাগুলো  কিভাবে লাইটিং করলে সবচেয়ে কম খরচ হবে এবং সেই খরচ টা কত সেটা বের করতে হবে । এটা বের করার জন্য আমরা Minimum Spanning Tree Algorithm ব্যাবহার করতে পারি ।  শেষে আমরা আমাদের MST থেকে পাওয়া খরচ কে আমাদের মোট খরচ থেকে বাদ দিব তাহলেই আমাদের সমস্যার সমাধান হয়ে যাবে কোড : হ্যাপি কোডিং :)

এখানে আমাদেকে বের করতে হবে য়ুদ্ধ শেষে কয়টা য়ুদ্ধ জাহাজ ভাসমান অবস্থায় থাকবে ।   x দিয়ে বলা হচ্ছে এটা জাহাজ বা জাহাজের অংশ । আর @ দিয়ে বলা হচ্ছে ওই জাগায় বোম আঘাত করেছিল এবং ' . ' মানে ফাকা জায়গা ।  আমরা আমাদের গ্রিডের প্রথম থেকে য়ুদ্ধ জাহাজ খোজা শুরু করবো । যদি x পাই তার মানে এখানে  একাটা  য়ুদ্ধ জাহাজ পেয়ে গেছি আমরা এই x এর আশেপাশে যত x ও @ আছে সেগুলো ' . ' দিয়ে পরিবর্তন করে দিব । যাতে করে একই জাহাজ কে আমরা একাধিক বার হিসাব না করি ।  আমাদের কে আশেপাশে ৪ দিকে গিয়ে চেক করতে হবে ।  সব শেষে আমরা মোট কতটা জাহাজ ভাসমান অবস্থায় পেলাম সেটা প্রিন্ট করে দিব ।  কোড : হ্যাপি কোডিং :D

আমরা ইনপুট নেয়ার সময়ই max_ppa এর মান বের করবো । এখন ১ নং শহর থেকে যাত্রা শুরু করে n পর্যন্ত সব শহরেই যাব যদি না সেই শহর এ আমরা আগে কখনো গিয়ে থাকি।  আমরা কোন একটা শহর থেকে যাত্রা শুরু করলে ওই শহর থেকে যতগুলি শহরে যাওয়া যায় তার সবগুলি তে যাওয়ার জন্য চেষ্টা করবো  যদি একটা শহর u থেকে v তে যেতে PPA এর মান max_ppa এর সমান না হয় তবে আমরা সেই রাস্তাটা কে বাদ দিয়ে continue করবো ।  কোন এটা শহর থেকে যাত্রা শুরু করলে মোট কয়টা শহরে যাওয়া যায় সেটা number_of_city তে জমা করে রাখব ।  শেষে ম্যাক্সিমাম number_of_city ই হল আমাদের মহান সিজার সাহেবের Provience [ উপনিবেশ ] । যেটা খুজে বের করার জন্য তিনি অস্থির হয়ে গেছেন :P   কোড করার আগে : আমাদের যদি একই road কয়েক বার ইনপুট দেয় এবং তাদের PPA যদি আলাদা আলাদা হয় যেমন : [ a, b ] = 10,  [ b, a ] = 20,  [ a, b ] = -111 তবে আমাদের কে ম্যাক্সিমাম PPA [ a, b ]=  20 কে নিতে হবে ।  PPA of that road [ fits in a signed 32 bit variable ] তার মানে PPA কিন্তু নেগেটিভ হতে পারে । তাই max_ppa এর মান শুরুতে -2147483648...

আমরা যদি একটু চিন্তা করি তবে এখানে একটা Pattern দেখতে পাব ।  আমাদের n এর মান [ ১, ২ ] এর জন্য মোট স্কোয়ার হবে ১ টি, [ ৩, ৪ ] এর জন্য ২ । [ ৫, ৬ ] এর জন্য ৩ । [ ৭, ৮ ] এর জন্য ৪ এবং [ ৯, ১০ ] এর জন্য মোট ৫ টি স্কোয়ার হবে ।  আমরা প্রথমে n ইনপুটের জন্য কয়টা স্কোয়ার বানানো যায় সেটা বের করবো । মনে  করি সেটা আমার n_square এ জমা করে রেখেছি । এখন আমাদের কে প্রতি n_square এর জন্য যে স্কোয়ার গঠন করা যায় তার যোগফল বের করতে হবে ।  শেষে আমরা আমাদের প্রতি স্কোয়ার এর যোগফল আলাদা আলাদা করে প্রিন্ট করবো ।   কোড : হ্যাপি কোডিং :)

আমরা আমাদের আইল্যান্ড থেকে একটা করে পজিশন রিড করবো । যদি ' . ' পাই তবে সেটা স্কিপ করবে ।  এখন প্রত্যেক টা গর্তের জন্য সেখানে Flood Fill চালাবো । আমাদের কে  পাশাপাশি ৪ দিকে যেতে হবে এবং  হিসাব করতে হবে  ওই একই ধরনের ক্যারেক্টার আসে পাশে কয়টা আছে ।   ওই ক্যারেক্টার ছাড়া অন্য  কোন ক্যারেক্টার পাই তবে আমাদের কে সেখান থেকে ব্যাক করতে হবে ।  একই ধরনের কয়টা ক্যারেক্টার পাওয়া গেলও সেটা আমাদের rank_list এ ওই ক্যারেক্টার সহ জমা করে রাখতে হবে ।  পুরা আইল্যান্ড যখন ভ্রমণ করা শেষ তখন আমাদের  rank_list কে সমস্যা তে বর্ণিত শর্ত অনুসারে সর্ট করতে হবে ।  rank_list এর সাইজ ৫০ * ৫০ এর একটু বেশি করে রাখা নিরাপদ ।   কারণ আমাদের আইল্যান্ড এর প্রত্যেক টা পজিশন যদি আলাদা আলাদা হোল হয় সেই ক্ষেত্রে যদি rank_list এর সাইজ ছোট হয় তবে রানটাইম এরর খেতে হবে :)  কোড : হ্যাপি কোডিং :)

আমরা আমাদের sky কে শুরু থেকে রিড করা শুরু করবো ।  আমরা যদি কোন পজিশনে ' * ' পাই তবে সেখানে DFS / BFS চালায়া দিবে এবং ' * ' এর পরিবর্তে ' . ' সেট করে দিব ।  DFS / BFS ফাংশনের মধ্যে Count করবে সেখানে কয়টা Adjacent স্টার আছে ।  এর পর Count এর মান কম্পেয়ার করে দেখব সেটা ১ কি না  যদি ১ হয় । তার মানে ওটা একটা স্টার । এবং আমরা এই স্টার Count করবো ।  আর যদি ১ এর থেকে বেশি হয় তবে সেটা স্টার না অন্য কোন বস্তু [ like moon, comet, sun or UFOs ]  হতে পারে । তাই সেটা স্কিপ করবো ।  কোড : হ্যাপি কোডিং :)

গ্রিড থেকে একাটা করে ক্যারেক্টার নিতে হবে এবং সেই ক্যারেক্টারের উপর ভিত্তি করে Flood Fill চলাতে হবে । যে ক্যারেক্টার নিলাম সেটা Count করে একটা অ্যারে তে জমা রাখতে হবে এবং  Visited মার্ক করে রাখতে হবে ।  আবার যদি একই ক্যারেক্টার আসে তবে সেটাকেও একই জায়গাই Count করে রাখতে হবে ।  যে অ্যারে তে আমরা Count করে রাখলাম সেই অ্যারের Count ও ইনডেক্স কে অন্য একটা Structure এর মধ্যে রেখে দিতে হবে । এই Structure এর মধ্যে প্রত্যেক ল্যাঙ্গুয়েজ এর নামে ও তার rank জমা করা থাকবে ।  এখন আমাদের কে এই Structure কে সর্ট করার সময় দেখতে হবে যদি দুটি ল্যাঙ্গুয়েজের rank একই হয় তবে Alphabetically যেটা আগে সেটা আগে প্রিন্ট করতে হবে ।  কোড : হ্যাপি কোডিং :)

প্রথমে Contours char কে খুজে বের করত হবে । একটা সেট এ একটাই Contours char থাকবে ।  এখন একটা করে লাইন রিড করবো এবং দেখব সেখানে marking char আছে কি না । যদি থাকে তবে সেই char টি একটি ভেক্টরে জমা করে রাখব এবং এর পজিশন অন্য একটি ভেক্টরে জমা করে রাখব ।  আমরা যদি লাইন রিড করতে করতে কোন একটা লাইনের শুরু তে ' _ ' পেয়ে যাই তার মানে এখন আমাকে রিড করা গ্রিড টি Execute করেত হবে ।  এই অবস্থায় আমরা আমাদের প্রত্যেক marking char এর জন্য  DFS / BFS চালায়া দেই এবং সব শেষে আমাদের গ্রিড কে প্রিন্ট করি তাহলেই আমাদের সমস্যা সমাধান হয়ে যাবে ।  কোড :  হ্যাপি কোডিং :)

C++ এর STL [ Standard Template Library ] এ কিছু কমন Data Structure ইমপ্লিমেন্ট করা আছে যেমন, vector, set, list, map, queue, deque, priority queue stack, bitset ইত্যাদি । এগুলো কে আমরা আমাদের প্রয়োজন অনুসাতে খুব সহজেই ব্যাবহার করেত পারি । আজকে আমরা এখানে map নিয়ে কিভাবে কাজ করা যায় সেটা নিয়ে আলোচনা করবো । কারণ উপরে আমরা যেগুলোর নাম লিখেছি তার মধ্যে map সবচেয়ে মজাদার । আমরা নিশ্চয় অ্যারে ব্যাবহার করেছি । অ্যারে তে আমরা কি করি ? আমরা অ্যারে এর টাইপ লিখি তারপর তার নাম দেই , তারপর তার সাইজ বলে দেই । আমাদের যদি ১০ সাইজ এর int টাইপ অ্যারে লাগে তখন আমরা লিখি 1 int arr[ 10 ]; value রাখার জন্য এবং পরে সেগুলো প্রিন্ট করার জন্য আমরা আমাদের অ্যারে এর ইনডেক্স ব্যাবহার করি 1 2 3 4 5 6 7 8 // for input for ( int i = 0 ; i < array_size; i ++ ) { cin >> arr[i]; } // for output for ( int i = 0 ; i < array_size; i ++ ) { cout << arr[i] << endl; } অ্যারে ইনডেক্স কিন্তু সবসময় int হতে হবে । ইনডেক্স কখ...

এই সমস্যা টি সমাধান করার জন্য আপনাকে USB Flash Dive থেকে উইন্ডোজে boot করতে হবে । তারপর যখন Windows Installation উইন্ডো আসবে । তখন Shift + F10 চাপুন । এর ফলে  cmd [ command prompt ] ওপেন হবে ।  এখন cmd তে লিখুন diskpart . Disk part ওপেন হলে সেখানে যদি আপনি list disk কমান্ড দেন তবে আপনার এই মুহূর্তে কয়টা হার্ডডিস্ক আছে তার একটা লিস্ট দেখাবে । আপনার যদি ১ টা হার্ডডিস্ক থাকে তবে দেখাবে Disk 0 আপনর হার্ড ডিস্ক এর সব ডাটা ব্যাকআপ করে রাখেন তার পর  নিচের ধাপ গুলি অনুসরণ করুন  কনসোলে ডিস্কপার্ট এ ঢুকুন তার জন্য diskpart লিখতে হবে ।  select disk 0 create partition primary size = SSS ; এখানে SSS হল আপনি যে সাইজ নিতে চান  select partition 1 active format fs=ntfs quick assign exit   এখন আপনার ক্রিয়েট করা primary partition টি bootable । এখন আমরা আমাদের পেনড্রাইভের মধ্যে যে উইন্ডোজ ফাইল আছে সেগুলো এই নতুন ক্রিয়েট করা পার্টিশনে কপি করব এবং আমরা সেখান থেকে উইন্ডোজ ইন্সটল করব ।  এটা করার জন্য নিচের ধাপগুলি অনুসরণ করতে হবে । মনে করি আ...

অনেক সময় দেখা যায় যে উইন্ডোজ দেয়ার সময় আমরা আমাদের হার্ডডিস্ক কে গুই ব্যবহার করে আমাদের প্রয়োজন অনুসারে ভাগ করতে পারি না । সেই ক্ষেত্রে আমারা যদি ডিস্কপার্ট সফটওয়্যার টি ব্যাবহার করি তবে সহজেই সেটা করতে পারব ।  উইন্ডোজ দেয়ার সময় যখন Install Windows অপশন আসে তখন আমারা যদি Shift + F10 চাপি তবে উইন্ডোজ এর কমান্ড লাইন চলে আসবে । সেখানে যদি আমরা diskpart লিখলেই diskpart ওপেন হবে । এখানে আমরা ডিস্কপার্ট এর বিভিন্ন কমান্ড ব্যাবহার করতে পারব ।     এখন দেখব ডিস্কপার্ট এর বিভিন্ন কমান্ড কিভাবে ব্যাবহার করা যায় ।  আমার কয়টা হার্ড ডিস্ক আছে আছে সেটা দেখার জন্য list disk লিস্ট থেকে কোন একটা হার্ডডিস্ক কে সিলেক্ট করার জন্য  select Disk 0; ডিস্ক ০ কে সিলেক্ট করবে সিলেক্ট করা হার্ড ডিস্ক এর আন্ডারে কয়টা পার্টিশন আছে সেটা দেখার জন্য list partition primary partition ক্রিয়েট করার জন্য কমান্ড  create partition primary size = sss    এটার ড্রাইভ লেটার দেয়ার জন্য লিখতে হবে assign letter = 'D' এটা কে ntfs এ ফরমেট করার জন্য ল...

টেবিল ক্রিয়েট করা জন্য কোড : মনে করি আমর উপরের মত করে একটা টেবিল তৈরি করেছি । এখন আমরা এমন একটা ফাংশন বানাতে চাচ্ছি যেটা ওই টেবিল থেকে কিছু কলাম বা সবগুলি কলাম নিয়ে নতুন নতুন একটা টেবিল আমাদের কে রিটার্ন করবে কিছু শর্তের উপর নির্ভর করে । এটা করার জন্য প্রথমে ওই টেবিল থেকে আমি যে যে কলাম নিতে চাই তার সবগুই নিয়ে এটা অবজেক্ট টাইপ বানাতা হবে নিচের মত করে । আমি টাইপ টির নাম দিয়েছি obj_type . আমরা যে অবজেক্ট টাইপ [ obj_type ] বানালাম সেই টাইপের নতুন একটা [ obj_of_table ] একই ধরনের অবজেক্ট বানাতে হবে নিচের মত করে । আমাদের নতুন টাইপ এর নাম দিলাম obj_of_table ফাংশনের রিটার্ন টাইপ হিসাবে কিন্তু এটাই ব্যবহার করতে হবে । এখন আমরা টেবিল রিটার্ন করার জন্য ফাংশন বানাতে পারি । এই ফাংশনের রিটার্ন টাইপ হবে obj_of_table এবং টেবিল টি আমরা new_table নামের ভারিয়েবলে জমা করে রাখব এবং সব শেষ আমরা new_table কে রিটার্ন করে দিব । সব কাজ শেষ :) এখন ফাংশনটি কল করার পালা । মনে করি ফাংশনের প্যারামিটার হিসাবে আমি আইডি 10 পাঠাব এবং যার আইডি এই আইডির সাথে মিলে যাবে সেই অনুসাতে টেবিল রিটার্ন করবে । ফাংশ...