当前位置：首页 > news >正文

AT_abc026_d 高橋君ボール1号题解

news 2026/5/11 12:05:15

AT_abc026_d [ABC026D] 高橋君ボール1号

Link:
https://www.luogu.com.cn/problem/AT_abc026_d
https://atcoder.jp/contests/abc026/tasks/abc026_d

题目描述

高桥君擅长打棒球。他能够投出一种名为“高桥君球 1 号”的变化球。

这种球在投出后t tt秒的位置可以表示为f ( t ) = A × t + B × sin ⁡ ( C × t × π ) f(t) = A \times t + B \times \sin(C \times t \times \pi)f(t)=A×t+B×sin(C×t×π)。

你需要在t ≥ 0 t \geq 0t≥0且f ( t ) = 100 f(t) = 100f(t)=100的时刻击打这个球。请你求出此时的t tt。

输入格式

输入通过标准输入按以下格式给出。

A AAB BBC CC

第1 11行给出表示f ( t ) f(t)f(t)公式的整数A , B , C A, B, CA,B,C，用空格分隔。( 1 ≤ A , B , C ≤ 100 ) (1 \leq A, B, C \leq 100)(1≤A,B,C≤100)。

输出格式

请输出一个满足f ( t ) = 100 f(t) = 100f(t)=100且t ≥ 0 t \geq 0t≥0的t tt。如果有多个解，输出任意一个即可。只要∣ f ( t ) − 100 ∣ ≤ 10 − 6 |f(t) - 100| \leq 10^{-6}∣f(t)−100∣≤10−6，就视为正确答案。

输出末尾需换行。

由于本题容易产生误差，请特别注意精度问题。

输入输出样例 #1

输入 #1

1 1 1

输出 #1

输入输出样例 #2

输入 #2

53 82 49

输出 #2

1.63372043395339

说明/提示

样例解释 1

当t = 100 t = 100t=100时，f ( t ) = 100 f(t) = 100f(t)=100。

样例解释 2

请注意，解可能不唯一。

由 ChatGPT 4.1 翻译

Solution

大致题意

求解方程A x + B sin ⁡ ( C π x ) − 100 = 0 Ax+B\sin(C\pi x)-100=0Ax+Bsin(Cπx)−100=0的近似解。

解答

本题的方程对应的函数f ( x ) = A x + B sin ⁡ ( C π x ) − 100 f(x)=Ax+B\sin(Cπx)-100f(x)=Ax+Bsin(Cπx)−100并不是一个严格的单调函数，因此二分法不一定能立刻想到。除了二分法以外，本题可以使用牛顿法求解。

由于f ( x ) = A x + B sin ⁡ ( C π x ) − 100 f(x)=Ax+B\sin(Cπx)-100f(x)=Ax+Bsin(Cπx)−100

则导函数f ′ ( x ) = A + B C π cos ⁡ ( C π x ) f'(x)=A+BC\pi \cos(C\pi x)f′(x)=A+BCπcos(Cπx)

根据牛顿法的近似公式x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_{n})}xn+1=xn−f′(xn)f(xn)即可将这个问题直接转化为一个递推问题，当相邻两项的差值小于给定的精度时即可结束递推输出答案。本题由于已经规定了A , B , C A,B,CA,B,C皆为[ 1 , 100 ] [1,100][1,100]范围内的整数，因此初始值x 0 x_0x0也就是代码中的sln[0]，可以选择从100 A \dfrac{100}{A}A100开始。

需要说明的是：

牛顿法通常比二分法收敛更快，适用于不具有单调性的场合，但是前提是所求的表达式必须在指定的区间上可导。
牛顿法的局限性在于只能求出方程某一个特定的近似解（如果方程有多解）。换用不同的初始值，得到的近似解也可能不同。本题要求对于可能的多解输出任意一个解即可，因此牛顿法可以通过此题。
如果使用long double类型来存储答案，计算乘幂、三角函数和对数等需要使用函数powl，sinl，cosl，log10l等来进行计算，输入/输出需要使用格式字符串"%Lf"。

AC 代码

#include<cmath>#include<iostream>usingnamespacestd;longdoubleA,B,C,pi=3.1415926535897932385L,eps=1e-13L;longdoublesln[10000];//The function.longdoubleF(longdoublex){returnA*x+B*sinl(C*pi*x)-100.L;}//The derivate function of F.longdoublederivateF(longdoublex){returnA+B*C*pi*cosl(C*pi*x);}intmain(){cin>>A>>B>>C;intr=0;sln[0]=100.L/A;while(r<=9998){sln[r+1]=sln[r]-1.0L*F(sln[r])/derivateF(sln[r]);if(fabs(sln[r+1]-sln[r])<=eps)break;r+=1;}printf("%.14Lf",sln[r]);}