C++ April 2020

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

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> c(m);
    int total_platform_length = 0;
    for (int i = 0; i < m; i++) {
        cin >> c[i];
        total_platform_length += c[i];
    }

    bool possible = true;
    int total_blanks;
    if ((m+1)*(d-1) < n - total_platform_length) {
        possible = false;
    }
    else {
        total_blanks = n - total_platform_length;
    }

    if (possible) {
        cout << "Yes" << endl;
        // Printing blanks and platforms
        for (int i = 0; i < m; i++) {
            // Blanks
            for (int j = 0; j < total_blanks/(m+1); j++) {
                cout << 0 << " ";
            }
            if (i < total_blanks%(m+1)) {
                cout << 0 << " ";
            }
            // Platforms
            for (int j = 0; j < c[i]; j++) {
                cout << i+1 << " ";
            }
        }
        // Last blank
        for (int j = 0; j < total_blanks/(m+1); j++) {
            cout << 0 << " ";
        }
        cout << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;
}

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        bool impossible = false;

        int next;
        cin >> next;
        int min_appeared = next;
        int prev;
        for (int i = 1; i < n; i++) {
            prev = next;
            cin >> next;
            if (!impossible) {
                if (next < min_appeared) {
                    min_appeared = next;
                }
                else {
                    if (next != prev+1) {
                        impossible = true;
                    }
                }
            }
        }
        if (impossible) {
            cout << "No" << endl;
        }
        else {
            cout << "Yes" << endl;
        }
    }
    return 0;
}

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

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n, k;
        cin >> n >> k;

        // Setting up input
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // Number of peaks in [i, i+k-1]
        vector<bool> is_peak(n, false);
        for (int i = 1; i < n-1; i++) {
            if (a[i] > a[i-1] && a[i] > a[i+1]) {
                is_peak[i] = true;
            }
        }
        vector<int> num_peaks(n, 0);
        int num_peaks_in_last_k = 0;
        int max_num_peaks = 0;
        int left = 0;
        for (int i = 1; i < n; i++) {
            if (is_peak[i-1]) {
                num_peaks_in_last_k++;
            }
            if (i >= k-1 && is_peak[i-k+1]) {
                num_peaks_in_last_k--;
            }
            num_peaks[i] = num_peaks_in_last_k;
            if (i >= k-1 && num_peaks[i] > max_num_peaks) {
                max_num_peaks = num_peaks[i];
                left = i-k+1;
            }
        }

        cout << max_num_peaks+1 << " " << left+1 << endl;

    }
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        if ((a+b)*n < c-d || (a-b)*n > c+d) {
            cout << "No" << endl;
        }
        else {
            cout << "Yes" << endl;
        }
    }
    return 0;
}

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

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        vector<int> c(10);
        int min_candles = 0;
        for (int i = 0; i < 10; i++) {
            cin >> c[i];
            if ((min_candles == 0 && c[i] <= c[min_candles]) || c[i] < c[min_candles]) {
                min_candles = i;
            }
        }
        if (c[min_candles] == 0) {
            if (min_candles == 0) {
                cout << 10 << endl;
            }
            else {
                cout << min_candles << endl;
            }
        }
        else if (min_candles == 0) {
            cout << 1;
            for (int i = 0; i < c[min_candles]+1; i++) {
                cout << min_candles;
            }
            cout << endl;
        }
        else {
            for (int i = 0; i < c[min_candles]+1; i++) {
                cout << min_candles;
            }
            cout << endl;
        }
    }
    return 0;
}

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

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        bool current_positive = (a[0] > 0);
        long long current_max_pos = LLONG_MIN;
        long long current_max_neg = LLONG_MIN;
        long long result = 0;
        for (int i = 0; i < n; i++) {
            if (current_positive) {
                if (a[i] > 0) {
                    current_max_pos = max(current_max_pos, a[i]);
                }
                else {
                    result += current_max_pos;
                    current_max_neg = a[i];
                    current_positive = false;
                }
            }
            else { // if (current_negative)
                if (a[i] < 0) {
                    current_max_neg = max(current_max_neg, a[i]);
                }
                else {
                    result += current_max_neg;
                    current_max_pos = a[i];
                    current_positive = true;
                }
            }
        }
        if (current_positive) {
            result += current_max_pos;
        }
        else { // if (current_negative)
            result += current_max_neg;
        }

        cout << result << endl;
    }
    return 0;
}

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        // Idea:
        // first half: 2 4  6 10  12 14...
        // second half: 1 5  7 9  11 15...
        // hence, n has to be divisiblea by 4 for this to be possible.
        if (n%4 != 0) {
            cout << "NO" << endl;
        }
        else {
            cout << "YES" << endl;
            for (int i = 0; i < n/2; i++) {
                if (i%4 == 0) {
                    cout << (i/2*5) + 2 << " ";
                }
                else if (i%4 == 1) {
                    cout << (i/2*5) + 4 << " ";
                }
                else if (i%4 == 2) {
                    cout << (i/2*5) + 1 << " ";
                }
                else if (i%4 == 3) {
                    cout << (i/2*5) + 5 << " ";
                }
            }
            for (int i = 0; i < n/2; i++) {
                if (i%4 == 0) {
                    cout << (i/2*5) + 1 << " ";
                }
                else if (i%4 == 1) {
                    cout << (i/2*5) + 5 << " ";
                }
                else if (i%4 == 2) {
                    cout << (i/2*5) + 2 << " ";
                }
                else if (i%4 == 3) {
                    cout << (i/2*5) + 4 << " ";
                }
            }
            cout << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        // Find if there is a 'b' such that:
        // x*b=n, b is 1111.. form in binary.
        bitset<32> b(3);
        for (int i = 1; i < 32; i++) {
            b[i] = 1;
            if (n%b.to_ulong() == 0) {
                cout << n/b.to_ulong() << endl;
                break;
            }
        }
    }
    return 0;
}

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

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int max_diff = 0;
        int first, second;
        for (int i = 1; i < n; i++) {
            if (max_diff < abs(a[i]-a[i-1])) {
                max_diff = abs(a[i]-a[i-1]);
                first = i;
                second = i+1;
            }

        }

        if (max_diff > 1) {
            cout << "YES" << endl;
            cout << first << " " << second << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1334/problem/C
1334C, Circle of Monsters
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Calculate for each monsters, needed shots assuming that the previous monster died.
    // Add all of them, and lastly add the minimum bi existing.
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        scanf("%d", &n);
        // cin >> n;
        vector<long long> healths(n);
        vector<long long> explosion(n);
        long long min_explosion = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            // cin >> healths[i] >> explosion[i];
            scanf("%lld%lld", &healths[i], &explosion[i]);
            if (healths[i] < min_explosion) {
                min_explosion = healths[i];
            }
            if (explosion[i] < min_explosion) {
                min_explosion = explosion[i];
            }
        }
        long long num_shots = min_explosion;
        if (healths[0]-explosion[n-1] > 0) {
            num_shots += healths[0]-explosion[n-1];
        }
        for (int i = 1; i < n; i++) {
            if (healths[i]-explosion[i-1] > 0) {
                num_shots += healths[i]-explosion[i-1];
            }
        }

        // cout << num_shots << endl;
        printf("%lld\n", num_shots);
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1336/problem/A
1336A, Linova and Kingdom
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void set_children_DFS(const int& current, vector<int>& depths, vector<int>& parents,
    vector<int>& num_children, const vector<vector<int>>& connected) {
    for (int i = 0; i < connected[current].size(); i++) {
        if (connected[current][i] == parents[current]) {
            continue;
        }
        int child = connected[current][i];
        parents[child] = current;
        depths[child] = depths[current]+1;
        set_children_DFS(child, depths, parents, num_children, connected);
        num_children[current] += num_children[child] + 1;
    }
}

long long get_happiness(const int& node, const vector<int>& depths,
    const vector<int>& parents, const vector<bool>& is_tourism) {
    if (is_tourism[node]) {
        return depths[node]+1;
    }
    else if (node == 0) {
        return 0;
    }
    else {
        return get_happiness(parents[node], depths, parents, is_tourism);
    }
}

int main() {
    int n, k;
    cin >> n >> k;

    // Containers
    vector<vector<int>> connected(n);
    vector<int> parents(n, -1);
    vector<int> depths(n);
    vector<int> num_children(n, 0);

    // Filling up containers from input
    int a, b;
    for (int i = 0; i < n-1; i++) {
        cin >> a >> b;
        connected[a-1].push_back(b-1);
        connected[b-1].push_back(a-1);
    }

    // Setting up data
    depths[0] = 0;
    set_children_DFS(0, depths, parents, num_children, connected);

    // Sorting for greedy
    vector<pair<int, int>> greedy_pair(n);
    for (int i = 0; i < n; i++) {
        greedy_pair[i].first = depths[i] - num_children[i];
        greedy_pair[i].second = i;
    }
    sort(greedy_pair.begin(), greedy_pair.end(), greater<pair<int, int>>());

    // Choose k nodes and set them non-tourism.
    vector<bool> is_tourism(n, true);
    for (int i = 0; i < k; i++) {
        is_tourism[greedy_pair[i].second] = false;
    }

    long long total_happiness = 0;
    for (int i = 0; i < n; i++) {
        if (!is_tourism[i] && (i == 0 || is_tourism[parents[i]])) {
            total_happiness += (num_children[i]+1) * get_happiness(i, depths, parents, is_tourism);
        }
    }

    cout << total_happiness << endl;

    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1255/problem/C
1255C, League of Leesins
*/
#include <iostream>
#include <vector>
using namespace std;

pair<int, int> get_next_two(const int& prev1, const int& prev2, const vector<int>& related) {
    int first = -1;
    int first_occurrence = 0;
    int second = -1;
    int second_occurrence = 0;
    for (int i = 0; i < related.size(); i++) {
        if (related[i] == prev1 || related[i] == prev2) {
            continue;
        }
        else if (first_occurrence == 0) {
            first = related[i];
            first_occurrence++;
        }
        else if (related[i] == first) {
            first_occurrence++;
        }
        else if (second_occurrence == 0) {
            second = related[i];
            second_occurrence++;
        }
        else {
            second_occurrence++;
        }
    }
    if (first_occurrence > second_occurrence) {
        return pair<int, int>(first, second);
    }
    else {
        return pair<int, int>(second, first);
    }
}

void set_next_two_element(const int& done_ind, vector<int>& result, const vector<vector<int>>& related) {
    if (done_ind == result.size()-1) {
        return;
    }
    else if (done_ind == result.size()-2) {
        // Only one left
        pair<int, int> next_one;
        if (done_ind > 1) {
            next_one = get_next_two(result[done_ind-1], result[done_ind-2], related[result[done_ind]]);
        }
        else {
            next_one = get_next_two(result[done_ind-1], -1, related[result[done_ind]]);
        }
        result[done_ind+1] = next_one.first;
    }
    else {
        // set two more
        pair<int, int> next_two;
        if (done_ind > 1) {
            next_two = get_next_two(result[done_ind-1], result[done_ind-2], related[result[done_ind]]);
        }
        else {
            next_two = get_next_two(result[done_ind-1], -1, related[result[done_ind]]);
        }

        result[done_ind+1] = next_two.first;
        result[done_ind+2] = next_two.second;
    }
}

int main() {
    int n;
    cin >> n;

    // Containers
    vector<vector<int>> related(n);

    // Setting up input
    for (int i = 0; i < n-2; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        // Make them start from 0
        a--; b--; c--;

        // Save into containers
        related[a].push_back(b);
        related[a].push_back(c);
        related[b].push_back(a);
        related[b].push_back(c);
        related[c].push_back(a);
        related[c].push_back(b);
    }

    vector<int> result(n);

    // Finding a first element (smaller of two)
    for (int i = 0; i < n; i++) {
        if (related[i].size() == 2) {
            result[0] = i;
            break;
        }
    }

    // Finding the second element
    if (related[related[result[0]][0]].size() == 4) {
        result[1] = related[result[0]][0];
    }
    else {
        result[1] = related[result[0]][1];
    }

    for (int i = 0; i < (n+1)/2-1; i++) {
        set_next_two_element(2*i+1, result, related);
    }

    for (int i = 0; i < n; i++) {
        cout << result[i]+1 << " ";
    }

    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1335/problem/A
Problem A: Candies and Two Sisters
During a 2-hour contest: Codeforces Round #634
*/
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        cout << max(0, (n+1)/2 - 1) << endl;
    }

    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1335/problem/B
Problem B: Construct the String
During a 2-hour contest: Codeforces Round #634
*/
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n, a, b;
        cin >> n >> a >> b;
        for (int i = 0; i < n; i++) {
            if (i%a < b) {
                cout << static_cast<char>('a'+i%a);
            }
            else {
                cout << 'a';
            }
        }
        cout << endl;
    }

    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1335/problem/C
Problem C: Two Teams Composing
During a 2-hour contest: Codeforces Round #634
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        // skills[s] = (# of people with skill s)
        vector<int> skills(n, 0);
        int next;
        for (int i = 0; i < n; i++) {
            cin >> next;
            skills[next-1]++;
        }

        // num_diff_skills, max_same_skills
        // which are possible maximum values of two teams
        int num_diff_skills = 0;
        int max_same_skills = 0;
        for (int i = 0; i < n; i++) {
            if (skills[i] > 0) {
                num_diff_skills++;
                max_same_skills = max(max_same_skills, skills[i]);
            }
        }

        // Result is the smaller of both
        // Boundary case: when the two are same,
        // there is an overlapping student so -1.
        if (num_diff_skills == max_same_skills) {
            cout << num_diff_skills-1 << endl;
        }
        else {
            cout << min(num_diff_skills, max_same_skills) << endl;
        }
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1335/problem/D
Problem D: Anti-Sudoku
During a 2-hour contest: Codeforces Round #634
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        vector<vector<char>> sudoku(9);

        // Filling sudoku from input
        for (int i = 0; i < 9; i++) {
            vector<char> sudoku_line(9);
            for (int j = 0; j < 9; j++) {
                cin >> sudoku_line[j];
            }
            sudoku[i] = sudoku_line;
        }

        // I'm too lazy to explain this.
        // To understand: draw 9*9 sudoku and track what it changes
        for (int i = 0; i < 9; i++) {
            int col = (3*i)%9+i/3;
            sudoku[i][col]++;
            if (sudoku[i][col] > '9') {
                sudoku[i][col] = '1';
            }
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << sudoku[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1339/problem/C
Problem C: Powered Addition
During a 2-hour contest: Codeforces Round #633
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        bool already_sorted = true;
        int x = 1;
        long long pow_2 = 1;
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i-1]) {
                already_sorted = false;
                if (a[i-1]-a[i] > pow_2) {
                    x = max(x, static_cast<int>((log2(a[i-1]-a[i])))+1);
                    pow_2 = pow(2, x-1);
                }
                a[i] = a[i-1];
            }
        }

        if (already_sorted) {
            cout << 0 << endl;
        }
        else {
            cout << x << endl;
        }

    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1339/problem/B
Problem B: Sorted Adjacent Differences
During a 2-hour contest: Codeforces Round #633
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        if (n%2 == 1) {
            cout << a[n/2] << " ";
            for (int i = n/2-1; i >= 0; i--) {
                cout << a[n-i-1] << " " << a[i] << " ";
            }
        }
        else {
            for (int i = n/2-1; i >= 0; i--) {
                cout << a[n-i-1] << " " << a[i] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1339/problem/A
Problem A: Filling Diamonds
During a 2-hour contest: Codeforces Round #633
*/
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
        cout << n << endl;
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1252/problem/A
1252A, Copying Homework
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        cout << n - a[i] + 1 << " ";
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74
Problem A: Pattern Matching
During a 2 hours and 30 mintues cotest: 2020 Google Code Jam 1A
*/

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        bool impossible = false;
        bool without_asterisk_found = false;
        string without_asterisk;

        // Setting up inputs
        vector<string> patterns(n);
        vector<string> front_parts;
        vector<string> back_parts;
        vector<string> middle_parts;
        for (int i = 0; i < n; i++) {
            cin >> patterns[i];

            int front_end = -1;
            int back_start = patterns[i].size();

            bool asterisk_appeared = false;
            // Getting front part
            for (int j = 0; j < patterns[i].size() && !impossible; j++) {
                if (patterns[i][j] == '*') {
                    asterisk_appeared = true;
                    if (j > 0) {
                        front_parts.push_back(patterns[i].substr(0, j));
                        front_end = j;
                    }
                    break;
                }
            }
            // Boundary case: String without *
            if (!asterisk_appeared) {
                if (without_asterisk_found
                    && without_asterisk != patterns[i]) {
                    impossible = true;
                }
                without_asterisk_found = true;
                without_asterisk = patterns[i];
            }
            else {
                for (int j = patterns[i].size()-1; j >= 0; j--) {
                    if (patterns[i][j] == '*') {
                        if (j < patterns[i].size()-1) {
                            back_parts.push_back(patterns[i].substr(j+1, patterns[i].size()-j-1));
                            back_start = j;
                        }
                        break;
                    }
                }
            }

            middle_parts.push_back(patterns[i].substr(front_end+1, back_start-front_end-1));

        }

        // Boundary case: String without asterisk exists
        // : Match every front, back and check if they match.
        if (!impossible && without_asterisk_found) {
            for (int i = 0; i < front_parts.size(); i++) {
                for (int j = 0; j < front_parts[i].size(); j++) {
                    if (front_parts[i][j] != without_asterisk[j]) {
                        impossible = true;
                        break;
                    }
                }
                if (impossible) {
                    break;
                }
            }
            for (int i = 0; i < back_parts.size(); i++) {
                int start_pos = without_asterisk.size()-back_parts[i].size();
                for (int j = 0; j < back_parts[i].size(); j++) {
                    if (back_parts[i][j] != without_asterisk[start_pos+j]) {
                        impossible = true;
                        break;
                    }
                }
                if (impossible) {
                    break;
                }
            }
            cout << "Case #" << tc+1 << ": " << without_asterisk << endl;
        }
        // Matching front / back strings.
        // When done, match the middles by simply concatenating.
        else if (!impossible) {
            string front;
            int longest_front_ind = 0;
            for (int i = 0; i < front_parts.size(); i++) {
                if (front_parts[i].size() > front_parts[longest_front_ind].size()) {
                    longest_front_ind = i;
                }
            }
            if (front_parts.size() > 0) {
                front = front_parts[longest_front_ind];
                for (int i = 0; i < front_parts.size(); i++) {
                    for (int j = 0; j < front_parts[i].size(); j++) {
                        if (front_parts[i][j] != front[j]) {
                            impossible = true;
                            break;
                        }
                    }

                }
            }

            string back;
            int longest_back_ind = 0;
            if (!impossible) {
                for (int i = 0; i < back_parts.size(); i++) {
                    if (back_parts[i].size() > back_parts[longest_back_ind].size()) {
                        longest_back_ind = i;
                    }
                }
                if (back_parts.size() > 0) {
                    back = back_parts[longest_back_ind];
                    for (int i = 0; i < back_parts.size(); i++) {
                        int start_pos = back.size()-back_parts[i].size();
                        for (int j = 0; j < back_parts[i].size(); j++) {
                            if (back_parts[i][j] != back[start_pos+j]) {
                                impossible = true;
                                break;
                            }
                        }
                    }
                }
            }


            if (!impossible) {
                cout << "Case #" << tc+1 << ": ";
                cout << front;
                for (int i = 0; i < middle_parts.size(); i++) {
                    for (int j = 0; j < middle_parts[i].size(); j++) {
                        if (middle_parts[i][j] != '*') {
                            cout << middle_parts[i][j];
                        }
                    }
                }
                cout << back << endl;
            }


        }

        if (impossible) {
            cout << "Case #" << tc+1 << ": *" << endl;
        }




    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1333/problem/A
1333A, Little Artem
*/
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n, m;
        cin >> n >> m;

        if (n == 2 && m == 3) {
            for (int j = 0; j < m; j++) {
                if (j < 3) {
                    cout << 'B';
                }
                else {
                    cout << 'W';
                }
            }
            cout << endl;
            for (int j = 0; j < m; j++) {
                if (j == 1) {
                    cout << 'B';
                }
                else {
                    cout << 'W';
                }
            }
            cout << endl;
        }
        else if (n == 2 && m > n) {
            for (int j = 0; j < m; j++) {
                if (j < 2) {
                    cout << 'B';
                }
                else {
                    cout << 'W';
                }
            }
            cout << endl;
            for (int j = 0; j < m; j++) {
                if (j == 1 || j == 2) {
                    cout << 'B';
                }
                else {
                    cout << 'W';
                }
            }
            cout << endl;
        }
        else if (n >= m) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (j <= i) {
                        cout << 'B';
                    }
                    else {
                        cout << 'W';
                    }
                }
                cout << endl;
            }
        }
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i == n-1 && j == 0) {
                        cout << 'W';
                    }
                    else if (j <= i) {
                        cout << 'B';
                    }
                    else {
                        cout << 'W';
                    }
                }
                cout << endl;
            }
        }
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1251/problem/D
1251D, Salary Changing
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool isValid(const long long& median, const vector<pair<long long, long long>>& ranges, const long long& s) {
    // check if a median works
    // Select half with lowest 'low'
    // that has 'high' at least 'median'.
    // (if can't be selected, return false.)
    // Sum of the whole. Compare with s.

    long long select_count = 0;
    long long sum = 0;
    for (int i = 0; i < ranges.size(); i++) {
        if (select_count < (ranges.size()+1)/2 && ranges[i].second >= median) {
            sum += max(ranges[i].first, median);
            select_count++;
        }
        else {
            sum += ranges[i].first;
        }
    }
    if (select_count < (ranges.size()+1)/2) {
        return false;
    }
    else {
        return (sum <= s);
    }
}

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        long long n, s;
        cin >> n >> s;

        // Setting up input
        vector<pair<long long, long long>> ranges(n);
        long long min_low = s;
        long long max_high = 0;
        for (int i = 0; i < n; i++) {
            cin >> ranges[i].first >> ranges[i].second;
            min_low = min(ranges[i].first, min_low);
            max_high = max(ranges[i].second, max_high);
        }
        sort(ranges.begin(), ranges.end(), greater<pair<long long, long long>>());

        long long low = min_low;
        long long high = max_high;
        long long middle;
        while (low < high) {
            middle = (low+high+1)/2;

            if (isValid(middle, ranges, s)) {
                low = middle;
            }
            else {
                high = middle-1;
            }
        }

        cout << low << endl;
    }

    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/contest/1271/problem/B
1271B, Blocks
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> isBlack(n);
    char next;
    for (int i = 0; i < n; i++) {
        cin >> next;
        if (next == 'B') {
            isBlack[i] = true;
        }
        else {
            isBlack[i] = false;
        }
    }

    bool possible = true;

    vector<bool> flip(n, false);
    for (int i = 0; i < n-1; i++) {
        if (!isBlack[i]) {
            flip[i] = !flip[i];
            isBlack[i] = !isBlack[i];
            isBlack[i+1] = !isBlack[i+1];
        }
    }
    if (isBlack[n-1]) {
        // done
    }
    else if ((n-1)%2 == 1) {
        possible = false;
    }
    else {
        for (int i = 0; i < n-1; i+=2) {
            flip[i] = !flip[i];
        }
    }

    if (!possible) {
        cout << -1 << endl;
    }
    else {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (flip[i]) {
                count++;
            }
        }
        cout << count << endl;
        for (int i = 0; i < n; i++) {
            if (flip[i]) {
                cout << i+1 << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

/*
This code is an accepted solution to:
https://codeforces.com/problemset/problem/1301/C
1301C, Ayoub's function
*/

#include <iostream>
using namespace std;

long long num_substr(const long long& len) {
    return len*(len+1)/2;
}

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        long long n, m;
        cin >> n >> m;

        long long result = num_substr(n);
        if (m == n) {
            // Boundary case: no subtraction
        }
        else if (m == 0) {
            // Boundary case: 0 substring
            result = 0;
        }
        else if (m < n/2) {
            int remainder = (n-m)%(m+1);
            int chunksize = (n-m)/(m+1);
            result -= (m+1-remainder)*num_substr(chunksize);
            if (remainder > 0) {
                result -= remainder*num_substr(chunksize+1);
            }
        }
        else {
            result -= (n-m);
        }

        cout << result << endl;
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f
Problem C: Parenting Partnering Returns (7+12 points)
During 2020 Google Code Jam Qualification Round (27 hours)
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        // Setting up input
        // <<start, end>, index>
        vector<pair<pair<int, int>, int>> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i].first.first >> a[i].first.second;
            a[i].second = i;
        }

        // Sort the input
        vector<pair<pair<int, int>, int>> as = a;
        sort(as.begin(), as.end());

        int C_ended = 0, J_ended = 0;
        bool impossible = false;
        vector<char> result(n);
        for (int i = 0; i < n; i++) {
            if (as[i].first.first >= C_ended) {
                // Cameron gets it
                result[as[i].second] = 'C';
                C_ended = as[i].first.second;
            }
            else if (as[i].first.first >= J_ended) {
                // Jamie gets it
                result[as[i].second] = 'J';
                J_ended = as[i].first.second;
            }
            else {
                // Impossible
                impossible = true;
                break;
            }
        }

        // Print result
        cout << "Case #" << tc+1 << ": ";
        if (impossible) {
            cout << "IMPOSSIBLE";
        }
        else {
            for (int i = 0; i < n; i++) {
                cout << result[i];
            }
        }
        cout << endl;

    }
    return 0;
}

/*
This code is an accepted solution to:
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f
Problem B: Nesting depth (5+11 points)
During 2020 Google Code Jam Qualification Round (27 hours)
*/
#include <iostream>
#include <string>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        string s;
        cin >> s;
        int tracker = '0';
        string result;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] > tracker) {
                for (int j = 0; j < s[i]-tracker; j++) {
                    result += "(";
                }
            }
            else if (s[i] < tracker) {
                for (int j = 0; j < tracker-s[i]; j++) {
                    result += ")";
                }
            }
            result += s[i];
            tracker = s[i];
        }
        if (tracker > 0) {
            for (int j = 0; j < tracker-'0'; j++) {
                result += ")";
            }
        }

        cout << "Case #" << tc+1 << ": " << result << endl;
    }
    return 0;
}

/*
This code is an accepted solution to:
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c
Problem A: Vestigium (7 points)
During 2020 Google Code Jam Qualification Round (27 hours)
*/
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;

        // Setting up input
        vector<vector<int>> m(n);
        vector<vector<pair<int, int>>> positions_asz(n);
        for (int i = 0; i < n; i++) {
            vector<int> row(n);
            for (int j = 0; j < n; j++) {
                cin >> row[j];
                positions_asz[row[j]-1].push_back(pair<int, int>(i+1, j+1));
            }
            m[i] = row;
        }


        // Calculating trace
        int trace = 0;
        for (int i = 0; i < n; i++) {
            trace += m[i][i];
        }

        set<pair<int, int>> duplicate_rows;
        set<pair<int, int>> duplicate_cols;

        // Getting duplicate rows / cols
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < positions_asz[i].size(); j++) {
                for (int k = j+1; k < positions_asz[i].size(); k++) {
                    if (positions_asz[i][j].first == positions_asz[i][k].first) {
                        duplicate_rows.insert(pair<int, int>(positions_asz[i][j].first, positions_asz[i][k].first));
                    }
                    if (positions_asz[i][j].second == positions_asz[i][k].second) {
                        duplicate_cols.insert(pair<int, int>(positions_asz[i][j].second, positions_asz[i][k].second));
                    }
                }
            }
        }

        // Printing results
        cout << "Case #" << tc+1 << ": "
            << trace << " " << duplicate_rows.size() << " "
            << duplicate_cols.size() << endl;

    }


    return 0;
}