Just another WordPress.com site

ধরি, আমাদের কাছে ২ টাকা এবং ৪ টাকার কয়েন আছে আর আমরা জানতে চাই, ঠিক কতভাবে ১ থেকে ৮টাকা বানানো যায়, যেমন ৪ টাকা বানানো যায় ২ ভাবেঃ ২টাকার ২ টা কয়েন বা ৪ টাকার  টা কয়েন দিয়ে।
আর আরেকটা কথা, যে কোন কয়েন যে কোন সংখ্যকবার নেয়া যাবে।

ধরি, একটা এরে নিলাম nway[], এতে থাকবে কোন টাকা কতভাবে বানানো যায়, মানে nway[1]=কতভাবে ১ টাকা বানানো যায়, nway[2] মানে কতভাবে ২ টাকা বানানো যায়…
nway[0] = 1,কারন আমরা ০ টাকা বানাতে পারি ১ ভাবে(কোন টাকা না নিয়ে)
এখন আমার nway array টা দেখতে এ রকমঃ

১   ০   ০   ০   ০   ০   ০   ০   ০
০   ১   ২   ৩   ৪   ৫   ৬   ৭    ৮
এবার আসল কাজ শুরু করা যাক।

প্রথমে ২ টাকার কয়েনটা নিই, ২ টাকার কয়েন দিয়ে অবশ্যই ১ টাকা বানানো যায় না,তাই টেস্ট করা শুরু করি ২ টাকা হতে। এখন ২ টাকার কয়েন দিয়ে কি ২ টাকা বানানো যায়?একটা জিনিস খুব ভালভাবে খেয়াল করতে হবেঃ ধরি,আমার কাছে ২ টাকা আছে, এটা দিয়ে ৫ টাকা বানাতে পারব, যদি আমার কাছে (৫-২) = ৩ টাকা থাকে।তাহলে ৩ টাকার সাথে ২ টাকা যোগ করে ৫ টাকা বানাতে পারব।

তেমনিভাবে, ১টা ২ টাকার কয়েন দিয়ে ২ টাকা বানানো যাবে যদি আমার কাছে (২-২)=০ টাকা থাকে, বা শুন্য টাকা বানাতে পারি। এখন কতভাবে ০ টাকা বানাতে পারি তা আছে nway[0] তে।
এখন, nway[0]=1>০,মানে আমার কাছে ০ টাকা আছে বা আমি ০ টাকা বানাতে পারি, তাই আমি ২ টাকার কয়েন দিয়ে ০+২= ২ টাকা বানাতে পারি। কিন্তু কতভাবে বানাতে পারি? যতভাবে ০ টাকা বানাতে পারি +nway[2 ] এর বর্তমান মান যত। nway[2] এর বর্তমান মান ০, আর ০ টাকা বানাতে পারি ১ ভাবে, তাই ২ টাকা বানাতে পারি ০+১ = ১ ভাবে।
এটা সি তে লিখব এভাবেঃ nway[2] =nway[0]+ nway[2], বা আরো সংক্ষেপে,nway[2]+=nway[0]. এখন, ২ টাকার কয়েন দিয়ে কি ৩ টাকা বানাতে পারি? এজন্য আগে দেখি ৩-২ = ১ টাকা বানানো যায় কিনা।
nway[1]=0.তার মানে আমি ১ টাকা বানাতে পারি না, তাই ১ টাকার হেল্প নিয়ে ৩ টাকাও বানানো সম্ভব না।
একইভাবে nway[4] = nway[4]+nway[4-2] মানে nway[4]+nway[2],nway[5] = nway[5]+nway[3] …
এভাবে ৮ টাকা পর্যন্ত চেক করার পরে আমার nway array টা এরকমঃ

১   ০   ১   ০   ১   ০   ১   ০   ১
০   ১   ২   ৩   ৪   ৫   ৬  ৭    ৮

এবার ৪ টাকার কয়েন নিয়ে কাজ করা যাকঃ
৪ টাকার কয়েন দিয়ে ১,২ বা ৩ টাকা বানানো সনভব না,কারণ এরা সবাই ৪ এর ছোট। ৪ টাকার কয়েন দিয়ে ৪ টাকা বানানো যায়, কিন্তু কতভাবে বানানো যায়? আগের মতই, যতভাবে ৪-৪=০ টাকা বানাতে পারি +nway[4 ] এর বর্তমান মান। nway[4] এর বর্তমান মান 1, আর ০ টাকা বানাতে পারি ১ ভাবে, তাই 4 টাকা বানাতে পারি 1+১ = 2 ভাবে।

এভাবে ৮ টাকা পর্যন্ত চেক করার পরে আমার nway array টা এরকমঃ

১   ০   ১   ০   ২   ০   ২   ০   ৩
০   ১   ২   ৩   ৪   ৫   ৬  ৭    ৮
কোড :
int nways[9];/* ৮ টাকা পর্সন্ত চেক করতে হবে,০ হতে ৮= ৯ টা মান*/

int main(){

int coins[5]={2,4};/*আমার কাছে যে সব কয়েন আছে */

int cent,total;

nways[0]=1;/*০ টাকা বানানোর উপায় ১ টা*/

for(int i=0;i<2;i++){/*সবগুলো কয়েন নিয়ে কাজ   করছি,কয়েন       তাই i<2*/

for(int j=coins[i],k=0;j<=8;j++,k++){/*৮ টাকা পর্যন্ত চেক করব, তাই j<8*/

nways[j]+=nways[k];
}
}

return 0;

}

এবার সলভ করে ফেলুনঃ acm 647,acm 147,acm 357.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: