PE472

#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

int f(int n) {
    bool *seats = new bool[n];
    int bestOutcome = 0;
    int bestCount = 0;

    for (int i=0;i<n;i++) {
        memset(seats,0,n);

        seats[i] = true;
        int seated = 1;
        while (1) {
            int bestDistance = 0;
            int bestSeat = -1;
            for (int p=n-1;p>=0;p--) {
                if (seats[p]) continue;
                if (p > 0 && seats[p-1]) continue;
                if (p < n-1 && seats[p+1]) continue;

                int distance = n+1;
                for (int q=0;q<n;q++) {
                    if (seats[q]) distance = min(distance,abs(q-p));
                }

                if (distance >= bestDistance) {
                    bestDistance = distance;
                    bestSeat = p;
                }

            }
            if (!bestDistance) break;

            seated++;
            seats[bestSeat] = true;
        }

        if (seated > bestOutcome) {
            bestOutcome = seated;
            bestCount = 1;
        } else if (seated == bestOutcome) {
            bestCount++;
        }
    }

    delete[] seats;
    return bestCount;
}

int main() {
    for (int n=1;n<1000;n++) printf("f(%d) = %d\n",n,f(n));
}