C++ এ মৌখিক পাটিগণিত ধাঁধা

ধরুন আমাদের একটি সমীকরণ আছে, এক্সপ্রেশনগুলি বাম পাশের শব্দ দ্বারা এবং ফলাফলটি ডান পাশের দ্বারা উপস্থাপন করা হয়। আমাদের পরীক্ষা করতে হবে যে সমীকরণটি নিম্নলিখিত নিয়মের অধীনে সমাধানযোগ্য কিনা −

• প্রতিটি অক্ষরকে একটি সংখ্যা (0 থেকে 9) হিসাবে ডিকোড করা হয়।

• বিভিন্ন অক্ষরের প্রতিটি জোড়াকে ভিন্ন অঙ্কের মানচিত্র করতে হবে।

• প্রতিটি শব্দ[i] এবং ফলাফল একটি সংখ্যা হিসাবে ডিকোড করা হয় যেখানে কোন অগ্রণী শূন্য উপস্থিত নেই।

• বাম পাশের সংখ্যার যোগফল ডান পাশের সংখ্যার সমান হবে।

• সমীকরণটি সমাধানযোগ্য কিনা তা আমরা পরীক্ষা করব।

সুতরাং, যদি ইনপুটটি শব্দের মত হয় =["পাঠান","আরো"], ফলাফল ="মানি", তাহলে আউটপুটটি সত্য হবে, যখন আমরা অক্ষরগুলিকে এইভাবে ম্যাপ করি:Map 'S'-> 9, 'E '->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2', তারপর "পাঠান" + "আরো" ="মানি" 9567 + 1085 =10652 এর মতো।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আকারের একটি অ্যারে i2c সংজ্ঞায়িত করুন:10, আকারের একটি অ্যারে c2i:26 এবং আরেকটি অ্যারে w

• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি idx, l, sum,

  নেবে

• যদি l r এর আকারের সমান হয়, তাহলে −

  • যোগফল 0

    এর সমান হলে true ফেরত দিন

• যদি idx w এর আকারের সমান হয়, তাহলে −

  • যদি c2i[r[l] - 'A'] এর ASCII -1 এর সমান না হয়, তাহলে −

    • যদি c2i[r[l] - 'A'] এর ASCII যোগফল 10 এর সমান হয়, তাহলে −

      • রিটার্ন সলভ (0, l + 1, যোগফল / 10)

  • অন্যথায় যখন i2c[sum mod 10] -1 এর মত হয়, তখন −

    • যদি l r এর আকারের সমান হয় এবং যোগফল 10 0 এর সমান হয়, তাহলে −

      • মিথ্যা ফেরত দিন

    • c2i[r[l] - ASCII of 'A'] =যোগফল 10

    • i2c[sum mod 10] =r[l] - 'A' এর ASCII

    • temp :=সমাধান (0, l + 1, যোগফল / 10)

    • c2i[r[l] - ASCII of 'A'] =- 1

    • i2c[sum mod 10] =- 1

    • রিটার্ন টেম্প

  • মিথ্যা ফেরত দিন

• যদি l>=w[idx] এর আকার হয়, তাহলে −

  • রিটার্ন সলভ (idx + 1, l, sum)

• যদি c2i[w[idx, l] - 'A'] -1 এর সমান না হয়, তাহলে −

  • l যদি w[idx] এবং c2i[w[idx, l]-এর আকারের সমান হয় - 'A'] এর ASCII 0 এর সমান, তাহলে −

    • মিথ্যা ফেরত দিন

  • রিটার্ন সলভ (idx + 1, l, sum + c2i[w[idx, l] - ASCII of 'A'])

• আরম্ভ করার জন্য i :=0, যখন i <10, আপডেট করুন (i 1 দ্বারা বাড়ান), −

  • যদি i2c[i] -1 এর সমান না হয়, তাহলে −

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • যদি i 0 এর সমান হয় এবং l w[idx] এর আকারের সমান হয়, তাহলে −

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • i2c[i] :=w[idx, l] - 'A' এর ASCII

  • c2i[w[idx, l] - ASCII of 'A'] =i

  • temp :=সমাধান (idx + 1, l, sum + i)

  • i2c[i] :=-1

  • c2i[w[idx, l] - ASCII of 'A'] =- 1

  • যদি তাপমাত্রা অ-শূন্য হয়, তাহলে −

    • প্রত্যাবর্তন সত্য

• মিথ্যা ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• -1

  দিয়ে i2c এবং c2i পূরণ করুন

• অ্যারের ফলাফল বিপরীত করুন

• আরম্ভ করার জন্য i :=0, যখন i <শব্দের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), do−

  • যদি শব্দের আকার [i]> ফলাফলের আকার, তাহলে −

    • মিথ্যা ফেরত দিন

  • অ্যারে শব্দগুলি বিপরীত করুন[i]

• r :=ফলাফল, w :=শব্দ

• রিটার্ন সমাধান(0, 0, 0)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   char i2c[10];
   int c2i[26];
   vector<string> w;
   string r;
   bool solve(int idx, int l, int sum){
      if (l == r.size()) {
         return sum == 0;
      }
      if (idx == w.size()) {
         if (c2i[r[l] - 'A'] != -1) {
            if (c2i[r[l] - 'A'] == sum % 10) {
               return solve(0, l + 1, sum / 10);
            }
         }
         else if (i2c[sum % 10] == -1) {
            if (l == r.size() - 1 && sum % 10 == 0)
            return false;
            c2i[r[l] - 'A'] = sum % 10;
            i2c[sum % 10] = r[l] - 'A';
            bool temp = solve(0, l + 1, sum / 10);
            c2i[r[l] - 'A'] = -1;
            i2c[sum % 10] = -1;
            return temp;
         }
         return false;
      }
      if (l >= w[idx].size()) {
         return solve(idx + 1, l, sum);
      }
      if (c2i[w[idx][l] - 'A'] != -1) {
         if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
            return false;
         }
         return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
      }
      for (int i = 0; i < 10; i++) {
         if (i2c[i] != -1)
         continue;
         if (i == 0 && l == w[idx].size() - 1)
         continue;
         i2c[i] = w[idx][l] - 'A';
         c2i[w[idx][l] - 'A'] = i;
         bool temp = solve(idx + 1, l, sum + i);
         i2c[i] = -1;
         c2i[w[idx][l] - 'A'] = -1;
         if (temp)
         return true;
      }
      return false;
   }
   bool isSolvable(vector<string>& words, string result){
      memset(i2c, -1, sizeof(i2c));
      memset(c2i, -1, sizeof(c2i));
      reverse(result.begin(), result.end());
      for (int i = 0; i < words.size(); i++) {
         if (words[i].size() > result.size())
         return false;
         reverse(words[i].begin(), words[i].end());
      }
      r = result;
      w = words;
      return solve(0, 0, 0);
   }
};
main(){
   Solution ob;
   vector<string> v = {"SEND","MORE"};
   cout << (ob.isSolvable(v, "MONEY"));
}

ইনপুট

{"SEND","MORE"}, "MONEY"

আউটপুট

1