Light OJ - 1233 - Coin Change (III) Tutorial

Problem Description here

Solution:

এই প্রব্লেমের সলুশ্যন নিয়ে বিস্তারিত আলোচনা করা হবে না😛

এই প্রব্লেমটি মূলত Knapsack-2 এবং Knapsack-3 এর সমন্বিত আইডিয়া দিয়ে সলভ করা সম্ভব! 

আর Knapsack-3 বুঝতে হলে Bitset বুঝতে হবে। 

উপরোক্ত পর্বগুলো দেখার পরও সলভ করা সম্ভব না হলে সলুশ্যন দেখতে পারো। 

	#include<bits/stdc++.h>
	#define Input freopen("in.txt","r",stdin)
	#define Output freopen("out.txt","w",stdout)
	#define ll long long int
	#define sc scanf
	#define scin(x) sc("%d",&(x))
	#define scin2(x,y) sc("%d %d",&(x),&(y))
	#define scln(x) sc("%lld",&(x))
	#define scln2(x,y) sc("%lld %lld",&(x),&(y))
	#define pf printf
	#define ms(a,b) memset(a,b,sizeof(a))
	#define pb(a) push_back(a)
	#define vi vector<int>
	#define vl vector<ll>
	#define vii vector<vector<int> >
	#define vll vector<vector<ll> >
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	int value[105],cnt[105];
	void Solve(int t)
	{
	const int sz = 100005;
	vi coin;
	bitset<sz>bset;
	int i,j,k,n,ans=0,m;
	scin2(n , m);
	for(i=1 ; i<=n ; i++) scin(value[i]);
	for(i=1 ; i<=n ; i++) scin(cnt[i]);
	///Make set of new valued coin(where every coin exist exact once) so that these can make all subset of previous coin set
	for(i=1 ; i<=n ; i++){
	int x = cnt[i] , now = 1 , spend = 0;
	while(spend+now <= x){
	coin.pb(value[i] * now);
	spend += now;
	now *= 2;
	}
	if(x-spend > 0)
	coin.pb(value[i] * (x-spend));
	}
	///
	bset[0] = 1;
	for(i=0 ; i<(int)coin.size() ; i++)
	bset |= (bset << coin[i]);
	for(i=1 ; i<=m ; i++){
	if(bset[i])
	ans++;
	}
	pf("Case %d: %d\n",t,ans);
	}
	int main()
	{
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw LOJ - 1233.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং😊