---

Problem 472

---

Comfortable Distance II

There are N seats in a row. N people come one after another to fill the seats according to the following rules:

1. No person sits beside another.
2. The first person chooses any seat.
3. Each subsequent person chooses the seat furthest from anyone else already seated, as long as it does not violate rule 1. If there is more than one choice satisfying this condition, then the person chooses the leftmost choice.

Note that due to rule 1, some seats will surely be left unoccupied, and the maximum number of people that can be seated is less than N (for N > 1).

Here are the possible seating arrangements for N = 15:

We see that if the first person chooses correctly, the 15 seats can seat up to 7 people.
We can also see that the first person has 9 choices to maximize the number of people that may be seated.

Let f(N) be the number of choices the first person has to maximize the number of occupants for N seats in a row. Thus, f(1) = 1, f(15) = 9, f(20) = 6, and f(500) = 16.

Also, ∑f(N) = 83 for 1 ≤ N ≤ 20 and ∑f(N) = 13343 for 1 ≤ N ≤ 500.

Find ∑f(N) for 1 ≤ N ≤ 10¹². Give the last 8 digits of your answer.

---

舒适距离 II

有一排N个座位，N个人根据下列规则依次坐到座位上：

1. 没有人坐在别人边上。
2. 第一个人可以坐在任意位置。
3. 接下来的每个人在不违背第一条规则的情况下，选择距离已经坐下的人最远的座位。如果有多于一个选择满足这个条件，选择最左边的座位。

注意到由于有第一条规则的存在，有些座位一定会被空着，因此最多能坐下的人数一定比N要小（如果N > 1）。

对于N = 15，下图表示了所有可能的座位安排：

可以看出如果第一个人选对了位置，那15个座位最多可以坐下7个人。
我们也能看出第一个人有9种方式来达到这个最大值。

记f(N)是第一个人使得N个座位能坐下最多的人的方法数，所以f(1) = 1，f(15) = 9，f(20) = 6，f(500) = 16。

同时，对于1 ≤ N ≤ 20，我们有∑f(N) = 83；对于1 ≤ N ≤ 500，我们有∑f(N) = 13343。

对于1 ≤ N ≤ 10¹²，求∑f(N)，并给出其最后八位数字。

---