Coming soon..

Coming soon..

#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();
    
}

Coming soon..

Coming soon..

#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();
    }
}

Coming soon..

Coming soon..

#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();
    }
    
}

Coming soon..

Coming soon..

#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();
    
}

Coming soon..

Coming soon..

#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();
    }
}

Coming soon..

Coming soon..

#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();
    
}

Coming soon..

Coming soon..

#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();
    
}

Coming soon..

Coming soon..

#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();
    
}

Coming soon..

Coming soon..

#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();
    }
}

Coming soon..

Coming soon..

#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();
    }
}

Coming soon..

Coming soon..

#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();
    
}

Coming soon..

Coming soon..

#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();
    }
}

Coming soon..

Coming soon..

#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();
    }
}