মান লিজিয়ে, N নামক একটি সংখ্যা দেওয়া আছে। একজন কেক বিক্রেতা ৪০ টাকায় কেক এবং ৭০ টাকায় ডোনাট বিক্রি করছে। আমাদের যাচাই করতে হবে যে আমরা কি কিছু কেক ও ডোনাট ঠিক N টাকা দিয়ে কিনতে পারি বা না।
যেমন, ইনপুট হলে N = 110, তবে আউটপুট হবে True, কারণ ৪০ + ৭০ = ১১০।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
o := false dfs() ফাংশন সংজ্ঞায়িত করুন, যা i গ্রহণ করবে: if i > n, তবে: return false if i == n, তবে: return true if dfs(i + 40), তবে: return true return dfs(i + 70) মূল ফাংশন থেকে: n := N o := dfs(0) return o
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int n; bool o = false; bool dfs(int i) { if (i > n) return false; if (i == n) return true; if (dfs(i + 40)) return true; return dfs(i + 70); } bool solve(int N) { n = N; o = dfs(0); return o; } int main(){ int N = 110; cout << solve(N) << endl; } ইনপুট
110
আউটপুট
1
