এই সমস্যায়, আমাদের একটি স্ট্রিং দেওয়া আছে যা একটি সংখ্যা রিপ্রেজেন্ট করে। এখন আমাদের স্ট্রিংটিকে দুটি অংশে ভাগ করতে হবে যাতে প্রথম অংশ A দিয়ে বিভাজ্য হয় এবং দ্বিতীয় অংশ B দিয়ে বিভাজ্য হয় (A এবং B দুটি পূর্ণসংখ্যা দেওয়া আছে)। উদাহরণ −
ইনপুট: str = "123", a = 12, b = 3 আউটপুট: YES 12 3 "12" হলো a দিয়ে বিভাজ্য এবং "3" হলো b দিয়ে বিভাজ্য। ইনপুট: str = "1200", a = 4, b = 3 আউটপুট: YES 12 00 ইনপুট: str = "125", a = 12, b = 3 আউটপুট: NO
এই সমস্যাতেই, আমরা কিছু প্রিক্যালকুলেশন (precalculation) করব যা প্রোগ্রামটিকে দ্রুত করবে এবং উচ্চ কনস্ট্রেইন্টের জন্যও কাজ করবে।
এই পদ্ধতিতে, আমরা স্ট্রিংয়ের মধ্য দিয়ে দুটি লুপ চালাব: প্রথমটি শুরু থেকে শেষ পর্যন্ত (forward) এবং দ্বিতীয়টি শেষ থেকে শুরু পর্যন্ত (backward)। প্রতিটি পয়েন্টে, প্রথম লুপে গঠিত সংখ্যার A দিয়ে মডুলো (mod) এবং দ্বিতীয় লুপে B দিয়ে মডুলো নিয়ে রাখব। এরপর আমরা বিভাজন পয়েন্ট (division point) খুঁজে বের করব।
#include <bits/stdc++.h> using namespace std; void divisionOfString(string &str, int a, int b){ int n = str.length(); vector<int> mod_a(n+1, 0); mod_a[0] = (str[0] - '0') % a; for (int i = 1; i < n; i++) // ফরওয়ার্ড লুপ: A দিয়ে মডুলো mod_a[i] = ((mod_a[i-1] * 10) % a + (str[i] - '0')) % a; vector<int> mod_b(n+1, 0); mod_b[n-1] = (str[n-1] - '0') % b; int power10 = 10; // লাস্ট ইনডেক্সে মান দেওয়া হয়েছে for (int i = n-2; i >= 0; i--) { // ব্যাকওয়ার্ড লুপ: B দিয়ে মডুলো mod_b[i] = (mod_b[i+1] + (str[i] - '0') * power10) % b; power10 = (power10 * 10) % b; } for (int i = 0; i < n-1; i++) { // বিভাজন পয়েন্ট খোঁজা if (mod_a[i] != 0) continue; // mod_a শূন্য নাও হলে স্কিপ if (mod_b[i+1] == 0) { // পরের ইনডেক্সে mod_b শূন্য হলে সেটিই উত্তর cout << "YES\n"; /*******বিভাজন প্রিন্ট**********/ for (int k = 0; k <= i; k++) cout << str[k]; cout << " "; for (int k = i+1; k < n; k++) cout << str[k]; return; } } cout << "NO\n"; // অন্যথায় NO } int main(){ string str = "123"; int a = 12, b = 3; divisionOfString(str, a, b); return 0; }
YES 12 3
এই পদ্ধতিতে, আমরা প্রতিটি বিভাজন পয়েন্টে গঠিত সংখ্যার রিমেইন্ডার (remainder) বের করেছি। প্রথম সংখ্যাটি A দিয়ে বিভাজ্য হতে হবে, তাই ফরওয়ার্ড লুপ চালিয়ে A দিয়ে মডুলো সংরক্ষণ করেছি। B-এর জন্য ব্যাকওয়ার্ড লুপ চালিয়ে মডুলো সংরক্ষণ করেছি। যেহেতু যেকোনো পজিশনে mod_a শূন্য এবং পরের ইনডেক্সে mod_b শূন্য হলে সেটিই আমাদের विभাজন পয়েন্ট, তাই সেটি প্রিন্ট করেছি।
এই টিউটোরিয়ালে আমরা একটি সংখ্যাকে দুটি বিভাজ্য অংশে ভাগ করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
