Home » 國際競賽 » Details

USACO 2018 December Contest, Platinum Problem 1. Balance Beam

Category: 國際競賽, 計(jì)算機(jī)國際競賽 Date: 2018年12月20日下午12:53

In order to save money for a new stall in her barn, Bessie the cow has started performing in the local circus, demonstrating her remarkable sense of balance as she carefully walks back and forth on an elevated balance beam!

The amount of money Bessie earns in her performance is related to where she manages to ultimately jump off the beam. The beam has positions labeled? $0, 1, \dots, N + 1$ ?from left to right. If Bessie ever reaches? $0$ ?or? $N + 1$ ?she falls off one of the ends of the beam and sadly gets no payment.

If Bessie is at a given position? $k$ , she can do either of the following:

1. Flip a coin. If she sees tails, she goes to position? $k - 1$ , and if she sees heads, she goes to position? $k + 1$ ?(i.e.? $\frac{1}{2}$ ?probability of either occurrence).

2. Jump off the beam and receive payment of? $f (k)$ ? $(0 \leq f (k) \leq 10^{9})$ .

Bessie realizes that she may not be able to guarantee any particular payment outcome, since her movement is governed by random coin flips. However, based on the location where she starts, she wants to determine what her expected payment will be if she makes an optimal sequence of decisions ("optimal" meaning that the decisions lead to the highest possible expected payment). For example, if her strategy earns her payment of? $10$ ?with probability? $1 / 2$ ,? $8$ ?with probability? $1 / 4$ , or? $0$ ?with probability? $1 / 4$ , then her expected payment will be the weighted average? $10 (1 / 2) + 8 (1 / 4) + 0 (1 / 4) = 7$ .

INPUT FORMAT (file balance.in):

The first line of input contains? $N$ ?( $2 \leq N \leq 10^{5}$ ). Each of the remaining? $N$ ?lines contain? $f (1) \dots f (N)$ .

OUTPUT FORMAT (file balance.out):

Output? $N$ ?lines. On line? $i$ , print out? $10^{5}$ ?times the expected value of payment if Bessie starts at position? $i$ ?and plays optimally, rounded down to the nearest integer.

SAMPLE INPUT:

2
1
3

SAMPLE OUTPUT:

150000
300000

Problem credits: Franklyn Wang and Spencer Compton

USACO 2018 December Contest, Platinum Problem 1. Balance Beam題解(翰林國際教育提供，僅供參考)

凸包。
如果初始在，并且a[L]和a[R]均大于a[i]。
那么必然可以以a[L]或者a[R]結(jié)束。
如果從i出發(fā)，每次向左或向右走，走到或停止，那么
最終停在的概率為(i – L) / (R – L)。
最終停在的概率為(R – i) / (R – L)。
換句話說，設(shè)是停在的概率，顯然有pL = 0, pR = 1
中間的p是一個(gè)等差數(shù)列。

所以說，從i出發(fā)，每次向左或向右走，走到或停止，這個(gè)策略的收益是
換句話說，如果點(diǎn)(i, ai)在從(L, a[L])到(R, a[R])的下面，那么他就可以刪去了，剩下的點(diǎn)恰好是一個(gè)凸包。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n;
double a[100020];
int s[100020], ss;
long long xm(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - x2 * y1;
}
int main() {
    freopen("balance.in", "r", stdin);
    freopen("balance.out", "w", stdout);
    scanf("%d", &n);
    s[ss++] = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (i <= n) {
            scanf("%lf", &a[i]);
        }
        while (ss >= 2 && xm(s[ss - 1] - s[ss - 2], a[s[ss - 1]] - a[s[ss - 2]],
            i - s[ss - 2], a[i] - a[s[ss - 2]]) > 0) {
            ss--;
        }
        s[ss++] = i;
    }
    int t = 0;
    for (int i = 1; i <= n; i++) {
        while (i > s[t]) {
            t++;
        }
        ull res = (ull)a[s[t]] * (i - s[t - 1]) + (ull)a[s[t - 1]] * (s[t] - i);
        res *= 100000;
        res /= s[t] - s[t - 1];
        printf("%llun", res);
    }
    return 0;
}

C++

Copy