راه‌حل‌های مسابقه الگوریتمی Newbies 2019

سلام!

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

همون طور که می‌دونید تصمیم گرفتیم مسابقات سال‌های گذشته Newbies رو به‌صورت آنلاین در کوئرا برگزار کنیم تا فرصتی برای تمرین و رقابت باشه. این هفته مسابقه‌ی الگوریتمی Newbies 2019 در کوئرا برگزار شد. این مسابقه در سال ۲۰۱۹ در دانشگاه شهید بهشتی با تلاش «محمدرضا محسنی»، «عرفان علی‌محمدی»، «مهدی آهنگران»، «بردیا ابهری» و «علی میرجهانی» طراحی و برگزار شده بود.

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

A – Cosmic Twins

اگر P بیشتر از D باشد، همواره دو نفر وجود دارند که روزهای تولدشان در یک روز باشد. بنابراین در این حالت، پاسخ مسئله برابر 1 است.

اگر P کمتر مساوی D باشد، احتمال اینکه دو نفر وجود داشته باشند که روز تولدشان یکی باشد را از طریق اصل متمم حساب می‌کنیم.

اگر سال D روز داشته باشد، احتمال اینکه هیچ دونفری تولدشان در یک روز نباشند. برابر است با:

 \frac{D \times (D-1) \times  .  .  .  \times (D-P+1)}{ D^{P} } 

بنابراین اگر سال D روز داشته باشد، احتمال اینکه دو نفر وجود داشته باشند که تولدشان در یک روز باشد برابر است با:

1- \frac{D \times (D-1) \times  .  .  .  \times (D-P+1)}{ D^{P} } 

پیچیدگی زمانی: O(P)

#include <bits/stdc++.h>

using namespace std;

typedef long double LD;
typedef long long int LL;
typedef pair <int,int> pii;

#define L first
#define R second

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	LD p, d;
	cin >> p >> d;
	if (d < p) {
		cout << "1.000000\n";
		return 0;
	}
	LD ans = 1; 
	for (int i = 0; i < p; i++)
		ans = (ans * (d - i)) / d;
	cout.precision(6);
	cout << fixed << 1 - ans << endl;

	return 0;
}

B – Yet Another Paper

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

پیچیدگی زمانی: O(N^2)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000;
int a[maxn];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		int min_idx = i;
		for (int j = i + 1; j < n; j++)
			if (a[min_idx] > a[j])
				min_idx = j;

		ans += min_idx - i;

		for (int j = min_idx - 1; j >= i; j--)
			swap(a[j], a[j + 1]);
	}

	cout << ans << '\n';

	return 0;
}

C – Jack-Jack and Matrices

برای هر خانه از ماتریس همه‌ی حالت‌هایی که از حداکثر 8 همسایه، 3 همسایه را انتخاب کنیم، در نظر بگیریم و سپس بررسی کنیم آیا جمع آن‌ها توانی از 2 است یا خیر.

پیچیدگی زمانی: O(MN)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000;
int a[maxn][maxn];

bool is_two_power(int n)
{
	int m = n, k = 1;
	while (m > 1)
	{
		m /= 2;
		k *= 2;
	}

	return (k == n);
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> a[i][j];

	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			vector <int> v;
			for (int x = max(0, i - 1); x <= min(i + 1, n - 1); x++)
				for (int y = max(0, j - 1); y <= min(j + 1, m - 1); y++)
					if (x != i || y != j)
						v.push_back(a[x][y]);

			bool okay = false;
			for (int r = 0; r < (int)v.size(); r++)
				for (int s = r + 1; s < (int)v.size(); s++)
					for (int t = s + 1; t < (int)v.size(); t++)
						if (is_two_power(v[r] + v[s] + v[t]))
							okay = true;
			
			if (okay)
				ans++;
		}

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

D – Champions League

کافی است جدول امتیازات را محاسبه و دو تیم برتر را طبق توضیحات سوال پیدا و نتیجه را چاپ کنید.

پیچیدگی زمانی: O(1)

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

map <string, long long int> score, goal_dif, goal_sco, goal_awa;
vector <string> names;

long long int to_number(string s)
{
	long long int result = 0;
	for (int i = 0; i < (int)s.size(); i++)
		result = result * 10 + s[i] - '0';
	return result;
}

string strip(string s)
{
	reverse(s.begin(), s.end());
	while (s.back() == ' ')
		s.pop_back();

	reverse(s.begin(), s.end());
	while (s.back() == ' ')
		s.pop_back();

	return s;
}

bool cmp(string teamA, string teamB)
{
	if (score[teamA] != score[teamB])
		return (score[teamA] > score[teamB]);

	if (goal_dif[teamA] != goal_dif[teamB])
		return (goal_dif[teamA] > goal_dif[teamB]);

	if (goal_sco[teamA] != goal_sco[teamB])
		return (goal_sco[teamA] > goal_sco[teamB]);

	return goal_awa[teamA] > goal_awa[teamB];
}


vector <string> parse(string s)
{
	s = strip(s);
	int mid = -1;
	for (int i = 0; i < (int)s.size(); i++)
		if (s[i] == '.')
		{
			mid = i;
			break;
		}

	string fi = "";
	for (int i = 0; i < mid - 2; i++)
		fi += s[i];
	fi = strip(fi);

	string se = "";
	for (int i = mid + 1; i < (int)s.size(); i++)
		se += s[i];
	se = strip(se);

	string fi_number = "";
	for (int i = (int)fi.size() - 1; i >= 0; i--)
		if (fi[i] == ' ')
			break;
		else
			fi_number += fi[i];
	reverse(fi_number.begin(), fi_number.end());
	fi_number = strip(fi_number);

	string fi_name = "";
	for (int i = 0; i < (int)fi.size() - (int)fi_number.size(); i++)
		fi_name += fi[i];
	fi_name = strip(fi_name);

	string se_number = "";
	for (int i = 0; i < (int)se.size(); i++)
		if (se[i] == ' ')
			break;
		else
			se_number += se[i];
	se_number = strip(se_number);

	string se_name = "";
	for (int i = (int)se_number.size() + 1; i < (int)se.size(); i++)
		se_name += se[i];
	se_name = strip(se_name);

	vector <string> result;
	result.push_back(fi_name);
	result.push_back(fi_number);
	result.push_back(se_name);
	result.push_back(se_number);
	return result;
}

int main()
{
	for (int i = 0; i < 12; i++)
	{
		string s;
		getline(cin, s);

		vector <string> v = parse(s);

		string HomeTeamName = v[0];
		long long int HomeTeamGoals = to_number(v[1]);

		string AwayTeamName = v[2];
		long long int AwayTeamGoals = to_number(v[3]);
		
		names.push_back(HomeTeamName);
		names.push_back(AwayTeamName);

		goal_dif[HomeTeamName] += HomeTeamGoals - AwayTeamGoals;
		goal_dif[AwayTeamName] += AwayTeamGoals - HomeTeamGoals;

		goal_sco[HomeTeamName] += HomeTeamGoals;
		goal_sco[AwayTeamName] += AwayTeamGoals;

		goal_awa[AwayTeamName] += AwayTeamGoals;

		if (HomeTeamGoals > AwayTeamGoals)
			score[HomeTeamName] += 3;
		else if (HomeTeamGoals < AwayTeamGoals)
			score[AwayTeamName] += 3;
		else
			score[HomeTeamName] += 1, score[AwayTeamName] += 1;
	}

	sort(names.begin(), names.end());
	names.resize(unique(names.begin(), names.end()) - names.begin());

	sort(names.begin(), names.end(), cmp);

	cout << names[0] << '\n' << names[1] << '\n';

	return 0;
}

E – Tic-Tac-Toe

صفحه دوز 9 خانه دارد و هر خانه 3 حالت دارد. یعنی در کل 3^9 حالت داریم. می‌توانیم با استفاده از روش «پس‌گرد» از صفحه‌ی خالی شروع کنیم و همه‌ی حالت‌ها را تولید کنیم. در نهایت به‌ازای ورودی‌های مختلف، بررسی کنیم به این ترتیب حالت‌های غیرممکن به راحتی بدست می‌آید. (بررسی بقیه حالت‌ها کار پیچیده‌ای نیست.)

پیچیدگی زمانی: O(1)

#include <iostream>
#include <map>

using namespace std;

map <string, string> ans;

string finished(string state)
{
	char a[3][3];
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			a[i][j] = state[i * 3 + j];

	int cnt_x = 0, cnt_o = 0;
	for (int i = 0; i < 3; i++)
	{
		cnt_x = 0, cnt_o = 0;
		for (int j = 0; j < 3; j++)
		{
			if (a[i][j] == 'X') cnt_x++;
			if (a[i][j] == 'O') cnt_o++;
		}
		if (cnt_x == 3) return "X";
		if (cnt_o == 3) return "O";
	}

	for (int j = 0; j < 3; j++)
	{
		cnt_x = 0, cnt_o = 0;
		for (int i = 0; i < 3; i++)
		{
			if (a[i][j] == 'X') cnt_x++;
			if (a[i][j] == 'O') cnt_o++;
		}
		if (cnt_x == 3) return "X";
		if (cnt_o == 3) return "O";
	}

	cnt_x = 0, cnt_o = 0;
	for (int i = 0; i < 3; i++)
	{
		if (a[i][i] == 'X') cnt_x++;
		if (a[i][i] == 'O') cnt_o++;
	}
	if (cnt_x == 3) return "X";
	if (cnt_o == 3) return "O";

	cnt_x = 0, cnt_o = 0;
	for (int i = 0; i < 3; i++)
	{
		if (a[2 - i][i] == 'X') cnt_x++;
		if (a[2 - i][i] == 'O') cnt_o++;
	}
	if (cnt_x == 3) return "X";
	if (cnt_o == 3) return "O";

	int cnt_q = 0;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			if (a[i][j] == '?')
				cnt_q++;

	if (cnt_q == 0)
		return "Draw";
	return "Unfinished";
}

void bt(string state, char turn)
{
	ans[state] = finished(state);
	if (ans[state] != "Unfinished")
		return;

	for (int i = 0; i < 9; i++)
		if (state[i] == '?')
		{
			state[i] = turn;
			bt(state, (turn == 'X' ? 'O' : 'X'));
			state[i] = '?';
		}
}

int main()
{

	bt("?????????", 'X');

	string state = "", s;
	cin >> s; state += s;
	cin >> s; state += s;
	cin >> s; state += s;

	if (ans.find(state) == ans.end())
		cout << "Invalid\n";
	else
		cout << ans[state] << '\n';

	return 0;
}

F – Circles

صفحه را به صورت یک گراف در نظر بگیرید. راس‌های گراف را تقاطع‌ها و یال‌های گراف را کمان‌های واصل دو تقاطع در نظر بگیرید که هیچ تقاطع بین آن‌ها نباشد. طبق قضیه اویلر برای گراف‌های مسطح داریم:

V+F=E+2

که F تعداد ناحیه‌ها و E تعداد یال‌ها و V تعداد راس‌های گراف است. مسئله پیدا کردن F در گراف بالا است و می‌توان آن را از روی تعداد راس‌ها و یال‌ها مقایسه کرد.

محاسبه‌ی تعداد راس‌ها و یال‌های این گراف، با پیدا کردن همه‌ی تقاطع‌ها از O(n^2) ممکن خواهد بود.

پیچیدگی زمانی: O(N^2)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1010;
const long double EPS = 1e-6;

#define X first
#define Y second
#define R second

typedef pair<long double, long double> Point;

int n, ans, e, v, sum, comps;
long double x[MAXN], r[MAXN];
map<Point, int> mp;
set<Point> st, st2;
vector<Point> circles;
bool mark[MAXN];
vector<int> adj[MAXN];

bool equals(long double a, long double b) {
	return fabs(a - b) < EPS;
}

bool equals(const Point& a, const Point& b) {
	return equals(a.first, b.first) && equals(a.second, b.second);
}

void insertToSet(const Point& p) {
	Point p2 = Point(p.first - EPS, p.second - EPS);
	auto q = st.lower_bound(p2);
	if (q == st.end() || !equals(p, *q)) {
		st.insert(p);
		mp[p]++;
	} else if (q != st.end() && equals(p, *q)) {
		mp[*q]++;
	}
}

void insertToSet2(const Point& p) {
	Point p2 = Point(p.first - EPS, p.second - EPS);
	auto q = st2.lower_bound(p2);
	if (q == st2.end() || !equals(p, *q)) {
		st2.insert(p);
	}
}

void dfs(int v) {
	mark[v] = true;
	for (auto u: adj[v])
		if (!mark[u])
			dfs(u);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, r;
		cin >> x >> r;
		circles.push_back(Point(x, r));
	}
	sort(circles.begin(), circles.end());
	circles.erase(unique(circles.begin(), circles.end()), circles.end());
	n = circles.size();
	for (int i = 0; i < n; i++) {
		st2.clear();
		insertToSet2(Point(circles[i].X - circles[i].R, 0));
		insertToSet2(Point(circles[i].X + circles[i].R, 0));
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			long double d = fabs(circles[i].X - circles[j].X);
			long double rSum = circles[i].R + circles[j].R;
			long double rDif = fabs(circles[i].R - circles[j].R);
			if (d + EPS < rSum && d - EPS > rDif) {
				long double r1 = circles[i].R;
				long double r2 = circles[j].R;
				long double x1 = circles[i].X;
				long double x2 = circles[j].X;
				long double pointX = (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2) / (2 * (x2 - x1));
				long double tmp = r1 * r1 - (pointX - x1) * (pointX - x1);
				long double pointY = sqrt(tmp);
				insertToSet2(Point(pointX, -pointY));
				insertToSet2(Point(pointX, +pointY));
				adj[i].push_back(j);
			}
			else if (equals(d, rSum) || equals(d, rDif)) {
				adj[i].push_back(j);
			}
		}
		Point last = Point(-1e18, -1e18);
		for (auto p: st2) {
			if (!equals(p, last))
				insertToSet(p);
			last = p;
		}
	}
	sum = 0;
	for (auto p: st) {
		sum += 2 * mp[p];
	}

	v = 0;
	Point last = Point(-1e18, -1e18);

	for (auto p: st) {
		if (!equals(p, last)) {
			// cout << p.X << " " << p.Y << endl;
			v++;
		}
		last = p;
	}

	e = sum / 2;
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			comps++;
			dfs(i);
		}
	}
	// cout << e << " " << v << " " << comps << endl;
	ans = e - v + 1 + comps;
	cout << ans << endl;
	return 0;
}

G – Network Connections

مسئله معادل پیدا کردن «دورترین جد مشترک» (یا همان LCA) برای k راس، در درخت است.

مسئله LCA برای دو راس قابل حل است و برای k راس می‌توانیم به صورت دوتا دوتا انجام دهیم تا به راس مورد نظر برسیم.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 1e5, maxl = 20;
vector <int> adj[maxn];
int h[maxn], par[maxn][maxl];

void dfs(int v)
{
	for (int i = 1; par[v][i - 1] != -1; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];

	for (int u : adj[v])
		if (u != par[v][0])
		{
			par[u][0] = v;
			h[u] = h[v] + 1;
			dfs(u);
		}
}

int lca(int v, int u)
{
	if (h[v] < h[u])
		swap(v, u);

	for (int i = maxl - 1; i >= 0; i--)
		if (par[v][i] != -1 && h[par[v][i]] >= h[u])
			v = par[v][i];

	if (v == u)
		return v;

	for (int i = maxl - 1; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];

	return par[v][0];
}

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

	int n, k;
	cin >> n >> k;

	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}

	memset(par, -1, sizeof par);
	dfs(0);

	int ans;
	cin >> ans;
	ans--;

	for (int i = 1; i < k; i++)
	{
		int u;
		cin >> u;
		u--;
		ans = lca(ans, u);
	}

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

H – Music Shopping

ابتدا ترتیب آهنگ‌ها را طوری در نظر بگیرید که اول همه‌ی آهنگ‌های آلبوم 1، سپس همه‌ی آهنگ‌های آلبوم 2 و… آمده است.

فرض کنید dp[i][j] یعنی اگر بخواهیم از آهنگ‌های 1 تا i خرید کنیم و j واحد پول داشته باشیم، حداکثر چند موزیک می‌توان خرید.

برای محاسبه مقدار این dp[i][j] حالت‌بندی زیر را انجام می‌دهیم:

حالت ۱. موزیک‌های آلبوم i را یکی یکی می‌خریم. اگر مقدار j کمتر از هزینه خرید آهنگ باشد:

dp[i][j]=dp[i−1][j]

در غیر این‌صورت اگر هزینه‌ی خرید ترک iام برابر s باشد و j≥s می‌توانیم آن را بخریم یعنی داریم:

dp[i][j]=dp[i−1][j−s]+1

حالت ۲. تمام موزیک‌های آلبوم مربوط به موزیک idx را به‌صورت یکجا می‌خریم. (این حالت را فقط برای موزیک آخر آلبوم بررسی می‌کنیم.)

dp[i][j]=dp[i−size(albums[i])][j−albumPrice[i]]+size(albums[i])

و به این ترتیب پاسخ مسئله در dp[N][P] خواهد بود.

پیچیدگی زمانی: O(NP)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5010;
const int MAXPRICE = 5010;

int n, m, totalPrice;
vector<long long> albums[MAXN];

long long dp[MAXN][MAXPRICE], albumPrice[MAXN];

int main() {
	cin >> n >> m >> totalPrice;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		albums[x].push_back(y);
	}
	for (int i = 1; i <= m; i++)
		cin >> albumPrice[i];
	int idx = 0;
	for (int i = 1; i <= m; i++) {
		for (auto song: albums[i]) {
			idx++;
			for (int price = 0; price <= totalPrice; price++) {
				dp[idx][price] = max(dp[idx - 1][price], (price >= song) ? dp[idx - 1][price - song] + 1 : 0);
			}
		}
		idx++;
		for (int price = 0; price <= totalPrice; price++) {
			dp[idx][price] = max(dp[idx - 1][price], (price >= albumPrice[i]) ? dp[idx - (int)albums[i].size() - 1][price - albumPrice[i]] + (int)albums[i].size() : 0);
		}
	}
	cout << dp[idx][totalPrice] << endl;
	return 0;
}

I – Morning Run

اگر برای هر دونده، نمودار مکان زمان آن را رسم کنیم؛ یک پاره خط کشیده می‌شود. و زمانی دو دونده همدیگر را ملاقات می‌کنند که این دو پاره‌خط با هم تقاطع کرده باشند.

پیچیدگی زمانی: O(N^2)

#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;
typedef pair <LL, LL> point;

#define X first
#define Y second

const int maxn = 100;
LL t[maxn], s[maxn], f[maxn];

LL cross(point A, point B)
{
	return A.X * B.Y - A.Y * B.X;
}

point mnus(point A, point B)
{
	return make_pair(A.X - B.X, A.Y - B.Y);
}

bool intersect(point A_1, point B_1, point A_2, point B_2)
{
	LL c_1 = cross(mnus(B_1, A_1), mnus(B_2, A_1));
	LL c_2 = cross(mnus(B_1, A_1), mnus(A_2, A_1));

	if ((c_1 > 0 && c_2 > 0) || (c_1 < 0 && c_2 < 0))
		return false;

	LL c_3 = cross(mnus(B_2, A_2), mnus(B_1, A_2));
	LL c_4 = cross(mnus(B_2, A_2), mnus(A_1, A_2));

	if ((c_3 > 0 && c_4 > 0) || (c_3 < 0 && c_4 < 0))
		return false;

	return true;
}

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> t[i] >> s[i] >> f[i];

	for (int i = 0; i < n; i++)
	{

		point A_1 = make_pair(t[i], s[i]);
		point B_1 = make_pair(t[i] + abs(f[i] - s[i]), f[i]);


		int r = 0;
		for (int j = 0; j < n; j++)
			if (j != i)
			{
				point A_2 = make_pair(t[j], s[j]);
				point B_2 = make_pair(t[j] + abs(f[j] - s[j]), f[j]);

				if (intersect(A_1, B_1, A_2, B_2))
					r++;
			}

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

	return 0;
}

J – Seasons

در این سوال کافی است فصل مربوط به هر ماه را چاپ کنید.

پیچیدگی زمانی: O(1)

#include<bits/stdc++.h>
using namespace std;

int main() {
    string month;
    cin >> month;
    if (month == "september" || month == "october" || month == "november") {
        cout << "spring";
    } else if (month == "december" || month == "january" || month == "february") {
        cout << "summer";
    } else if (month == "march" || month == "april" || month == "may") {
        cout << "autumn";
    } else if (month == "june" || month == "july" || month == "august") {
        cout << "winter";
    }


}

K – The Sacred Number

می‌توان ثابت کرد که تنها به ازای حالت‌هایی که n مضرب 7 باشد نفر دوم استراتژی برد دارد و در غیراین‌صورت نفر اول برنده استراتژی برد خواهد داشت.

فرض کنید که n مضرب 7 باشد. در این صورت نفر دوم می‌تواند بعد از هر حرکت نفر اول، حرکت خود را مشخص کند. اگر نفر اول عدد k را برداشت نفر دوم عدد 7-k را بردارد. در این صورت همیشه نفر دوم حرکتی برای انجام دادن دارد. با توجه به اینکه بازی پایان پذیر است، نفر دوم استراتژی برد دارد.

اگر n مضرب 7 نبود، یعنی باقی‌مانده‌ی ناصفر r بر 7 داشت، نفر اول می‌تواند در نوبت اول مقدار r را بردارد و بعد از آن استراتژی مشابه نفر دوم در حالت مضرب 7 را در پی بگیرد. به این ترتیب نفر اول در این حالت استراتژی برد دارد.

پیچیدگی زمانی: O(1)

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	cin >> n;
	cout << ((n % 7 == 0) ? "Mat" : "Pat") << endl;
	return 0;
}

L – N-Bonacci Numbers

با بررسی دنباله‌ی F و نحوه‌ی تعریف آن، می‌توان نشان داد که این دنباله N+1 متناوب است و از این خاصیت F و نحوه‌ی تعریف S می‌توان نتیجه گرفت که S هم N+1 متناوب است.

پس کافی است مقدار F و S را فقط برای N+1 جمله‌ی اول محاسبه کنیم تا بتوانیم جواب همه‌ی سوالات را از O(1) بدهیم.

پیچیدگی زمانی: O(N+Q)

// In the Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long double LD;
typedef long long int LL;
typedef pair <int,int> pii;

#define L first
#define R second

const int maxn = 1e5 + 100;
int f[maxn], s[maxn];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> f[i], f[n + 1] ^= f[i];

	for (int i = 1; i <= n + 1; i++)
		s[i] = s[i - 1] ^ f[i];

	while (q--) {
		int idx;
		cin >> idx;
		idx = ((idx - 1) % (n + 1)) + 1;
		cout << s[idx] << '\n';
	}

	return 0;
}