آنالیز مسابقه ۱۰۶ سایت Codeforces

امروز تو این کانتست شرکت کردم. از عملکرد خودم توش نسبتا راضی بودم. سه تا سوال اول رو با سرعت نسبتا خوبی زدم. سوال چهارم رو یک کم اول ترسیدم ازش رفتم سوال پنجم رو هم خوندم. یکم این قضیه باعث شد که وقت هدر بره. این اتفاق که سره انتخاب سوال گیج می‌شم برام کمابیش می‌افته که باید سعی کنم کمتر پیش بیاد. سوال چهار ایده جدیدی نداشت و تقریبا حل کردنش طول نکشید. و کدش رو هم با سرعت خوبی زدم. سوال پنج stringای بود. باز هم مثل همیشه بلد نبودن KMP کار دستم داد. البته تونستم به راه دیگه پیدا کنم که به زور تایم نشه. فعلا که WA شده. خود راه حلم باید درست باشه. هروقت باگش رو پیدا کردم آنالیز اون رو هم می‌نویسم. به قول حامد (صالح) خاک تو سرم! اگه سوال پنج رو گرفته بودم سوم می‌شدم. حالا مهم نیست. یه انگیزه دیگه ایجاد شد که من برم KMP یاد بگیرم. که می‌دونم آخرش یاد نمی‌گیرم!!

برای دسترسی به سوال ها و ارسال پاسخ به آدرس مقابل بروید: http://www.codeforces.com/contest/149

سوال یکم ـ ‌Business Trip

به شما عدد صحیح و نامنفی k و دنباله‌ای شامل ۱۲ عدد داده می‌شود. شما باید بگویید حداقل چند تا از اعداد دنباله را باید انتخاب کرد تا مجموع اعداد انتخاب شده از k کمتر نباشد و در صورتی که این کار غیر ممکن است این را اعلام کنید.

راه حل

می‌توانید اعداد را از بزرگ به کوچک مرتب کنید و از بزرگترین اعداد تا جایی که مجموع بزرگتر مساوی k شود بردارید. اگر همه اعداد را برداشتید و مجموع اعداد از k‌ کمتر بود این کار غیر ممکن است.

کد

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int a[12], k;

	cin >> k;
	for (int i = 0; i < 12; i++)
		cin >> a[i];

	sort(a, a+12, greater<int> ());

	int sum = 0, pos = 0;
	while (pos < 12 && sum < k) {
		sum += a[pos];
		pos++;
	}

	if (sum < k)
		cout << -1 << endl;
	else
		cout << pos << endl;

	return 0;
}

سوال دوم ـ Martian Clock

نمایشی از ساعت دیجیتال به فرم Hour:Minute به شما داده می‌شود. اعداد ساعت و دقیقه لزوما در مبنای ده‌دهی نوشته نشده اند. شما باید مشخص کنید ساعت داده شده در چه مبناهایی معتبر است. می‌دانیم که ساعات روز از ۰ تا ۲۳ اند و دقایق هر ساعت از ۰ تا ۵۹. اگر ساعت داده شده در تعداد بی‌شماری از مبناها معتبر است این را اعلام کنید.

راه حل

اگر یک ساعت در تعداد بی‌شماری از مبناها معتبر باشد به این معنا است که هرچه مبنای ساعت از حد خاصی بزرگتر شود عدد نوشته شده ارزشش بیشتر نمی‌شود. پس می‌توان نتیجه گرفت عدد ورودی یک رقمی است. اگر عددی بیش از یک رقم داشته باشد حتما در مبنای ۱۰۰ مقدارش از ۵۹ و ۲۳ بزرگتر خواهد شد. پس کافیست به ازای هر مبنا بین ۲ تا ۱۰۰ چک کنیم آیا ساعت داده شده در آن مبنا معتبر است یا خیر. طبق نتایج گرفته شده اگر ساعتی در مبنای ۱۰۰ معتبر باشد در تمام مبناهای بالاتر معتبر است.

برای این که بفهمیم یک ساعت در مبنای b معتبر است یا نه کافیست چک کنیم ارقامش بین ۰ تا b-۱ باشند و مقدار ساعتی که در آن مبنا نشان می‌دهد بین ۰ تا ۲۳ باشد. همچنین مقدار دقیقه بین ۰ تا ۵۹ باشد.

کد

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

const long long INF = 1e9;

// Converts a digit character to its value
int c2i(char c) {
	if (c <= '9')
		return c-'0';
	return c-'A'+10;
}

// Converts a number from base "base" to its value
// If "num" is not a valid base "base" number returns infinity
long long conv(string num, int base) {
	long long res = 0;
	for (int i = 0; i < (int)num.length(); i++) {
		if (c2i(num[i]) >= base) return INF;
		res = res*base + c2i(num[i]);
	}
	return res;
}

int main() {
	string inp, h, m;
	cin >> inp;
	for (int i = 0; i < (int)inp.length(); i++)
		if (inp[i] == ':')
			inp[i] = ' ';
	istringstream sin(inp);
	sin >> h >> m;

	vector<int> res;
	for (int base = 2; base <= 100; base++)
		if (conv(h, base) < 24 && conv(m, base) < 60)
			res.push_back(base);

	if (res.empty())
		cout << 0 << endl;
	else if (res.back() == 100)
		cout << -1 << endl;
	else {
		for (int i = 0; i < (int)res.size(); i++)
			cout << res[i] << " ";
		cout << endl;
	}
	return 0;
}

سوال سوم ـ Division into Teams

n نفر می‌خواهند با هم فوتبال بازی کنند. مهارت هر فرد را با عددی طبیعی نمایش می‌دهیم. هرچه این عدد بزرگتر باشد مهارت فرد در بازی فوتبال بیشتر است. می‌خواهیم این افراد را به دو تیم افراز کنیم به طوری که:

• تفاوت اندازه تیم‌ها دست بالا یک نفر باشد.
• هرکس در دقیقا یک تیم آمده باشد.
• مهارت هر تیم برابر با مجموع مهارت اعضایش است. می‌خواهیم تفاضل مهارت این دو تیم از مهارت ماهر ترین بازیکن بیشتر نشود.

تضمین شده است که چنین افرازی برای افراد همواره وجود دارد. همچنین می‌دانیم تعداد افراد از ۱۰۰،۰۰۰ بیشتر نیست.

راه حل

یک روش تقسیم این‌گونه است که ابتدا افراد را بر حسب مهارتشان مرتب کنیم (مثلا از کوچک به بزرگ). سپس یکی درمیان در تیم‌ها بگذاریمشان. یعنی افرادی که در جایگاه فرد قرار دارند در یک تیم و افرادی که در جایگاه زوج قرار دارند در تیم دیگر.

ادعا می‌کنیم این تقسیم بندی شرایط مساله را ارضا می‌کند. واضح است که دو شرط اول تقسیم بندی رعایت شده است. حال ثابت می‌کنیم که شرط سوم نیز برقرار است.

فرض کنید افراد را بر حسب مهارت به صورت دنباله a_۱, a_۲, ..., a_n مرتب کرده ایم و فرد a_n قویترین فرد ممکن است. با فرض این که n فرد است می‌خواهیم ثابت کنیم:

(a_۱+a_۳+...+a_n)-(a_۲+a_۳+...+a_n-۱) ≤ a_n

از آنجا که می‌دانیم:

(a_۱-a_۲)+(a_۳-a_۴)+...+(a_n-۲-a_n-۱) ≤ ۰

می‌توانیم به دو طرف نامساوی a_n را اضافه کنیم تا به عبارت اول برسیم.

حال اگر n‌ زوج باشد می‌توانیم a_n را حذف کنیم و تیم ها را افراز کنیم. سپس a_n را اضافه کنیم و با توجه به این که a_n-۱ ≤ a_n نابرابری را ثابت کنیم.

کد

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
	vector<pair<int, int> > V;
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		V.push_back(make_pair(p, i+1));
	}

	sort(V.begin(), V.end());

	cout << (n+1)/2 << endl;
	for (int i = 0; i < n; i += 2)
		cout << V[i].second << " ";
	cout << endl;

	cout << n/2 << endl;
	for (int i = 1; i < n; i += 2)
		cout << V[i].second << " ";
	cout << endl;

	return 0;
}

سوال چهارم ـ Coloring Brackets

یک عبارت معتبر از پرانتزها عبارتی است که بتوان با اضافه کردن رقم ۱ و عمل + به آن یک عبارت ریاضی به دست آورد. هر پرانتز در چنین عبارتی جفت خودش را دارد. می‌خواهیم تعدادی از پرانتزها را رنگ کنیم به طوری که

• هر پرانتز با رنگ نشده باشد یا قرمز یا آبی باشد.
• هیچ دو کاراکتر مجاوری در رشته در صورتی که هر دو شان رنگ شده‌اند همرنگ نباشند.
• از بین هر پرانتز و جفتش دقیقا یکی رنگ شده باشد.

یک عبارت معتبر از پرانتزها به شما داده می‌شود. تعداد روش‌های رنگ آمیزی آن را حساب کنید. چون ممکن است جواب بسیار بزرگ شود باقی‌مانده آن را بر ۱۰۰۰۰۰۰۰۰۷ چاپ کنید.

راه حل

تابع داینامیک f(a, b, ca, cb) را در نظر بگیرید. مقدار f برابر با تعداد راه‌هایی است که رشته از کاراکتر a تا b را طوری رنگ کنیم که رنگ کاراکتر a برابر با ca و رنگ کارکتر b برابر با cb باشد. در کل سه نوع رنگ داریم. رنگ ۰ به معنای بی‌رنگ است، رنگ ۱ قرمز و ۲ آبی. در تابع f فرض می‌کنیم b‌ جفت a است. برای حساب کردن مقدار f تمام جفت پرانتز هایی را که بلافاصله در عمق ۱ از ab آمده اند را در نظر می‌گیریم. یعنی جفت های مشکی در زیر:

a-> ((...)(...)...(...)) <- b

حال که رنگ a و b‌ را می‌دانیم تعداد رنگ آمیزی‌های پرانتزهای داخل ab را می‌توان با مقادیر تابع f برای جفت پرانتزهای مشکی شده توسط یک داینامیک نسبتا ساده حساب کرد.

کد

در کدی که در ادامه آمده است برای هر جفت ab یک ماتریس ۳×۳ تولید کرده ام به طوری که درایه سطر ca و ستون cb آن برابر با f(a, b, ca, cb) است. تابع merge نیز دو ماتریس را می‌گیرد و تعداد راه های کنار هم گذاشتن آن‌ها را حساب می‌کند. اگر طول رشته ورودی n باشد. پیچیدگی زمانی کد برابر با O(n) است.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define mat vector<vector<ll> >
typedef long long ll;

mat empty = mat (3, vector<ll> (3, 0ll));
mat one = mat (3, vector<ll> (3, 0ll));

const ll MOD = 1000000007;
string s;
int head;

mat merge(mat a, mat b) {
	mat c = empty;

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 3; k++)
				for (int l = 0; l < 3; l++)
					 if (j == 0 || k == 0 || (j != k))
						 c[i][l] += a[i][j] * b[k][l], c[i][l] %= MOD;
	return c;
}

mat process() {
	head++;
	if (s[head] == ')') {
		head++;
		return one;
	}

	vector<mat> V;

	while(s[head] != ')')
		V.push_back(process());
	head++;

	for (int i = 1; i < (int)V.size(); i++)
		V[0] = merge(V[0], V[i]);

	mat res = empty;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if ((i == 0 || j == 0) && (i != 0 || j != 0))
				for (int k = 0; k < 3; k++)
					for (int l = 0; l < 3; l++) {
						if (i && k == i) continue;
						if (j && l == j) continue;
						res[i][j] += V[0][k][l];
						res[i][j] %= MOD;
					}

	return res;
}

int main() {
	for (int i = 1; i <= 2; i++) one[i][0] = one[0][i] = 1;
	cin >> s;

	vector<mat> V;

	while (head < (int)s.length())
		V.push_back(process());

	for (int i = 1; i < (int)V.size(); i++)
		V[0] = merge(V[0], V[i]);

	mat res = V[0];
	ll tot = 0;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			tot += res[i][j];
	tot %= MOD;

	cout << tot << endl;

	return 0;
}

سوال پنجم ـ‌ Martian Strings

رشته s₁s₂...s_n را به شما داده اند. رشته s_a...b+s_c...d را به ازای هر چهار عدد ۱ ≤ a ≤ b < c ≤ d ≤ n را «خوب» می‌نامیم. به شما m رشته داده می‌شود طول هرکدام از این رشته ها از ۱۰۰۰ بیشتر نیست. همچنین m از ۱۰۰ و n از ۱۰۰،۰۰۰ بیشتر نیست. شما باید بگویید چند تا از این m رشته خوب هستند.

راه حل

<در اینجا قرار می‌گیرد>

کد

<در اینجا قرار می‌گیرد>