列表

详情

NC24826. [USACO 2009 Feb B]Cruel Math Teacher, II

描述

As if powers of numbers were not cruel enough, Bessie's cruel math teacher has created yet another cruel assignment: Find the 'root' or 'zero' of a polynomial. All of these polynomials have a highest degree D (1 <= D <= 11) that is odd and have but a single solution in the range -1,000,000 <= X <= 1,000,000; for that solution, the polynomial's value when evaluated for X is very close or equal to to 0 in computer math.
Given a polynomial with real number coefficients (-500 <= coef_i <= 500), find a value of X that is within 0.0005 of the value of X that will yield 0 when the polynomial is evaluated. Multiply that value of X by 1,000 and print it as an (unrounded) integer. 
By way of example, consider the cubic polynomial problem 1.5*x*x*x - 10 = 0.  Astute algebra students will quickly recognize a solution for this as x*x*x = 100/15 = 20/3 = 6.66666. To five decimal places, the exactly solution is 1.88207. For this task, the proper output would be 1882. The polynomial is expressed as the sum from i=0..D of coef_i*x^i (where x^i means x to the i-th power). No answer will require more than six significant digits and each answer will be small enough that it is able to be incremented by 0.0001 in the 'double' precision floating point datatype without losing lots of precision. HINT: Find a strategy to narrow the search space each time you choose a new X value as a guess.

输入描述

* Line 1: A single integer: D
* Lines 2..D+2: Line i+2 contains a single real number: coef_i

输出描述

* Line 1: A single integer that is the truncated product of 1,000 and the X value that is closest to the X value that causes the polynomial to evaluate to 0

示例1

输入: 

3
-10.0
0.0
0.0
1.50

输出: 

1882

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 628K, 提交时间: 2019-09-15 20:17:10 

#pragma GCC target("popcnt")
#pragma GCC optimize("Ofast,inline")
#pragma comment(linker,"/STACK:1024000000,1024000000")
#undef __STRICT_ANSI__
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <cfloat>
#include <complex>
#include <climits>
#include <new>
#include <memory>
#include <cerrno>
#include <cassert>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <utility>
#include <iterator>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cstddef>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <streambuf>
#include <cfenv>
#include <tuple>
#include <cstdint>
#include <random>
#include <regex>
#define lc c[0]
#define rc c[1]
#define fir first
#define sec second
#define lson x<<1
#define rson x<<1|1
#define PB push_back
#define PF push_front
#define MP make_pair
#define MT make_tuple
#define EB emplace_back
#define EF emplace_front
#define Lson l,m,lson
#define Rson m+1,r,rson
#define LB lower_bound
#define UB upper_bound
#define npos string::npos
#define FF fflush(stdout)
#define PQ priority_queue
#define rint register int
#define LSON L,m,l,m,lson
#define RSON m+1,R,m+1,r,rson
#define sqr(X) ((X)*(X))
#define cbr(X) ((X)*(X)*(X))
#define LBT(X) ((X)&(-(X)))
#define SZ(X) (int)(X).size()
#define ALL(X) (X).begin(),(X).end()
#define INS(X) inserter((X),(X).begin())
#define POS(X,Y,Z) LB((X),(Y),(Z))-(X)+1
#define CPY(X,Y) memcpy((X),(Y),sizeof((Y)))
#define MEM(X,Y) memset((X),(Y),sizeof((X)))
#define SC(X) while(scanf("%s",(X)),!strlen((X)))
#define NUM(X,Y,L,R) UB((X),(Y),(R))-LB((X),(Y),(L))
#define SU(X,Y,Z) sort((X),(Y)),(Z)=unique((X),(Y))-(X)
#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
#define NNF 0xc0c0c0c0
#define INF64 0x3f3f3f3f3f3f3f3fLL
#define NNF64 0xc0c0c0c0c0c0c0c0LL
#define PH 0.75
#define P 131
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<int,int> PII;
typedef pair<char,int> PCI;
typedef pair<int,char> PIC;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;
typedef pair<double,int> PDI;
typedef pair<double,double> PDD;
typedef pair<string,string> PSS;
typedef tuple<LL,LL,LL> PLLL;
typedef tuple<LL,LL,int> PLLI;
typedef tuple<int,LL,LL> PILL;
typedef tuple<LL,int,int> PLII;
typedef tuple<int,int,LL> PIIL;
typedef tuple<int,int,int> PIII;
typedef tuple<LL,LL,LL,LL> PLLLL;
typedef tuple<int,int,int,int> PIIII;
typedef tuple<double,double,int> PDDI;
typedef tuple<double,double,double> PDDD;
typedef tuple<double,double,double,int> PDDDI;
typedef set<LL> SL;
typedef set<int> SI;
typedef set<PII> SPII;
typedef set<PIL> SPIL;
typedef set<PLI> SPLI;
typedef set<PLL> SPLL;
typedef set<PIII> SPIII;
typedef set<PLLL> SPLLL;
typedef set<string> SS;
typedef queue<LL> QL;
typedef queue<int> QI;
typedef queue<PII> QPII;
typedef queue<PIL> QPIL;
typedef queue<PLI> QPLI;
typedef queue<PLL> QPLL;
typedef deque<LL> DL;
typedef deque<int> DI;
typedef deque<PII> DPII;
typedef deque<PIL> DPIL;
typedef deque<PLI> DPLI;
typedef deque<PLL> DPLL;
typedef complex<LL> CL;
typedef complex<int> CI;
typedef complex<double> CD;
typedef map<LL,LL> MLL;
typedef map<int,LL> MIL;
typedef map<LL,int> MLI;
typedef map<int,int> MII;
typedef map<PII,int> MPIII;
typedef map<PLL,int> MPLLI;
typedef map<string,int> MSI;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<PII> VPII;
typedef vector<PIL> VPIL;
typedef vector<PLI> VPLI;
typedef vector<PLL> VPLL;
typedef vector<PIC> VPIC;
typedef vector<PCI> VPCI;
typedef vector<string> VS;
typedef vector<PIII> VPIII;
typedef vector<PIIL> VPIIL;
typedef vector<PILL> VPILL;
typedef vector<PLLL> VPLLL;
typedef vector<PLII> VPLII;
typedef vector<PLLI> VPLLI;
typedef vector<PIIII> VPIIII;
typedef vector<PLLLL> VPLLLL;
template<typename T> T gcd(T x,T y) {return y?gcd(y,x%y):x;}
template<typename T> T lcm(T x,T y) {return x/gcd(x,y)*y;}
template<typename T> void adm(T &x,T y,T z) {x=x+y;if(x>=z)x=x-z;}
template<typename T> void adj(T &x,T y) {if(x>=y||x<=-y)x=x%y;if(x<0)x=x+y;}
template<typename T> T qpow(T x,LL y,T z) {for(;y;y>>=1,x=x*x)if(y&1)z=z*x;return z;}
template<typename T> T mpow(LL w,T x,LL y,T z) {for(;y;y>>=1,x=x*x,x=x%w)if(y&1)z=z*x,z=z%w;return z;}
template<typename T> T exgcd(T a,T b,T &x,T &y) {T t=a;b?(t=exgcd(b,a%b,y,x),y=y-(a/b)*x):(x=1,y=0);return t;}
const double EPS = 1e-7;
const LL MOD = 5000011LL;
const int M = 700005;
const int N = 15;
int n;
double a[N],ans;

double judge(double m)
{
    double res=0.0;
    for (int i=0;i<=n;i++) res+=a[i]*pow(m,i);
    return res;
}

double bs(double l,double r)
{
    while (r-l>=EPS)
    {
        double m=(l+r)/2.0;
        if (judge(m)*judge(r)<0.0) l=m; else r=m;
    }
    return l;
}

int main()
{
    scanf("%d",&n);
    for (int i=0;i<=n;i++) scanf("%lf",&a[i]);
    ans=1000.0*bs(-1000000.0,1000000.0);
    printf("%d\n",(int)ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 496K, 提交时间: 2020-02-15 16:43:32 

#include<bits/stdc++.h>
#define db double
using namespace std;
const db eps=1e-4;
int n;
db A[15];
int sgn(db x)
{
	if(x>0)return 1;
	if(x<0)return -1;
	return 0;
}
db GetF(db x)
{
	db t=1,res=0;
	for(int i=0;i<=n;i++,t*=x) res+=t*A[i];
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<=n;i++) scanf("%lf",&A[i]);
	db l=-1e6,r=1e6,mid=(l+r)/2;
	while(fabs(GetF(mid))>eps)
	{
		if(sgn(GetF(mid))==sgn(GetF(r))) r=mid,mid=(l+r)/2;
		else l=mid,mid=(l+r)/2;
	}
	printf("%d\n",(int)(mid*1000.0));
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 27ms, 内存消耗: 3424K, 提交时间: 2019-09-16 09:18:58 

def eval(coefs, x):
  ans = 0
  for c in coefs[::-1]:
    ans = ans * x + c
  return ans

def round(x):
  return int(x)

def main():
  D = int(input())
  coefs = []
  for _ in range(D + 1):
    coefs.append(float(input()))
  eps = 1E-6
  lo = -1000000.0
  hi = 1000000.0
  while hi - lo > eps:
    mi = (lo + hi) * 0.5
    if eval(coefs, mi) * eval(coefs, lo) > 0:
      lo = mi
    else:
      hi = mi
  print(round(lo * 1000.0))

main()

Python(2.7.3) 解法, 执行用时: 16ms, 内存消耗: 3056K, 提交时间: 2019-09-14 15:04:38 

# -*- coding: utf-8 -*-
eps = 1e-6
d = int(input())
a = [float(input()) for i in range(d + 1)][::-1]
l, r = -1e6, 1e6
def f(x) :
  ans = 0.
  for i in a : ans = ans * x + i
  return ans
if f(l) < -eps :
  for i in range(len(a)) : a[i] = -a[i]
while l + eps < r :
  mid = (l + r) / 2.
  if f(mid) > eps : l = mid
  else : r = mid
print int(l * 1000)

上一题

© 2024 nowcoder.com