There are n teams. Each team has 3 trick-or-treaters. Therefore, there are $$$3 \cdot n$$$ trick-or-treaters.

Time complexity: $$$O(1)$$$

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;

    cout<<3*n<<endl;

    return 0;
}

Let $$$m$$$ be the maximum value in $$$a$$$. After $$$n \cdot (m−1)$$$ moves, only ghosts with $$$a_i$$$=$$$m$$$ will have candies remaining, so no other ghosts can win. If $$$a_i$$$=$$$m$$$, then ghost $$$i$$$ can win if the first ghost is ghost $$$(i \bmod n) + 1$$$. Hence, the answer is the number of maximums of $$$a$$$.

Time complexity: $$$O(n)$$$

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    
    int mx = 0, ans = 0;
    for (int i : a) mx = max(i, mx);
    for (int i : a) ans += i == mx;
    cout << ans << '\n';
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) solve();
}

To begin with, we note that it makes no sense to buy the same number of pumpkins more than 3 times, and it also makes no sense to buy more than $$$(3^{\lfloor \log_3 n \rfloor})$$$ pumpkins at once. Indeed, if we buy $$$(3^k)$$$ pumpkins 3 times, we will end up with $$$(3^{k+1})$$$ pumpkins , and we could have bought $$$(3^{k+1})$$$ pumpkins in one deal, which would have resulted in 2 fewer deals. The second statement means that it makes no sense to buy more pumpkins than necessary. Thus, we can assign an integer from 0 to 2 to all possible deal options. Let us assign the number $$$(w_i)$$$ to the $$$(i)$$$-th deal option; then the following condition must be satisfied:

As can be observed, this is the definition of the representation of the number $$$(n)$$$ in the ternary numeral system. The representation in the ternary system is unique, which means we will find this representation $$$((w_0,w_1,\ldots,w_{\lfloor \log_3 n \rfloor}))$$$, and the answer, as can be seen, will be:

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long min_k = 0;
        long long min_cost = 0;
        int sz = 0;
        while (n) {
            min_k += n % 3;
            min_cost += (n % 3) * cost[sz];
            n /= 3;
            sz++;
        }
        cout << min_cost << '\n';
    }
    
    return 0;
}

There are two solutions:

1. We can make partial sums $$$(sum_i = a_1 + a_2 + \ldots + a_i)$$$ and then make a binary search for each query $$$q_i$$$ to find the result $$$j$$$ with the properties $$$sum_{j-1} \lt q_i$$$ and

   Unable to parse markup [type=CF_MATHJAX]

   .

2. We can precalculate the index of the pile for each worm and then answer for each query in $$$O(1)$$$. This solution has the complexity $$$O(n + m)$$$.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> pref(n);
    for (int i = 0; i < n; i++) {
        cin >> pref[i];
        if (i > 0) pref[i] += pref[i - 1];
    }

    int m;
    cin >> m;

    while (m--) {
        long long q;
        cin >> q;

        int ans = lower_bound(pref.begin(), pref.end(), q)
                  - pref.begin();

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

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n);
    long long total = 0;

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

    vector<int> bag(total + 1);

    ll label = 1;
    for (int i = 0; i < n; i++) {
        for (ll j = 0; j < a[i]; j++) {
            bag[label++] = i + 1;
        }
    }

    int m;
    cin >> m;

    while (m--) {
        ll q;
        cin >> q;
        cout << bag[q] << '\n';
    }

    return 0;
}

This problem with small coordinates can be solved using partial sums and some easy counting. Let's carry an array $$$cnt$$$, where $$$cnt_i$$$ will be equal to the number of segments that cover the point with coordinate $$$i$$$. How to calculate $$$cnt$$$ in $$$(O(n+\max X)$$$?

For each segment $$$(l_i,r_i)$$$, let's add $$$+1$$$ to $$$cnt_{l_i}$$$ and $$$-1$$$ to $$$cnt_{r_i+1}$$$. Now build prefix sums on this array and notice that $$$cnt_i$$$ equals the number of segments that cover the point with coordinate $$$i$$$. Then $$$ans_i$$$ will be equal to

All the answers can be calculated in $$$O(\max X)$$$ in total. So the total complexity of this solution is $$$O(n+\max X)$$$.

But in our problem it is too slow to build an entire array $$$cnt$$$. So what should we do? It is obvious that if any coordinate $$$j$$$ is not equal to some $$$l_i$$$ or some $$$r_i+1$$$, then $$$cnt_j=cnt_{j-1}$$$. So we do not need to carry all the positions explicitly. Let's carry all $$$l_i$$$ and $$$r_i+1$$$ in some logarithmic data structure or let's use the coordinate compression method.

The coordinate compression method allows us to transform the set of big sparse objects to the set of small compressed objects while maintaining the relative order. In our problem, let's do the following things: push all $$$l_i$$$ and $$$r_i+1$$$ into vector $$$cval$$$, sort this vector, keep only unique values, and then use the position of elements in vector $$$cval$$$ instead of the original value (any position can be found in $$$O(\log n)$$$ by binary search or standard methods such as lower_bound in C++).

So the first part of the solution works in $$$O(n\log n)$$$. The answer can be calculated using almost the same approach as in the solution to this problem with small coordinates. But now we know that between two adjacent elements $$$cval_i$$$ and $$$cval_{i+1}$$$, there are exactly $$$cval_{i+1}-cval_i$$$ points with answer equal to $$$cnt_i$$$. So if we iterate over all pairs of adjacent elements $$$cval_i$$$ and $$$cval_{i+1}$$$ and add $$$cval_{i+1}-cval_i$$$ to $$$ans_{cnt_i}$$$, we will calculate all the answers in $$$O(n)$$$.

Time complexity: $$$O(n log(n))$$$

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<long long, long long>> segments(n);
    vector<long long> coords;

    for (auto &[l, r] : segments) {
        cin >> l >> r;
        coords.push_back(l);
        coords.push_back(r + 1);
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());

    int k = coords.size();
    vector<int> cnt(k, 0);

    for (auto [l, r] : segments) {
        int left = lower_bound(coords.begin(), coords.end(), l)
                   - coords.begin();
        int right = lower_bound(coords.begin(), coords.end(), r + 1)
                    - coords.begin();

        cnt[left]++;
        cnt[right]--;
    }

    for (int i = 1; i < k; i++)
        cnt[i] += cnt[i - 1];

    vector<long long> ans(n + 1, 0);

    for (int i = 1; i < k; i++)
        ans[cnt[i - 1]] += coords[i] - coords[i - 1];

    for (int i = 1; i <= n; i++)
        cout << ans[i] << (i == n ? '\n' : ' ');

    return 0;
}

Let's look at the first nail. If it is occupied by the fold place, then the Witch will put the next fold place on the third nail, then on the fifth, and so on. Otherwise, if the first nail is occupied by an end of a rod, then the second, fourth, sixth, and so on nails will be occupied by the fold places.

Let's see if we can complete our polyline with the first nail occupied by a fold place. This means we should check whether we have an unused rod with length $$$\operatorname{dist}(\text{nails}[n],\text{nails}[1])+\operatorname{dist}(\text{nails}[1],\text{nails}[2])$$$. Then check the third nail, and so on.

If we can complete the polyline, we have found a valid answer. Otherwise, repeat the previous procedure, but start from the second nail, assuming that the first nail is occupied by an end of a rod instead.

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

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

    vector<long long> x(n), y(n), d(n), r(m);

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    for (int i = 0; i < m; i++)
        cin >> r[i];

    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        d[i] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
    }

    for (int s = 0; s < 2; s++) {
        map<long long, vector<int>> mp;

        for (int i = 0; i < m; i++)
            mp[r[i]].push_back(i + 1);

        vector<int> ans(n, -1);
        bool ok = true;

        for (int i = s; i < n; i += 2) {
            long long need = d[(i - 1 + n) % n] + d[i];

            if (mp[need].empty()) {
                ok = false;
                break;
            }

            ans[i] = mp[need].back();
            mp[need].pop_back();
        }

        if (ok) {
            cout << "YES\n";

            for (int i = 0; i < n; i++)
                cout << ans[i] << " \n"[i == n - 1];

            return 0;
        }
    }

    cout << "NO\n";
    return 0;
}