Light OJ - 1393 - Crazy Calendar Tutorial

Problem Description here

প্রবলেমঃ প্রব্লেমটিতে মূলত বলা হয়েছে একটি r * c গ্রীড দেয়া থাকবে। গ্রীডের প্রতিটি সেলে কিছু কয়েন থাকবে। দুইজন প্লেয়ার অপটিমালি খেলবে। প্রতি টার্নে একজন প্লেয়ার এক বা একাধিক কয়েন নিবে একটি সেল থেকে। নিয়ে ঠিক তার নিচের অথবা ডানের সেলে রাখবে। যখন সবগুলো কয়েন grid[r][c] তে পৌছাবে তখন খেলা শেষ। শেষ মুভ যে প্লেয়ার দিবে সে জিতবে। বলতে হবে প্রথম প্লেয়ার জিতেছে নাকি হেরেছে। 

আইডিয়াঃ এটি মূলত একটি নিম গেইম। এখন, আমরা প্রব্লেমটিকে নিম্বল গেইমে রূপান্তর এর চেষ্টা করবো। নিম্বল গেইম সম্পর্কে না জানলে ক্লিক করুন।

নিম্বল গেইমে একটি 1*n গ্রীডের প্রতিটি সেলে কিছু কয়েন থাকে। সেল গুলোর ইনডেক্স যদি 0 to n-1 হয় তবে প্রতি চালে যেকোন ঘর থেকে একটি কয়েন নিয়ে বামের যেকোন ঘরে রাখা যায় যতোক্ষণ না সবগুলো কয়েন সর্ববামের ঘরে চলে যায়। 

এই প্রব্লেমে আমি  (i,j) সেল থেকে ডেস্টিনেশন সেল (r,c) তে যেতে পারি (r-i)+(c-j) সংখ্যক মুভ দিয়ে। খেয়াল করলে বুঝবে যে এই প্রব্লেমে আমি কয়েন এক বা একাধিক নিতে পারি আর মুভ এক ঘর ই দিতে পারি এক টার্নে। নিম্বল গেইমের ঠিক উল্টো! ওখানে ছিলো কয়েন একটি আর মুভ এক বা একাধিক ঘর। 

এখন, নিম্বল গেইমে কনভার্ট করলে অর্থাৎ 1D গ্রীডে কনভার্ট করলে কেমন হবে? grid[i][j] হবে 1D grid এর ইনডেক্স। আর ওই ইনডেক্স এর ভ্যালু হিসেবে যোগ হবে (r-i)+(c-j)। মানে, কয়েনগুলোকে ইনডেক্স বানিয়ে ফেলেছি আর দরকারী মুভ সংখ্যা কে কয়েন -_-

বাকি অংশ আশাকরি চিন্তা করে ইমপ্লিমেন্ট করতে পারবে। না পারলে কোড দেখতে পারো।

	#include<bits/stdc++.h>
	#define Input freopen("in.txt","r",stdin)
	#define Output freopen("out.txt","w",stdout)
	#define ll long long int
	#define ull unsigned long long int
	#define pii pair<int,int>
	#define pll pair<ll,ll>
	#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 RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	void Solve(int t)
	{
	map<ll , ll>m;
	map<ll , ll>:: iterator it;
	ll i,j,k,row,col,XOR=0;
	scln2(row , col);
	ll mat[row+5][col+5];
	for(i=1 ; i<=row ; i++){
	for(j=1 ; j<=col ; j++){
	scln(mat[i][j]);
	ll id = (row-i)+(col-j);
	m[mat[i][j]] += id;
	}
	}
	for(it=m.begin() ; it!=m.end() ; it++){
	ll coin = it->first;
	ll id = it->second;
	if(id%2)
	XOR ^= coin;
	}
	if(XOR > 0)
	pf("Case %d: win\n",t);
	else
	pf("Case %d: lose\n",t);
	}
	int main()
	{
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

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