Skip to main content

Posts

Showing posts from December, 2016

[ UVa ] 11747 - Heavy Cycle Edges

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

[ UVa ] 599 - The Forrest for the Trees

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.  আর সাইজ শূন্য থেকে বড় হলে সেটা একটা ট্রি ।  কোড : হ্যাপি কোডিং ;)

[ UVa ] 10928 - My Dear Neighbours

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

[ UVa ] 11991 - Easy Problem from Rujia Liu ?

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

[ UVa ] 11690 - Money Matters

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

[ UVa ] 10685 - Nature

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

[ UVa ] 11631 - Dark roads

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

[ UVa ] 11953 - Battleships.

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

[ UVa ] 11749 - Poor Trade Advisor.

আমরা ইনপুট নেয়ার সময়ই 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...

[ UVa ] 11470 - Square Sums

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

[ UVa ] 10946 - You want what filled ?

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

[ UVa ] 11244 - Counting Stars

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

[ UVa ] 10336 - Rank the language_ranks

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

[ UVa ] 785 - Grid Colouring.

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

CPP তে map কেন এবং কিভাবে সেটা ব্যাবহার করতে হয়

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 হতে হবে । ইনডেক্স কখ...

Setup was unable to create a new system partition এই সমস্যা সমাধান করার উপায় [ আগে হার্ডডিস্ক এর সব ডাটা ব্যাকআপ করে রাখেন ]

এই সমস্যা টি সমাধান করার জন্য আপনাকে 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 । এখন আমরা আমাদের পেনড্রাইভের মধ্যে যে উইন্ডোজ ফাইল আছে সেগুলো এই নতুন ক্রিয়েট করা পার্টিশনে কপি করব এবং আমরা সেখান থেকে উইন্ডোজ ইন্সটল করব ।  এটা করার জন্য নিচের ধাপগুলি অনুসরণ করতে হবে । মনে করি আ...

উইন্ডোজ এর Diskpart এর কিছু কমান্ড নিয়ে কাজ করা

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

ওরাকলে একটা ফাংশন থেকে কি ভাবে একটা টেবিল রিটার্ন করা যায় [ Table return in Oracle PL/SQL function]

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