Codeforces 556A - Case of the Zeros and Ones সমাধান

সমস্যার বর্ণনা:
শুধু 0 আর 1 সংবলিত একটা বাইনারি string দেয়া আছে, যার length দেয়া আছে n ।

এই string এ 0 আর 1 পাশাপাশি রাখা যাবে না । এজন্য যেসব স্থানে একটি 0 আর একটি 1 পাশাপাশি আছে, এমন 0 আর 1 গুলোকে রিমুভ করে দিতে হবে । এভাবে সকল পাশাপাশি থাকে 0 আর 1 কে রিমুভ করে দেবার পরে বাকি ক্যারেকটারগুলি নিয়ে নতুন string তৈরি হবে ।

একই ভাবে নতুন string যদি আবারও কোথাও একটি 0 আর একটি 1 পাশাপাশি থাকে, তবে এই প্রসেস চলতেই থাকবে, অর্থাৎ আবারও যেসব স্থানে একটি 0 আর একটি 1 পাশাপাশি আছে, এমন 0 আর 1 গুলোকে রিমুভ করে দিতে হবে  - যতক্ষণ না string এ কোথাও কোন 0 আর 1 পাশাপাশি না থাকে ।

আউটপুটে দেখাতে হবে এভাবে রিমুভ করার পরে, ফাইনালি string এর মিনিমাম length কত হবে ?

Sample ইনপুট ও আউটপুটঃ

...............

Input

4
1100

Output

0

ব্যাখ্যাঃ
1100 এ ২য় ও ৩য় পজিশনের 0 আর 1 পাশাপাশি আছে । এদেরকে রিমুভ করে দেবার পরে string থাকে ১ম 1 ও শেষ 0. এরা কাছাকাছি চলে এসে নতুন string হয়  10
আবারও 1 আর 0 পাশাপাশি আছে । তাই এদের দুইটাই রিমুভ হয়ে আর কিছুই থাকবে না । তাই আউটপুট 0.


...................

Input

5
01010

Output

1

 ব্যাখ্যাঃ
 01010 তে ২য় পজিশনের 1 ও ৩য় পজিশনের 0 পাশাপাশি এবং ৪র্থ পজিশনের 1 ও ৫ম পজিশনের 0 পাশাপাশি আছে । তাই এই ৪ টা রিমুভ হবার পরে থাকে শুধু ১ম 0. তাই আউটপুট 1, কারণ এই string এর length হলো 1.
...................

Input

8
11101111

Output

6

ব্যাখ্যাঃ
 এখানে ৪র্থ পজিশনের 0 বামেও 1 আছে ও ডানেও 1 আছে । তাই ৪র্থ ও ৫ম অথবা ৩য় ও ৪র্থ পজিশনের দুইটা digit কে রিমুভ করে দিলে আর কোন 0, 1 পাশাপাশি থাকবে না । তাই আউটপুট 6.
..................

সমাধানঃ

একটু চিন্তা করে দেখলেই সহজেই প্রোবলেমটা সলভ করতে পারি । string এ যদি 0 আর 1 দুটোই থাকে তবে, যে কোন একটা 0 আর একটা 1 adjacent  হবেই । কারণ অন্তত একটা 0 কে কোন না কোন 1 এর পাশে থাকবেই ।
যখন তাদের রিমুভ করব আবার যদি 0 আর 1 দুটোই থাকে, তবে আবারো নতুন adjacent তৈরী হবেই ।
যেহেতু প্রতি বার রিমুভ করার সময় একসাথে দুইটা ডিজিট রিমুভ করতে হয়, তাই আমরা দেখব মোট কত জোড়া 0 আর 1 আছে । অত জোড়াই রিমুভ করা যাবে । এজন্য 0 আর 1 এর মাঝে দেখতে হবে কোনটি কম আছে । তত জোড়া তৈরি হবে, বাকি ডিজিট গুলো থেকে যাবে ।

আশা করছি, বুঝতে পেরেছ । তাই আর বেশি ব্যাখ্যা দিলাম না । তবুও বুঝতে সমস্যা হলে কমেন্টে জানাও ।
কোডটা হবে এরকম-

	#include <stdio.h>
	int main()
	{
	int n, zero=0, one=0, i;
	char s[200005];
	scanf("%d",&n);
	scanf("%s", s);
	for(i=0;i<n;i++)
	if(s[i]=='0')
	zero++;
	else one++;
	if(one<zero)
	printf("%d\n", n-2*one);
	else printf("%d\n", n-2*zero);
	return 0;
	}

view raw cf 556a.cpp hosted with ❤ by GitHub