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
100输入输出样例 #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]);}2023.08.21 更新：修正公式中的一处错误，增加一些补充说明。
