Kazakhstan FAIO 2024 · Correction IOAI Training

C. Flight Speed

Cette page donne toute la méthode. Lisez-la une fois que vous avez cherché.

Métrique: exact answer on hidden tests
Évaluée sur: self-generated tests (official tests are hidden)
Notre score: sample exact, 10000 checks
Niveau attendu: sample output 244.65116

Niveau attendu atteint

Nous avons résolu l'épreuve nous-mêmes : téléchargé les données, mené les expériences et mesuré le score ci-dessous. L'énoncé et les données appartiennent à leurs organisateurs. Cette correction est rédigée en anglais.

The problem in brief

A rocket's distance from Earth after $x$ hours follows a parabola, $y = a x^2 + b x + c$ kilometres, with the three coefficients given. The program must print the rocket's speed exactly $d$ hours after launch. "Speed at an instant" is the derivative of distance with respect to time, so the task is a one-line application of calculus. It is also a gentle first meeting with the object that drives all of deep learning: the derivative.

How you are scored

Hidden tests compare your printed number with the exact speed (the statement does not give the tolerance; printing enough decimals is the safe choice). On the sample, $a = 10$ , $b = 4.65116$ , $c = 7.178$ , $d = 12$ , the expected output is $244.65116$ , which our program reproduces exactly.

The key idea

Instantaneous speed is the limit of average speeds over shorter and shorter intervals. Between times $d$ and $d + h$ , the rocket covers $y(d+h) - y(d)$ kilometres, so its average speed is

\frac{y(d+h) - y(d)}{h} = \frac{a(d+h)^2 + b(d+h) + c - a d^2 - b d - c}{h} = \frac{2adh + a h^2 + b h}{h} = 2ad + b + a h .

As $h \to 0$ the extra term $a h$ vanishes, leaving

y'(d) = 2ad + b .

Geometrically this is the slope of the tangent line to the parabola at $x = d$ . Note that $c$ , the starting distance, disappears: shifting the whole curve up does not change how fast it rises.

Left: secants over 6 and 3 hours are steeper than the tangent at d = 12, whose slope 244.65 km/h is the speed. Right: the average speed over [d, d + h] equals 2ad + b + ah and converges to 244.65116 as h shrinks.

Sample check: $2 \times 10 \times 12 + 4.65116 = 244.65116$ .

The full solution

a, b, c, d = map(float, sys.stdin.read().split()[:4])
v = 2 * a * d + b
print(f"{v:.10f}".rstrip("0").rstrip("."))

Reading all tokens with split() works whether the four numbers come on separate lines (as the statement says) or on one line (as the sample shows). Formatting with ten decimals then stripping trailing zeros prints 244.65116 instead of a float artefact such as 244.65115999999998.

solution.py --check compares the formula with a numerical derivative $\frac{y(d+h) - y(d-h)}{2h}$ on 10 000 random inputs in the allowed range.

Results

approach	sample	general
exact derivative $2ad + b$	244.65116	correct
average speed from launch, $y(d)/d$	125.25	wrong: average, not instantaneous
average speed $(y(d) - c)/d = ad + b$	124.65	wrong: off by $ad$
one-sided difference with $h = 1$	254.65	wrong: error $a h$
central difference with small $h$	244.65116	correct up to rounding

What to remember

Speed is the derivative of position: the limit of $\frac{y(d+h) - y(d)}{h}$ , the slope of the tangent.
Derivative of a polynomial: $\frac{d}{dx}(a x^2 + b x + c) = 2ax + b$ ; constants vanish.
A central difference $\frac{y(d+h) - y(d-h)}{2h}$ is a cheap, accurate check of any derivative you compute by hand. Deep-learning practitioners use exactly this "gradient check" to test backpropagation code.
Read inputs token by token, not line by line, when the statement and the sample disagree on layout.

Code complet (solution.py)

"""FAIO 2024 (Kazakhstan) qualification, problem C "Flight Speed".

Distance y(x) = a x^2 + b x + c (x in hours). Speed at time d = y'(d) = 2 a d + b.

    printf "10\n4.65116\n7.178\n12\n" | python solution.py   -> 244.65116
    python solution.py --check                                -> checks + figure
"""
import sys


def speed(a, b, c, d):
    return 2 * a * d + b                # derivative of a x^2 + b x + c at x = d


def fmt(v):
    s = f"{v:.10f}".rstrip("0").rstrip(".")
    return s if s not in ("", "-0") else "0"


def check():
    import random
    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt

    assert fmt(speed(10, 4.65116, 7.178, 12)) == "244.65116"
    y = lambda a, b, c, x: a * x * x + b * x + c
    for _ in range(10000):              # compare with a symmetric finite difference
        a, b, c, d = (random.uniform(0.001, 999.999) for _ in range(4))
        h = 1e-4 * max(1.0, d)
        num = (y(a, b, c, d + h) - y(a, b, c, d - h)) / (2 * h)
        assert abs(num - speed(a, b, c, d)) <= 1e-6 * max(1.0, abs(num))
    print("sample OK, 10000 finite-difference checks OK")

    # figure: average speed over [d, d + h] -> instantaneous speed as h -> 0
    plt.rcParams.update({"font.size": 12, "axes.spines.top": False, "axes.spines.right": False})
    a, b, c, d = 10, 4.65116, 7.178, 12
    xs = [i / 20 for i in range(0, 361)]
    fig, axs = plt.subplots(1, 2, figsize=(12, 4.4), dpi=150)
    axs[0].plot(xs, [y(a, b, c, x) for x in xs], color="#2e86ab", lw=2.5, label="y = a x^2 + b x + c")
    for h, col in [(6, "#c9a227"), (3, "#8d5a97")]:
        s = (y(a, b, c, d + h) - y(a, b, c, d)) / h
        axs[0].plot([d - 4, d + h + 1], [y(a, b, c, d) + s * (t - d) for t in (d - 4, d + h + 1)],
                    "--", color=col, lw=1.8, label=f"secant, h = {h}: {s:.1f} km/h")
    s = speed(a, b, c, d)
    axs[0].plot([d - 4, d + 7], [y(a, b, c, d) + s * (t - d) for t in (d - 4, d + 7)],
                color="#d1495b", lw=2.2, label=f"tangent at d = 12: {s:.2f} km/h")
    axs[0].scatter([d], [y(a, b, c, d)], color="black", zorder=5)
    axs[0].set_xlim(4, 18); axs[0].set_ylim(0, 3500)
    axs[0].set_xlabel("time x (hours)"); axs[0].set_ylabel("distance y (km)")
    axs[0].set_title("Speed = slope of the tangent"); axs[0].legend(frameon=False, fontsize=10)
    hs = [10 ** (-k / 4) for k in range(0, 21)]
    axs[1].semilogx(hs, [(y(a, b, c, d + h) - y(a, b, c, d)) / h for h in hs], "o-", color="#3a7d44",
                    label="(y(d + h) - y(d)) / h  =  2ad + b + a h")
    axs[1].axhline(s, color="#d1495b", ls="--", label="2ad + b = 244.65116")
    axs[1].invert_xaxis(); axs[1].set_xlabel("h (hours), shrinking to the right")
    axs[1].set_ylabel("average speed (km/h)")
    axs[1].set_title("Average speed tends to 2ad + b"); axs[1].legend(frameon=False, fontsize=10)
    fig.tight_layout(); fig.savefig("figures/tangent.png", facecolor="white")


if __name__ == "__main__":
    if "--check" in sys.argv:
        check()
    else:
        a, b, c, d = map(float, sys.stdin.read().split()[:4])
        print(fmt(speed(a, b, c, d)))