C++ এ সুপার এগ ড্রপ

ধরুন আমরা K ডিম দিয়েছি, এবং আমাদের কাছে 1 থেকে N তলা বিশিষ্ট একটি বিল্ডিং আছে। এখন প্রতিটি ডিমের কার্যকারিতা একই, এবং যদি একটি ডিম ভেঙ্গে যায়, আমরা তা আবার ফেলে দিতে পারি না।

0 এবং N-এর মধ্যে একটি ফ্লোর F রয়েছে যাতে F-এর চেয়ে উপরে ফ্লোরে ফেলে দেওয়া যে কোনও ডিম ভেঙে যায় এবং F তলায় বা নীচে ফেলে দেওয়া কোনও ডিম ভেঙে যায় না। প্রতিটি পদক্ষেপে, আমরা একটি ডিম নিতে পারি এবং এটিকে যেকোন ফ্লোর X থেকে ফেলে দিতে পারি। X এর রেঞ্জ 1 থেকে N।

আমাদের লক্ষ্য হল নিশ্চিতভাবে জেনে রাখা যে F এর মান কী। সুতরাং, F-এর প্রাথমিক মান নির্বিশেষে, F কী তা আমাদের নিশ্চিতভাবে জানতে হবে সর্বনিম্ন কতগুলি চাল?

সুতরাং, ইনপুট যদি K =2 এবং N =6 এর মত হয়, তাহলে আউটপুট হবে 3।

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

• একটি 2D অ্যারে ডিপি

  সংজ্ঞায়িত করুন

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

  নেবে

• যদি N <=1, তাহলে −

  • ফেরত N

• K যদি 1 এর সমান হয়, তাহলে −

  • ফেরত N

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

  • dp[K, N>

    ফেরত দিন

• ret :=N, low :=0, high :=N

  • যখন কম <=উচ্চ, করুন −

  • বাম :=1 + সমাধান (কে - 1, মধ্য - 1)

  • ডান :=1 + সমাধান (K, N - মধ্য)

  • ret :=সর্বনিম্ন ret এবং সর্বোচ্চ বাম এবং ডান

  • যদি বাম ডানের সমান হয়, তাহলে −

    • লুপ থেকে বেরিয়ে আসুন

  • যদি বামে <ডান, তারপর:

    • নিম্ন :=মধ্য + 1

  • অন্যথায় উচ্চ :=মধ্য - 1

• রিটার্ন dp[K, N] =ret

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

• dp :=একটি 2D অ্যারে তৈরি করুন (K + 1) x (N + 1), এটি -1 দিয়ে পূরণ করুন

• রিটার্ন সলভ(K, N)

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<vector<int>> dp;
   int solve(int K, int N) {
      if (N <= 1)
         return N;
      if (K == 1)
         return N;
      if (dp[K][N] != -1)
         return dp[K][N];
      int ret = N;
      int low = 0;
      int high = N;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         int left = 1 + solve(K - 1, mid - 1);
         int right = 1 + solve(K, N - mid);
         ret = min(ret, max(left, right));
         if (left == right)
         break;
         if (left < right) {
            low = mid + 1;
         } else
            high = mid - 1;
      }
      return dp[K][N] = ret;
   }
   int superEggDrop(int K, int N) {
      dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
      return solve(K, N);
   }
};
main(){
   Solution ob;
   cout << (ob.superEggDrop(2,6));
}

ইনপুট

2, 6

আউটপুট

3