Ingenuity

This is a list of problems with deceptively simple solutions, all that I might’ve either completely missed or arrived at via a contrived way losing the essence and intuition of it. This is like those argumentative proofs in combinatorics.

There are $N$ food items in a row, each either fast food (+0 energy) or good food (+1 energy). For each $k=1...N$, consume the first $k$ food; after that you can spend 1 energy to get the next food item. Find the total number of items you can eat before running out of energy.

https://atcoder.jp/contests/abc469/tasks/abc469_c

Try to think in terms of deltas. Every good food will pay for a fast food later. Define $X(k)$ = count of fast food in prefix $k$, the number of good foods in that prefix is then $k-X(k)$, each good food can pay for ONE bad food after $k$, so you want the ${k-X(k)}_{t}h$ bad food after that ( or the end ). So in the prefix, there are $X(k)$ fast foods we’ve eaten, we want the $k-X(k)$ NEXT one from there, so effectively we want the $k_{t}h$ fast food item, for each k.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  string s;
  cin >> n >> s;
 
  vector<int> pos;
  for (int i = 0; i < n; i++)
    if (s[i] == 'x')
      pos.push_back(i + 1);
 
  for (int i = 1; i <= n; i++) {
    cout << (i <= (int)pos.size() ? pos[i - 1] : n) << "\n";
  }
}