راه‌حل‌های مسابقه الگوریتمی Newbies 2015 – 2016

راه‌حل‌های سؤالات مسابقه الگوریتمی Newbies 2015 – 2016 در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

A – Donuts and the Giant Pizza

همیشه باید مرکز پیتزا (مستطیل) را روی مرکز میز (دایره) قرار دهیم. حال برای اینکه بررسی کنیم آیا پیتزا روی میز جا می‌شود یا نه کافی است بررسی کنیم قطر مستطیل کمتر یا مساوی قطر دایره است یا نه. یعنی:

\sqrt{w^2 + l^2} \leq 2r

برای اینکه نیاز به محاسبه‌ی جذر نداشته باشیم، می‌توانیم طرفین نامساوی را به‌توان دو برسانیم.

w^2 + l^2 \leq 4r^2

و از روی این شرط بررسی کنیم که آیا پیتز روی میز جا می‌شود یا نه.

پیچیدگی زمانی:

\mathcal{O}(T)

#include <iostream>

using namespace std;

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;
	while (tc--) 
	{
		int r, w, h;
		cin >> r >> w >> h;
		if (w * w + h * h <= 4 * r * r)
			cout << "Pizza fits on the table.\n";
		else
			cout << "Pizza does not fit on the table.\n";
	}
    return 0;
}

B – 0x55

می‌توانیم نمایش اعداد در مبنای ۱۰، ۲ و ۱۶ را به صورت رشته در بیاوریم و به‌راحتی بررسی کنیم آیا آینه‌ای (palindrome) هست یا نه.

پیچیدگی زمانی:

\mathcal{O}(T)

#include <bits/stdc++.h>

using namespace std;

bool palindrom(string s) 
{
	return s == string(s.rbegin(), s.rend());
}

bool check(int n) 
{
	stringstream ss, ss1, ss2, ss3;
	ss1 << n;
	ss2 << hex << n;
	ss << bitset<20>(n);
	ss3 << stoi(ss.str());
	return palindrom(ss1.str()) + palindrom(ss2.str()) + palindrom(ss3.str()) >= 2;
}

int main() 
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	
	int tc;
	cin >> tc;
	while (tc--) 
	{
		int n;
		cin >> n;
		cout << (check(n) ? "Magical\n" : "I'm sorry Sherlock :(\n");
	}
    return 0;
}

C – Colonelmo, CaptainH1 and Cluna

می‌توانیم یک آرایه به طول n داشته باشیم و در هر لحظه نگه داریم که چه کسی در هر لحظه در فروشگاه است. سپس بعد از هر خروج، بررسی کنیم چه کسی رمز چه کس دیگری را فهمید. برای ذخیره کردن هم از یک آرایه دوبعدی استفاده می‌کنیم که در شمارش، تکراری حساب نکنیم.

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

پیچیدگی زمانی:

\mathcal{O}(n^2)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000;
string pass[maxn];
bool in[maxn], knows[maxn][maxn];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> pass[i];
		sort(pass[i].begin(), pass[i].end());
	}

	int m;
	cin >> m;

	while (m--)
	{
		int x;
		cin >> x;
		x--;

		in[x] = !in[x];

		if (in[x] == 0)
			for (int i = 0; i < n; i++)
				if (in[i] && pass[i] == pass[x])
					knows[i][x] = true;
	}

	for (int i = 0; i < n; i++)
	{
		int s = 0;
		for (int j = 0; j < n; j++)
			s += knows[i][j];

		cout << s << " \n"[i == n - 1];
	}

	return 0;
}

D – Erfan and Minions

در هر خانه‌ای که قرار داریم می‌توانیم درصورت داشتن موز کافی به هشت خانه‌ی اطراف (به شرط برخورد نکردن با دیوار) برویم.

علاوه بر خانه‌هایی که به‌طور مستقیم همسایه‌ی خانه‌ی فعلی محسوب می‌شوند، خانه‌هایی هستند که می‌توان بدون عبور از همسایه‌ی‌های مستقیم به آن رسید. برای مثال از خانه‌ی ۷ می‌توان به خانه‌های ۲ و ۶ رفت، بدون اینکه از خانه‌ی دیگری عبور کنیم.

برای بدست آوردن تعداد حالات باید بدانیم از هر خانه‌ به چه خانه‌هایی می‌توانیم برویم. مختصات خانه‌هایی که از خانه‌ی فعلی می‌توانیم به آن برویم با یک حلقه بر روی تمامی مقادیر آرایه‌ی dx[k] و dy[k] بدست می‌آید.

متغیرk تعداد حالت‌هایی‌ست که از خانه فعلی امکان رفتن به آن وجود دارد (۱۶ تا با احتساب حالت همسایه مستقیم و غیرمستقیم) البته ممکن است اصلا این مختصات وجود نداشته باشد یا قبلاً به آن رفته باشیم، به همین سبب از تابع avail استفاده می‌کنیم.

i_{new} = i + dx[k]
\\
j_{new} = j + dy[k]

چون حالات تکراری زیادی وجود دارند و محاسبه‌ی همه آن‌ها بطور جداگانه زمان‌گیر است از روش Dynamic Promgramming استفاده می‌کنیم. یک آرایه‌ی دو بعدی dp درنظر می‌گیریم که بعد اول آن خانه‌ی فعلی و بعد دوم آن حالتی است که تا به حال به آن رسیده‌ایم را بیان می‌کند.

اگر بعد دوم حالتی باشد که موزها به اتمام برسد، یکی به جواب نهایی اضافه خواهیم کرد.

نکته پیاده‌سازی: برای ذخیره هر حالت در بعد دوم آرایه‌ی dp از روش bit masking استفاده می‌کنیم.

پیچیدگی زمانی:

\mathcal{O}(T \times (2^N))

#include <bits/stdc++.h>

using namespace std;

int n, s;

int avail(int mask, int i, int j) 
{
	if (i < 0 || j < 0 || i >= 3 || j >= 3) 
		return 0;
	int ind = i * 3 + j;
	return ~mask & (1 << ind);
}

int dx[16] = {-1, 0, 0, +1, -1, -1, +1, +1, -1, -1, +1, +1, -2, -2, +2, +2};
int dy[16] = {0, -1, +1, 0, -1, +1, -1, +1, +2, -2, +2, -2, +1, -1, +1, -1};

int dp[MAX][1 << MAX];

int DP(int ind, int mask) 
{
	if (__builtin_popcount(mask) == n) 
		return 1;
	
	int &ret = dp[ind][mask];

	if (ret != -1) 
		return ret;
	
	ret = 0;
	
	int i = ind / 3;
	int j = ind % 3;
	
	for (int k = 0; k < 16; k++) 
	{
		if (avail(mask, i + dx[k], j + dy[k])) 
		{
			int newInd = (i + dx[k]) * 3 + j + dy[k];
			ret += DP(newInd, mask | (1 << newInd));
		}
		else if (avail(mask, i + 2 * dx[k], j + 2 * dy[k])) 
		{
			int newInd = (i + 2 * dx[k]) * 3 + j + 2 * dy[k];
			ret += DP(newInd, mask | (1 << newInd));
		}
	}
	return ret;
}

void initialize() 
{
	memset(dp, -1, sizeof dp);
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int tc = 0;
	cin >> tc;
	for (int TC = 1; TC <= tc; TC++) 
	{
		cin >> s >> n;
		initialize();
		s--;
		int ans = DP(s, 1 << s);
		cout << "Case#" << TC << " : " << ans << endl;
	}
    return 0;
}

E – Flower Lovers

ظرفیت‌های هر گروهی زودتر پر شود، بازنده است. به این ترتیب استراتژی برد هر گروه این است که با افرادی که کمترین ظرفیت را در گروه دیگر دارند شروع کند تا هر چه زودتر یک فرد در گروه مقابل را حذف کند.

برای حل، ظرفیت‌ها را از کوچک به بزرگ در هر گروه مرتب می‌کنیم. به نوبت، پرتاب گل را برای هر گروه اعمال می‌کنیم، هر گروهی که زودتر ظرفیت افرادش به اتمام برسد بازنده خواهد بود.

دقت کنید درمورد اینکه چه گروهی بازی را اول شروع می‌کند شرطی گذاشته نشده، لذا زمانی که نتیجه‌ی بازی بر حسب اینکه کدام گروه اول بازی را شروع کند متغیر باشد، بیانگر این است که هیچکس نخواهد برد.

پیچیدگی زمانی:

\mathcal{O}(T \times N \times M)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000 + 10

int a[maxn], b[maxn];

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--) 
	{
		int N, M;
		cin >> N >> M;
		for (int i = 0; i < N; i++) 
			cin >> a[i];

		for (int i = 0; i < M; i++) 
			cin >> b[i];

		sort(a, a + N);
		sort(b, b + M);

		int i1 = 0, i2 = 0;
		while (i1 < N && i2 < M) 
		{
			int cost1 = M - i2;
			int cost2 = N - i1;
			
			while (i1 < N && cost1) 
			{
				a[i1]--;
				cost1--;
				if (a[i1] == 0) 
					i1++;
			}
			while (i2 < M && cost2) 
			{
				b[i2]--;
				cost2--;
				if (b[i2] == 0) 
					i2++;
			}
		}

		bool a_win = (i2 == M);
		bool b_win = (i1 == N);

		if (a_win ^ b_win) 
		{
			if (a_win) 
				cout << "A\n";
			else 
				cout << "B\n";
		} 
		else 
			cout << "we will all sing songs together\n";
	}
	return 0;
}

F – Be Like Bob not Raha

یک آرایه‌ی دوبعدی (mat) که بیانگر دوستی بین افراد است را درنظر می‌گیریم.

برای مثال mat[i][j] اگر یک باشد بدین معناست که i و j با یکدیگر دوست هستند، ضمناً از آنجایی که دوستی دوطرفه است mat[j][i] نیز یک است.

برای محاسبه تعداد دوستان باب کافیست تمامی کسانی که با دوستان باب دوست هستند را برسی کنیم. اگر مستقیماً با باب دوست نیستند یکی به پاسخ نهایی اضافه خواهیم کرد.

پیچیدگی زمانی:

\mathcal{O}(T \times (M + N^ 2))

#include <bits/stdc++.h>

using namespace std;

const int maxn = 410;
char mat[maxn][maxn];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int tc;
	cin >> tc;
	while (tc--) 
	{
		int n, m;
		cin >> n >> m;

		memset(mat, 0, sizeof mat);
		
		while (m--) 
		{
			int u, v;
			cin >> u >> v;
			mat[u][v] = mat[v][u] = 1;
		}

		int ans = 0;
		for (int j = 2; j <= n; j++)
			for (int i = 2; i <= n; i++)
				if (mat[1][i] && mat[i][j] && !mat[1][j]) 
				{
					ans++;
					break;
				}

		cout << ans << '\n';
	}
    return 0;
}

G – Middle Out

برای هر تست، کافیست فاصله‌ی هر N تا D2F را با M تا آژانسی که به آن مرتبط است محاسبه کرده و مقدار ماکسیمم آن را برگردانیم.

جواب نهایی ماکسیمم این مقدار برای هریک آژانس‌های D2F است.

پیچیدگی زمانی:

\mathcal{O}(T \times ( N \times M))

#include <iostream>

using namespace std;

const int maxn = 120;
int d2f[maxn];

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int tc;
	cin >> tc;
	while (tc--) 
	{
		int n;
		cin >> n;
		
		for (int i = 1; i <= n; i++)
			cin >> d2f[i];
		
		int ans = 0;
		for (int i = 1; i <= n; i++) 
		{
			int m;
			cin >> m;
			while (m--) 
			{
				int v;
				cin >> v;
				ans = max(ans, abs(d2f[i] - d2f[v]));
			}
		}
		cout << ans << '\n';
	}
    return 0;
}

H – Trap of Ultron

برای هر ورودی باید در تمامی زمان‌های ممکن، مکان N تا avengers را محاسبه کنیم. همچنین مربعی که در آن زمان مشخص تمامی آن‌ها را در برمی‌گیرید، بدست آوریم. محاسبه‌ی اندازه این مربع توسط تابع calc، با ورودی زمان موردنظر، محاسبه شده است. در نهایت باید بین تمامی زمان‌ها مینیمم مقدار این مربع را به‌عنوان خروجی چاپ کنیم.

از آن‌جایی که زمان تا 10^9 ثانیه محاسبه می‌شود و تعداد N نیز می‌تواند زیاد باشد، امکان اینکه در تک تک ثانیه‌ها حالت N تا avengers را محاسبه کنیم، نداریم.

لذا برای بدست آوردن زمان و محدود کردن بازه‌ی زمانی از Ternary Search استفاده می‌کنیم. درمورد این نحوه سرچ، می‌توانید در این لینک مطالعه بفرمایید.

پیچیدگی زمانی:

\mathcal{O}(T \times N)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef complex<double> pt;

#define L(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define mp make_pair

#define Trace(X) cerr << #X << " = " << X << endl
#define _ << " - " << 

#define MAX (100010)
#define INF 1e10
#define EPS 1e-9

#define X real()
#define Y imag()

pt o[MAX];
pt v[MAX];

int n;

double calc(double time) {
	double maxX, maxY, minX, minY;
	maxX = maxY = -INF;
	minX = minY = INF;
	for (int i = 0; i < n; i++) {
		pt newPt = o[i] + time * v[i];
		maxX = max(maxX, newPt.X);
		maxY = max(maxY, newPt.Y);
		minX = min(minX, newPt.X);
		minY = min(minY, newPt.Y);
	}
	return max(maxX - minX, maxY - minY);
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tc = 0;
	cin >> tc;
	while (tc-- && cin >> n) {
		for (int i = 0; i < n; i++) {
			double x, y, vx, vy;
			cin >> x >> y >> vx >> vy;
			o[i] = pt( x,  y);
			v[i] = pt(vx, vy);
		}

		double l = EPS, h = INF;
		for (int rep = 0; rep < 300; rep++) {
			double m1 = (2 * l + h) / 3;
			double m2 = (2 * h + l) / 3;
			if (calc(m1) < calc(m2)) {
				h = m2;
			}
			else {
				l = m1;
			}
		}
		cout << setprecision(2) << fixed << calc(l) << endl;
	}
    return 0;
}

I – Shamir’s Birthday Party

برای حل این سوال از مبحث رنگ‌آمیزی گراف استفاده می‌کنیم. تمامی افراد را به‌عنوان گره‌های گراف و ارتباط بین آن‌ها را یال گراف درنظر می‌گیریم. با رنگ‌آمیزی گراف، گراف‌های چندبخشی خواهیم داشت که هرکدام رنگ مجزایی دارند و هرکدام از این بخش‌ها با بخش‌های دیگر ارتباطی ندارد. هرکدام از این بخش‌ها تعداد گره‌ی کمتری داشته باشند، مطلوب ما هستند و می‌توانیم به‌عنوان پاسخ آن را خروجی دهیم.

در راه‌حل، تابع dfs2 برای رنگ‌آمیزی گراف استفاده می‌شود.

پیچیدگی زمانی:

\mathcal{O}(T \times (N+M))

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5;
vector <int> adj1[maxn], adj2[maxn], top, ver;
bool mark[maxn];
int col[maxn], cmp;

void dfs1(int v)
{
	mark[v] = true;
	for (int u : adj1[v])
		if (!mark[u])
			dfs1(u);
	top.push_back(v);
}

void dfs2(int v)
{
	ver.push_back(v);
	col[v] = cmp;
	for (int u : adj2[v])
		if (!col[u])
			dfs2(u);
}

void solve()
{
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) 
	{
		adj1[i].clear();
		adj2[i].clear();
	}

	for (int i = 0; i < m; i++) 
	{
		int u, v;
		cin >> u >> v;
		u--, v--;

		adj1[v].push_back(u);
		adj2[u].push_back(v);
	}

	for (int i = 0; i < n; i++)
		mark[i] = false;

	for (int i = 0; i < n; i++)
		if (!mark[i])
			dfs1(i);

	reverse(top.begin(), top.end());

	cmp = 0;
	for (int i = 0; i < n; i++)
		col[i] = 0;

	int ans = n;
	for (int v : top)
		if (!col[v])
		{
			cmp++;
			ver.clear();
			dfs2(v);
 
			bool hasout = false;
			for (int u : ver)
				for (int w : adj2[u])
					if (col[w] != col[u])
						hasout = true;

			if (!hasout)
				ans = min(ans, (int)ver.size());
		}

	cout << ans << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--)
		solve();

	return 0;
}