[A- The Problems Problem](https://mirror.codeforces.com/gym/105262/problem/A)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int N = 12, M = 300, mod = 1e9 + 7;↵
↵
ll power(int a, int p) {↵
if (!p) return 1;↵
return 1ll * (p & 1 ? a : 1) * power(1ll * a * a % mod, p >> 1) % mod;↵
}↵
↵
ll inverse(int a) { return power(a, mod - 2); }↵
↵
ll dp[N + 1][1 << N][M];↵
↵
int timeToSolve[N], timeToFail[N];↵
↵
ll getExpectedScore(int rating, int problemsState, int timeLeft) {↵
if (problemsState == 0 or timeLeft <= 0)↵
return 0;↵
↵
auto &me = dp[rating][problemsState][timeLeft];↵
if (me != -1)↵
return me;↵
↵
↵
int numberOfPaths = 0;↵
ll sumOfPaths = 0;↵
for (int i = 0; i < N; ++i) {↵
if (problemsState & (1 << i)) {↵
numberOfPaths++;↵
if (i < rating)↵
sumOfPaths += (timeLeft >= timeToSolve[i]) + getExpectedScore(rating, problemsState ^ (1 << i), timeLeft - timeToSolve[i]);↵
else↵
sumOfPaths += getExpectedScore(rating, problemsState ^ (1 << i), timeLeft - timeToFail[i]);↵
}↵
}↵
↵
return me = sumOfPaths % mod * inverse(numberOfPaths) % mod;↵
↵
}↵
↵
void solve() {↵
↵
memset(dp, -1, sizeof dp);↵
↵
int n, m, t;↵
cin >> n >> m >> t;↵
vector<vector<int>> problemRatings(n, vector<int>(3));↵
↵
for (int j = 0; j < 3; ++j)↵
for (int i = 0; i < n; ++i)↵
cin >> problemRatings[i][j];↵
↵
sort(problemRatings.begin(), problemRatings.end());↵
↵
for (int i = 0; i < n; ++i) {↵
timeToSolve[i] = problemRatings[i][1];↵
timeToFail[i] = problemRatings[i][2];↵
}↵
↵
for (int i = 0; i < m; ++i) {↵
int rating;↵
cin >> rating;↵
rating = lower_bound(problemRatings.begin(), problemRatings.end(), vector<int>({rating + 1})) - problemRatings.begin();↵
cout << getExpectedScore(rating, (1 << n) - 1, t) << " ";↵
}↵
cout << endl;↵
↵
}↵
↵
int main(int argc, char *argv[]) {↵
int t = 1;↵
// cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[B- Re-Indexing](https://mirror.codeforces.com/gym/105262/problem/B)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
↵
void solve() {↵
↵
int n, q;↵
cin >> n >> q;↵
↵
vector<pair<int, string>> chapters(n+1);↵
for (int i = 0; i < n; ++i) ↵
cin >> chapters[i].second >> chapters[i].first;↵
chapters[n] = {2'000'000'000, "No More Chapters"};↵
sort(chapters.begin(), chapters.end());↵
↵
map<string, string> nextChapter;↵
for (int i = 0; i < n; ++i)↵
nextChapter[chapters[i].second] = chapters[i + 1].second;↵
↵
for (int i = 0; i < q; ++i) {↵
string s;↵
cin >> s;↵
cout << nextChapter[s] << "\n";↵
}↵
↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[C- The Problems Problem](https://mirror.codeforces.com/gym/105262/problem/C)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
int n, m, k, xc[4] = {-1, 1, 0, 0}, yc[4] = {0, 0, -1, 1};↵
↵
bool valid(pair<int, int> position) {↵
return position.first >= 0 and position.first < n and position.second >= 0 and position.second < m;↵
}↵
↵
void solve() {↵
↵
cin >> n >> m >> k;↵
int matrix[n][m];↵
vector<pair<int, int>> positions[26];↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
char c;↵
cin >> c;↵
matrix[i][j] = c - 'a';↵
positions[matrix[i][j]].emplace_back(i, j);↵
}↵
}↵
↵
int minimumDistance[26][26];↵
memset(minimumDistance, -1, sizeof minimumDistance);↵
↵
bool vis[n][m];↵
for (int c = 0; c < 26; ++c) {↵
memset(vis, 0, sizeof vis);↵
↵
queue<pair<int, int>> currentPositions;↵
for (auto position: positions[c]) {↵
vis[position.first][position.second] = true;↵
currentPositions.push(position);↵
}↵
↵
int currentDistance = 0;↵
while (!currentPositions.empty()) {↵
↵
int size = currentPositions.size();↵
while (size--) {↵
↵
auto me = currentPositions.front();↵
currentPositions.pop();↵
↵
int myValue = matrix[me.first][me.second];↵
if (!~minimumDistance[c][myValue])↵
minimumDistance[c][myValue] = currentDistance;↵
↵
for (int i = 0; i < 4; ++i) {↵
pair<int, int> neighbor = {me.first + xc[i], me.second + yc[i]};↵
if (!valid(neighbor) or vis[neighbor.first][neighbor.second])↵
continue;↵
vis[neighbor.first][neighbor.second] = true;↵
currentPositions.push(neighbor);↵
}↵
}↵
currentDistance++;↵
}↵
↵
}↵
↵
↵
string s;↵
cin >> s;↵
ll sum = 0;↵
↵
for (int i = 0; i < k - 1; ++i)↵
sum += minimumDistance[s[i] - 'a'][s[i + 1] - 'a'];↵
↵
cout << sum << endl;↵
↵
↵
}↵
↵
int main(int argc, char *argv[]) {↵
int t = 1;↵
cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[D- The FFT Problem](https://mirror.codeforces.com/gym/105262/problem/D)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const ll N = 1e6;↵
↵
void solve() {↵
ll n;↵
cin >> n;↵
↵
pair<int, ll> ans = {1, -1}; ↵
↵
if (n >= 16)↵
ans = {1, n - 4}; // 14↵
↵
if (n % 4 == 0 and n - 4 > 16)↵
ans = {2, (n - 4) / 4}; // 44 (only case where b > sqrt(n) and number of fours is greater than 1, allowing us to ignore all bases above sqrt(MAX_N))↵
↵
for (ll b = 2; b <= min(b + 1, N); ++b) {↵
int digits = 0, fours = 0;↵
↵
ll current = n;↵
while (current) {↵
digits++;↵
fours += current % b == 4;↵
current /= b;↵
}↵
↵
ans = max(ans, make_pair(fours, b));↵
if (ans.first >= digits) break;↵
}↵
↵
cout << ans.second << endl;↵
↵
}↵
↵
int main(int argc, char *argv[]) {↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[E- Tim Game](https://mirror.codeforces.com/gym/105262/problem/E)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 4e5 + 5;↵
↵
vector<int> adj[N];↵
↵
int getGrundy(int u = 0, int p = 0) {↵
↵
int ret = 0;↵
for (auto v: adj[u])↵
if (v != p) ↵
ret ^= getGrundy(v, u);↵
↵
return ret + 1;↵
}↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
for (int i = 1; i < n; ++i) {↵
int u, v;↵
cin >> u >> v;↵
--u, --v;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
if (getGrundy() > 1)↵
cout << "The Secret Partner\n";↵
else↵
cout << "Eddard\n";↵
↵
for (int i = 0; i < n; ++i)↵
adj[i].clear();↵
↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[F- Fibonacci Strings](https://mirror.codeforces.com/gym/105262/problem/F)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const ll MAX_X = 1000, MAX_K = 1'000'000'000'000'000'000;↵
↵
void solve() {↵
↵
ll fibonacci[MAX_X + 1];↵
cin >> fibonacci[1] >> fibonacci[2];↵
↵
for (int i = 3; i <= MAX_X; ++i) {↵
fibonacci[i] = min(fibonacci[i - 1] + fibonacci[i - 2], MAX_K);↵
}↵
↵
string fibonacciString[4];↵
cin >> fibonacciString[1] >> fibonacciString[2];↵
fibonacciString[3] = fibonacciString[2] + fibonacciString[1];↵
↵
ll x, k;↵
cin >> x >> k;↵
↵
if (x == 1) {↵
cout << fibonacciString[x][k - 1] << endl;↵
return;↵
}↵
while (k > fibonacci[3]) {↵
int l = 2, r = x;↵
while (r - l > 1) {↵
int mid = (l + r) / 2;↵
if (k > fibonacci[mid])↵
l = mid;↵
else↵
r = mid;↵
}↵
k -= fibonacci[l];↵
}↵
cout << fibonacciString[3][k - 1] << endl;↵
↵
}↵
↵
int main() {↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[G- Symmetric Subarrays](https://mirror.codeforces.com/gym/105262/problem/G)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int mod = 1e9 + 7;↵
↵
void manacher(vector<int> &v, vector<int> &radii) {↵
int n = v.size(), last = 0;↵
↵
for (int i = 1; i < n - 1; ++i) {↵
↵
if (last + radii[last] > i)↵
radii[i] = min(last + radii[last] - i, radii[last - (i - last)]);↵
↵
while (v[i + radii[i]] == v[i - radii[i]])↵
++radii[i];↵
↵
if (i + radii[i] > last + radii[last])↵
last = i;↵
↵
}↵
}↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
↵
vector<int> v(2 * n + 1);↵
v[0] = -2;↵
v[2 * n] = -1;↵
↵
for (int i = 0; i < n; ++i) ↵
cin >> v[2 * i + 1];↵
n = 2 * n + 1;↵
↵
vector<int> radii(n);↵
manacher(v, radii);↵
↵
vector<ll> prefixSum(n + 2);↵
↵
for (int i = 1; i < n - 1; ++i) {↵
radii[i] -= (radii[i] & 1) ^ !!v[i];↵
↵
prefixSum[i - radii[i]] += 1;↵
prefixSum[i + 1] -= 2;↵
prefixSum[i + radii[i] + 2] += 1;↵
}↵
↵
for (int c = 0; c < 2; ++c)↵
for (int i = 1; i < n; ++i)↵
prefixSum[i] += prefixSum[i - 1];↵
↵
for (int i = 0; i < n; ++i)↵
prefixSum[i] >>= 1;↵
↵
ll ans = 0;↵
for (int i = 1; i < n - 1; ++i)↵
ans += prefixSum[i] % mod * v[i] % mod;↵
↵
cout << ans % mod << endl;↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[H- Hot Cappuccino](https://mirror.codeforces.com/gym/105262/problem/H)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const ll N = 1e6;↵
↵
int xc[4] = {0, 0, -1, 1}, yc[4] = {-1, 1, 0, 0};↵
↵
void solve() {↵
↵
int n, m;↵
cin >> n >> m;↵
int a[n][m];↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
cin >> a[i][j];↵
}↵
}↵
↵
int cost[n][m][2];↵
memset(cost, -1, sizeof cost);↵
↵
cost[0][0][0] = cost[n - 1][m - 1][1] = 0;↵
↵
for (int mover = 0; mover < 2; ++mover) {↵
deque<pair<int, int>> currentBlocks;↵
currentBlocks.emplace_front((n - 1) * mover, (m - 1) * mover);↵
while (!currentBlocks.empty()) {↵
auto currentBlock = currentBlocks.front();↵
currentBlocks.pop_front();↵
↵
int x = currentBlock.first, y = currentBlock.second;↵
↵
int stepCost = !(a[x][y] & (1 << !mover));↵
↵
for (int i = 0; i < 4; ++i) {↵
int x1 = x + xc[i], y1 = y + yc[i];↵
if (x1 < 0 or x1 >= n or y1 < 0 or y1 >= m or↵
cost[x1][y1][mover] != -1 and cost[x1][y1][mover] <= cost[x][y][mover] + stepCost)↵
continue;↵
↵
cost[x1][y1][mover] = cost[x][y][mover] + stepCost;↵
↵
if (stepCost)↵
currentBlocks.emplace_back(x1, y1);↵
else↵
currentBlocks.emplace_front(x1, y1);↵
}↵
}↵
}↵
↵
int minCost = 1e8;↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
minCost = min(minCost, cost[i][j][0] + cost[i][j][1]);↵
}↵
}↵
↵
cout << minCost << endl;↵
↵
}↵
↵
int main() {↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[I- The Vampire Partner](https://mirror.codeforces.com/gym/105262/problem/I)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
↵
void solve() {↵
↵
ll n, fc;↵
cin >> n >> fc;↵
↵
ll p[n];↵
for (int i = 0; i < n; ++i)↵
cin >> p[i];↵
↵
ll fp = 0;↵
for (int i = 0; i < n and fp <= fc; ++i)↵
fp += p[i] * (i + 1);↵
↵
↵
if (fp == fc)↵
cout << "YES\n";↵
else↵
cout << "NO\n";↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[J- Just One More Bro, I Swear](https://mirror.codeforces.com/gym/105262/problem/J)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
cout << n;↵
↵
}↵
↵
void init() {↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
// cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[K- The Red Tomato](https://mirror.codeforces.com/gym/105262/problem/K)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int mod = 1e9 + 7;↵
↵
void solve() {↵
↵
int e;↵
cin >> e;↵
pair<ll, ll> w = {0, 1e16};↵
while (e--) {↵
int n, m;↵
cin >> n >> m;↵
m = n - m;↵
↵
ll a[n + 2];↵
a[0] = 0;↵
for (int i = 1; i <= n; ++i) ↵
cin >> a[i], a[i] += a[i - 1];↵
a[n + 1] = 1e16;↵
↵
w.first = max(w.first, a[m]);↵
w.second = min(w.second, a[m+1]);↵
↵
}↵
↵
if (w.first >= w.second) ↵
cout << "False Hypothesis\n";↵
else↵
cout << w.first << "\n";↵
↵
}↵
↵
int main() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[L- Growing Letters](https://mirror.codeforces.com/gym/105262/problem/L)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
string generate(int x) {↵
string ret = "a";↵
while (x--)↵
ret += "b" + ret;↵
return ret;↵
}↵
↵
ll fullMask[N];↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
string s;↵
ll ans = 0;↵
for (int i = 0; i < n; ++i) {↵
int x;↵
cin >> x;↵
for (auto c: generate(min(x, 2))) {↵
while (!s.empty() and s.back() == c) {↵
c++, s.pop_back();↵
}↵
s.push_back(c);↵
}↵
ans += max(0ll, fullMask[x + 1] - fullMask[3]);↵
}↵
ans += s.size();↵
cout << ans << endl;↵
↵
}↵
↵
void init() {↵
for (int i = 1; i < N; ++i)↵
fullMask[i] = fullMask[i - 1] * 2 + 1;↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[M- Maximum Subarray Alternating Sum](https://mirror.codeforces.com/gym/105262/problem/M)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
ll kadane(vector<int>& a) {↵
ll sum = 0, maxSum = 0;↵
for (int i = 0; i < a.size(); ++i) {↵
sum += a[i];↵
if (sum < 0) ↵
sum = 0;↵
maxSum = max(maxSum, sum);↵
}↵
return maxSum;↵
}↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) ↵
cin >> a[i];↵
↵
for (int i = 1; i < n; i += 2)↵
a[i] = -a[i];↵
↵
ll answer = kadane(a);↵
↵
for (int i = 0; i < n; ++i)↵
a[i] = -a[i];↵
↵
answer = max(answer, kadane(a));↵
↵
cout << answer << endl;↵
↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int N = 12, M = 300, mod = 1e9 + 7;↵
↵
ll power(int a, int p) {↵
if (!p) return 1;↵
return 1ll * (p & 1 ? a : 1) * power(1ll * a * a % mod, p >> 1) % mod;↵
}↵
↵
ll inverse(int a) { return power(a, mod - 2); }↵
↵
ll dp[N + 1][1 << N][M];↵
↵
int timeToSolve[N], timeToFail[N];↵
↵
ll getExpectedScore(int rating, int problemsState, int timeLeft) {↵
if (problemsState == 0 or timeLeft <= 0)↵
return 0;↵
↵
auto &me = dp[rating][problemsState][timeLeft];↵
if (me != -1)↵
return me;↵
↵
↵
int numberOfPaths = 0;↵
ll sumOfPaths = 0;↵
for (int i = 0; i < N; ++i) {↵
if (problemsState & (1 << i)) {↵
numberOfPaths++;↵
if (i < rating)↵
sumOfPaths += (timeLeft >= timeToSolve[i]) + getExpectedScore(rating, problemsState ^ (1 << i), timeLeft - timeToSolve[i]);↵
else↵
sumOfPaths += getExpectedScore(rating, problemsState ^ (1 << i), timeLeft - timeToFail[i]);↵
}↵
}↵
↵
return me = sumOfPaths % mod * inverse(numberOfPaths) % mod;↵
↵
}↵
↵
void solve() {↵
↵
memset(dp, -1, sizeof dp);↵
↵
int n, m, t;↵
cin >> n >> m >> t;↵
vector<vector<int>> problemRatings(n, vector<int>(3));↵
↵
for (int j = 0; j < 3; ++j)↵
for (int i = 0; i < n; ++i)↵
cin >> problemRatings[i][j];↵
↵
sort(problemRatings.begin(), problemRatings.end());↵
↵
for (int i = 0; i < n; ++i) {↵
timeToSolve[i] = problemRatings[i][1];↵
timeToFail[i] = problemRatings[i][2];↵
}↵
↵
for (int i = 0; i < m; ++i) {↵
int rating;↵
cin >> rating;↵
rating = lower_bound(problemRatings.begin(), problemRatings.end(), vector<int>({rating + 1})) - problemRatings.begin();↵
cout << getExpectedScore(rating, (1 << n) - 1, t) << " ";↵
}↵
cout << endl;↵
↵
}↵
↵
int main(int argc, char *argv[]) {↵
int t = 1;↵
// cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[B- Re-Indexing](https://mirror.codeforces.com/gym/105262/problem/B)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
↵
void solve() {↵
↵
int n, q;↵
cin >> n >> q;↵
↵
vector<pair<int, string>> chapters(n+1);↵
for (int i = 0; i < n; ++i) ↵
cin >> chapters[i].second >> chapters[i].first;↵
chapters[n] = {2'000'000'000, "No More Chapters"};↵
sort(chapters.begin(), chapters.end());↵
↵
map<string, string> nextChapter;↵
for (int i = 0; i < n; ++i)↵
nextChapter[chapters[i].second] = chapters[i + 1].second;↵
↵
for (int i = 0; i < q; ++i) {↵
string s;↵
cin >> s;↵
cout << nextChapter[s] << "\n";↵
}↵
↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[C- The Problems Problem](https://mirror.codeforces.com/gym/105262/problem/C)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
int n, m, k, xc[4] = {-1, 1, 0, 0}, yc[4] = {0, 0, -1, 1};↵
↵
bool valid(pair<int, int> position) {↵
return position.first >= 0 and position.first < n and position.second >= 0 and position.second < m;↵
}↵
↵
void solve() {↵
↵
cin >> n >> m >> k;↵
int matrix[n][m];↵
vector<pair<int, int>> positions[26];↵
↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
char c;↵
cin >> c;↵
matrix[i][j] = c - 'a';↵
positions[matrix[i][j]].emplace_back(i, j);↵
}↵
}↵
↵
int minimumDistance[26][26];↵
memset(minimumDistance, -1, sizeof minimumDistance);↵
↵
bool vis[n][m];↵
for (int c = 0; c < 26; ++c) {↵
memset(vis, 0, sizeof vis);↵
↵
queue<pair<int, int>> currentPositions;↵
for (auto position: positions[c]) {↵
vis[position.first][position.second] = true;↵
currentPositions.push(position);↵
}↵
↵
int currentDistance = 0;↵
while (!currentPositions.empty()) {↵
↵
int size = currentPositions.size();↵
while (size--) {↵
↵
auto me = currentPositions.front();↵
currentPositions.pop();↵
↵
int myValue = matrix[me.first][me.second];↵
if (!~minimumDistance[c][myValue])↵
minimumDistance[c][myValue] = currentDistance;↵
↵
for (int i = 0; i < 4; ++i) {↵
pair<int, int> neighbor = {me.first + xc[i], me.second + yc[i]};↵
if (!valid(neighbor) or vis[neighbor.first][neighbor.second])↵
continue;↵
vis[neighbor.first][neighbor.second] = true;↵
currentPositions.push(neighbor);↵
}↵
}↵
currentDistance++;↵
}↵
↵
}↵
↵
↵
string s;↵
cin >> s;↵
ll sum = 0;↵
↵
for (int i = 0; i < k - 1; ++i)↵
sum += minimumDistance[s[i] - 'a'][s[i + 1] - 'a'];↵
↵
cout << sum << endl;↵
↵
↵
}↵
↵
int main(int argc, char *argv[]) {↵
int t = 1;↵
cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[D- The FFT Problem](https://mirror.codeforces.com/gym/105262/problem/D)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const ll N = 1e6;↵
↵
void solve() {↵
ll n;↵
cin >> n;↵
↵
pair<int, ll> ans = {1, -1}; ↵
↵
if (n >= 16)↵
ans = {1, n - 4}; // 14↵
↵
if (n % 4 == 0 and n - 4 > 16)↵
ans = {2, (n - 4) / 4}; // 44 (only case where b > sqrt(n) and number of fours is greater than 1, allowing us to ignore all bases above sqrt(MAX_N))↵
↵
for (ll b = 2; b <= min(b + 1, N); ++b) {↵
int digits = 0, fours = 0;↵
↵
ll current = n;↵
while (current) {↵
digits++;↵
fours += current % b == 4;↵
current /= b;↵
}↵
↵
ans = max(ans, make_pair(fours, b));↵
if (ans.first >= digits) break;↵
}↵
↵
cout << ans.second << endl;↵
↵
}↵
↵
int main(int argc, char *argv[]) {↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[E- Tim Game](https://mirror.codeforces.com/gym/105262/problem/E)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 4e5 + 5;↵
↵
vector<int> adj[N];↵
↵
int getGrundy(int u = 0, int p = 0) {↵
↵
int ret = 0;↵
for (auto v: adj[u])↵
if (v != p) ↵
ret ^= getGrundy(v, u);↵
↵
return ret + 1;↵
}↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
for (int i = 1; i < n; ++i) {↵
int u, v;↵
cin >> u >> v;↵
--u, --v;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
if (getGrundy() > 1)↵
cout << "The Secret Partner\n";↵
else↵
cout << "Eddard\n";↵
↵
for (int i = 0; i < n; ++i)↵
adj[i].clear();↵
↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[F- Fibonacci Strings](https://mirror.codeforces.com/gym/105262/problem/F)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const ll MAX_X = 1000, MAX_K = 1'000'000'000'000'000'000;↵
↵
void solve() {↵
↵
ll fibonacci[MAX_X + 1];↵
cin >> fibonacci[1] >> fibonacci[2];↵
↵
for (int i = 3; i <= MAX_X; ++i) {↵
fibonacci[i] = min(fibonacci[i - 1] + fibonacci[i - 2], MAX_K);↵
}↵
↵
string fibonacciString[4];↵
cin >> fibonacciString[1] >> fibonacciString[2];↵
fibonacciString[3] = fibonacciString[2] + fibonacciString[1];↵
↵
ll x, k;↵
cin >> x >> k;↵
↵
if (x == 1) {↵
cout << fibonacciString[x][k - 1] << endl;↵
return;↵
}↵
while (k > fibonacci[3]) {↵
int l = 2, r = x;↵
while (r - l > 1) {↵
int mid = (l + r) / 2;↵
if (k > fibonacci[mid])↵
l = mid;↵
else↵
r = mid;↵
}↵
k -= fibonacci[l];↵
}↵
cout << fibonacciString[3][k - 1] << endl;↵
↵
}↵
↵
int main() {↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[G- Symmetric Subarrays](https://mirror.codeforces.com/gym/105262/problem/G)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int mod = 1e9 + 7;↵
↵
void manacher(vector<int> &v, vector<int> &radii) {↵
int n = v.size(), last = 0;↵
↵
for (int i = 1; i < n - 1; ++i) {↵
↵
if (last + radii[last] > i)↵
radii[i] = min(last + radii[last] - i, radii[last - (i - last)]);↵
↵
while (v[i + radii[i]] == v[i - radii[i]])↵
++radii[i];↵
↵
if (i + radii[i] > last + radii[last])↵
last = i;↵
↵
}↵
}↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
↵
vector<int> v(2 * n + 1);↵
v[0] = -2;↵
v[2 * n] = -1;↵
↵
for (int i = 0; i < n; ++i) ↵
cin >> v[2 * i + 1];↵
n = 2 * n + 1;↵
↵
vector<int> radii(n);↵
manacher(v, radii);↵
↵
vector<ll> prefixSum(n + 2);↵
↵
for (int i = 1; i < n - 1; ++i) {↵
radii[i] -= (radii[i] & 1) ^ !!v[i];↵
↵
prefixSum[i - radii[i]] += 1;↵
prefixSum[i + 1] -= 2;↵
prefixSum[i + radii[i] + 2] += 1;↵
}↵
↵
for (int c = 0; c < 2; ++c)↵
for (int i = 1; i < n; ++i)↵
prefixSum[i] += prefixSum[i - 1];↵
↵
for (int i = 0; i < n; ++i)↵
prefixSum[i] >>= 1;↵
↵
ll ans = 0;↵
for (int i = 1; i < n - 1; ++i)↵
ans += prefixSum[i] % mod * v[i] % mod;↵
↵
cout << ans % mod << endl;↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[H- Hot Cappuccino](https://mirror.codeforces.com/gym/105262/problem/H)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const ll N = 1e6;↵
↵
int xc[4] = {0, 0, -1, 1}, yc[4] = {-1, 1, 0, 0};↵
↵
void solve() {↵
↵
int n, m;↵
cin >> n >> m;↵
int a[n][m];↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
cin >> a[i][j];↵
}↵
}↵
↵
int cost[n][m][2];↵
memset(cost, -1, sizeof cost);↵
↵
cost[0][0][0] = cost[n - 1][m - 1][1] = 0;↵
↵
for (int mover = 0; mover < 2; ++mover) {↵
deque<pair<int, int>> currentBlocks;↵
currentBlocks.emplace_front((n - 1) * mover, (m - 1) * mover);↵
while (!currentBlocks.empty()) {↵
auto currentBlock = currentBlocks.front();↵
currentBlocks.pop_front();↵
↵
int x = currentBlock.first, y = currentBlock.second;↵
↵
int stepCost = !(a[x][y] & (1 << !mover));↵
↵
for (int i = 0; i < 4; ++i) {↵
int x1 = x + xc[i], y1 = y + yc[i];↵
if (x1 < 0 or x1 >= n or y1 < 0 or y1 >= m or↵
cost[x1][y1][mover] != -1 and cost[x1][y1][mover] <= cost[x][y][mover] + stepCost)↵
continue;↵
↵
cost[x1][y1][mover] = cost[x][y][mover] + stepCost;↵
↵
if (stepCost)↵
currentBlocks.emplace_back(x1, y1);↵
else↵
currentBlocks.emplace_front(x1, y1);↵
}↵
}↵
}↵
↵
int minCost = 1e8;↵
for (int i = 0; i < n; ++i) {↵
for (int j = 0; j < m; ++j) {↵
minCost = min(minCost, cost[i][j][0] + cost[i][j][1]);↵
}↵
}↵
↵
cout << minCost << endl;↵
↵
}↵
↵
int main() {↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[I- The Vampire Partner](https://mirror.codeforces.com/gym/105262/problem/I)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
↵
void solve() {↵
↵
ll n, fc;↵
cin >> n >> fc;↵
↵
ll p[n];↵
for (int i = 0; i < n; ++i)↵
cin >> p[i];↵
↵
ll fp = 0;↵
for (int i = 0; i < n and fp <= fc; ++i)↵
fp += p[i] * (i + 1);↵
↵
↵
if (fp == fc)↵
cout << "YES\n";↵
else↵
cout << "NO\n";↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[J- Just One More Bro, I Swear](https://mirror.codeforces.com/gym/105262/problem/J)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
cout << n;↵
↵
}↵
↵
void init() {↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
// cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[K- The Red Tomato](https://mirror.codeforces.com/gym/105262/problem/K)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int mod = 1e9 + 7;↵
↵
void solve() {↵
↵
int e;↵
cin >> e;↵
pair<ll, ll> w = {0, 1e16};↵
while (e--) {↵
int n, m;↵
cin >> n >> m;↵
m = n - m;↵
↵
ll a[n + 2];↵
a[0] = 0;↵
for (int i = 1; i <= n; ++i) ↵
cin >> a[i], a[i] += a[i - 1];↵
a[n + 1] = 1e16;↵
↵
w.first = max(w.first, a[m]);↵
w.second = min(w.second, a[m+1]);↵
↵
}↵
↵
if (w.first >= w.second) ↵
cout << "False Hypothesis\n";↵
else↵
cout << w.first << "\n";↵
↵
}↵
↵
int main() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
int t = 1;↵
cin >> t;↵
↵
while (t--)↵
solve();↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
[L- Growing Letters](https://mirror.codeforces.com/gym/105262/problem/L)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
string generate(int x) {↵
string ret = "a";↵
while (x--)↵
ret += "b" + ret;↵
return ret;↵
}↵
↵
ll fullMask[N];↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
string s;↵
ll ans = 0;↵
for (int i = 0; i < n; ++i) {↵
int x;↵
cin >> x;↵
for (auto c: generate(min(x, 2))) {↵
while (!s.empty() and s.back() == c) {↵
c++, s.pop_back();↵
}↵
s.push_back(c);↵
}↵
ans += max(0ll, fullMask[x + 1] - fullMask[3]);↵
}↵
ans += s.size();↵
cout << ans << endl;↵
↵
}↵
↵
void init() {↵
for (int i = 1; i < N; ++i)↵
fullMask[i] = fullMask[i - 1] * 2 + 1;↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[M- Maximum Subarray Alternating Sum](https://mirror.codeforces.com/gym/105262/problem/M)↵
------------------↵
↵
<spoiler summary="Hints">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Coming soon..↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int N = 17, mod = 1e9 + 7;↵
↵
mt19937 rnd(time(nullptr));↵
↵
ll kadane(vector<int>& a) {↵
ll sum = 0, maxSum = 0;↵
for (int i = 0; i < a.size(); ++i) {↵
sum += a[i];↵
if (sum < 0) ↵
sum = 0;↵
maxSum = max(maxSum, sum);↵
}↵
return maxSum;↵
}↵
↵
void solve() {↵
↵
int n;↵
cin >> n;↵
↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) ↵
cin >> a[i];↵
↵
for (int i = 1; i < n; i += 2)↵
a[i] = -a[i];↵
↵
ll answer = kadane(a);↵
↵
for (int i = 0; i < n; ++i)↵
a[i] = -a[i];↵
↵
answer = max(answer, kadane(a));↵
↵
cout << answer << endl;↵
↵
↵
}↵
↵
void init() {↵
cin.tie(nullptr);↵
cin.sync_with_stdio(false);↵
}↵
↵
int main() {↵
init();↵
int testCases = 1;↵
cin >> testCases;↵
for (int testCase = 1; testCase <= testCases; ++testCase) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
