洛谷 P1024 [NOIP 2001 提高组] 一元三次方程求解

// P1024 一元三次方程求解 —— 大多数人真实的第一版：把 x 从 -100 扫到 100
//
// 题目把范围直接给了：根在 [-100, 100] 之间。那最直白的想法就是拿个小步长扫过去，
// 谁让 f(x) 差不多等于 0，谁就是根：
//
//     for (double x = -100; x <= 100; x += STEP)
//         if (fabs(f(x)) < EPS) 输出 x;
//
// ⚠ 它有一个**没法调对**的地方：STEP 和 EPS 这两个旋钮是互相拧着的。
//   · EPS 大了：一个根附近连着好几个 x 都「差不多等于 0」，同一个根被输出好几次；
//   · EPS 小了：步子正好跨过根、每一步都不够接近，那个根**一个都输不出来**。
//   而且要多大多小**取决于系数** —— a 很大时 f 很陡，同样的 EPS 就等价于更小的窗口。
//
// ★ 这就是这道题真正要教的事：**「差不多等于 0」不是一个可以判定的条件，
//   「符号变了」才是。** 下一版就换成符号。
//
// 用法：./p1024Enum [step] [eps]      默认 0.001 / 1e-4，可以自己拧两个旋钮试试

#include <bits/stdc++.h>
using namespace std;

static double A, B, C, D;
static double f(double x) { return ((A * x + B) * x + C) * x + D; }

int main(int argc, char** argv) {
    double STEP = (argc > 1) ? atof(argv[1]) : 0.001;
    double EPS  = (argc > 2) ? atof(argv[2]) : 1e-4;
    if (scanf("%lf %lf %lf %lf", &A, &B, &C, &D) != 4) return 0;

    int cnt = 0;
    for (double x = -100; x <= 100.0000001; x += STEP) {
        if (fabs(f(x)) < EPS) { printf("%.2f ", x); cnt++; }
    }
    printf("\n");
    if (cnt != 3) fprintf(stderr, "⚠ 输出了 %d 个「根」，而题目说恰好有 3 个\n", cnt);
    return 0;
}

// P1024 的第一个 WA：改用「符号变了」—— 但漏掉了正好落在整点上的根
//
// 上一版的病根是「fabs(f(x)) < EPS」不可判定。题面自己给了替代品：
//
//     若 f(x1) × f(x2) < 0，则 (x1, x2) 之间一定有一个根。
//
// 又因为题目保证「根与根之差 >= 1」，所以**每个长度为 1 的整数区间里最多一个根** ——
// 于是把 [-100, 100] 切成 200 段，逐段判符号，变号的那一段里二分。这个思路完全正确。
//
// ⚠ 可是它有一个**样例就能打出来**的洞：`f(x1) × f(x2) < 0` 要求两端**严格异号**，
//   而根正好落在整点上时，那一端的 f 就是 **0**，乘积也是 0，`< 0` 不成立 ⇒ **整根被跳过**。
//   样例 `1 -5 -4 20` 的三个根是 -2、2、5，**全是整数** —— 这一版一个都输不出来。
//
// ★ 值得单独记一笔：这个 bug 不需要对拍，**样例自己就是反例**。
//   而它仍然是最常见的第一版 —— 因为「f(x1)×f(x2) < 0」这句话是题面**原文**抄下来的，
//   抄的时候没人会想「那 = 0 呢」。⇒ **题面给的判据是「充分」的，不一定是「完备」的。**

#include <bits/stdc++.h>
using namespace std;

static double A, B, C, D;
static double f(double x) { return ((A * x + B) * x + C) * x + D; }

int main() {
    if (scanf("%lf %lf %lf %lf", &A, &B, &C, &D) != 4) return 0;

    for (int i = -100; i < 100; i++) {
        double l = i, r = i + 1;
        if (f(l) * f(r) < 0) {                  // ⚠ 严格 < 0：整根那一端 f 是 0，进不来
            for (int t = 0; t < 100; t++) {     // 区间长 1，减半 100 次远够 10⁻² 的精度
                double mid = (l + r) / 2;
                if (f(l) * f(mid) <= 0) r = mid;
                else l = mid;
            }
            printf("%.2f ", l);
        }
    }
    printf("\n");
    return 0;
}

// P1024 一元三次方程求解 —— ★ 这一版就已经能 AC 了
//
// 相比上一版只补了一件事：**先单独看一眼整点自己是不是根**。
//
//   for (int i = -100; i <= 100; i++)
//       if (f(i) == 0) 它就是根                 ← 整根走这条路
//       else if (i < 100 && f(i) * f(i+1) < 0)  ← 严格异号才二分
//           在 [i, i+1] 里二分
//
// ⚠ 两个细节，都不是「随手写就对」的：
//   ① 整点判断只看**左端**（i 自己），不去看 i+1 —— 否则 i = 2 那个根会被
//      [1,2] 的右端和 [2,3] 的左端各数一次，输出成两个 2.00。
//   ② `f(i) == 0` 里的 `==` 在浮点上一般是禁忌，但这道题的系数是从题面读进来的实数，
//      整根处算出来的就是精确的 0；稳妥起见这里仍然写成 `fabs(f(i)) < 1e-9`。
//
// ★ 为什么切成「长度 1 的整数区间」就够：题目保证**根与根之差 >= 1**。
//   ⇒ 每段里最多一个根 ⇒ 段内 f 至多变一次号 ⇒ 二分才是合法的。
//   **这个保证是整个解法的前提**，题面里那句不起眼的话才是最关键的条件。
//
// ⚠ 二分的终止条件不能写成 `while (l < r)` —— 浮点数减半永远减不到相等，
//   那是个死循环（p1024Loop.cpp 让它当场死给你看）。这里用**固定次数**：
//   区间长 1，减半 100 次后长度是 2⁻¹⁰⁰，远远超过「精确到小数点后 2 位」的要求。

#include <bits/stdc++.h>
using namespace std;

static double A, B, C, D;
static double f(double x) { return ((A * x + B) * x + C) * x + D; }

int main() {
    if (scanf("%lf %lf %lf %lf", &A, &B, &C, &D) != 4) return 0;

    for (int i = -100; i <= 100; i++) {
        if (fabs(f(i)) < 1e-9) {                        // ① 整点自己就是根
            printf("%.2f ", (double)i);
            continue;
        }
        if (i == 100) break;
        double l = i, r = i + 1;
        if (f(l) * f(r) < 0) {                          // ② 严格异号 ⇒ 段内有且只有一个根
            for (int t = 0; t < 100; t++) {             // ③ 固定次数，不写 while (l < r)
                double mid = (l + r) / 2;
                if (f(l) * f(mid) <= 0) r = mid;
                else l = mid;
            }
            printf("%.2f ", l);
        }
    }
    printf("\n");
    return 0;
}

// ⚠ 故意写错的：实数二分写成 `while (l < r)` —— 亲眼看它停不下来
//
// 第 8 章第 ⑥ 步在**整数**上看过一次死循环（区间缩不动）。实数这边的死法不一样，
// 而且更隐蔽：`l` 和 `r` 是 double，一直取中点，区间长度按 2⁻ᵗ 缩小 ——
// 它**会**越来越小，但**永远不会相等**，于是 `l < r` 永远成立。
//
// ★ 准确地说 —— 这句是实测出来的，不是推出来的：它**一次都停不了**。
//   区间缩到只差 1 个 ULP（最后一位）时，(l + r) / 2 算出来的 mid 会**舍入成端点本身**，
//   于是 `r = mid` 或 `l = mid` 赋的是它原来的值，区间**再也不动**，而 l < r 仍然成立。
//   实测（输入 `1.0 -1.5 -8.5 12.0`，根 -2.89 / 1.39 / 3.00）：
//   [-3, -2] 那一段转了 1000 万次，r − l 一直是 4.441e-16，一步没挪。
//   ⚠ 别拿样例来试这一版 —— 样例的根全是整数，f(端点) = 0 ⇒ 每段都被 continue 掉，
//     `while` 一次都进不去，看起来「没事」。**它是被另一个 bug 挡住了。**
//   ⇒ 它不是「转很久」，是**真的死在那儿**。
//
// ⚠ 这份代码带了一个 1000 万次的上限，跑到上限就打印「转了多少次还没停」然后退出 ——
//   **不是为了好看，是为了它能进 check:viz**：一个不退出的程序会把整条检查挂住
//   （第 4 章 P1731 那次踩过，两分钟不出结果，全量检查一起卡在那儿）。
//
// ⇒ 正确写法是**固定次数**（p1024.cpp 那样转 100 次），或者 `while (r - l > 1e-6)`。

#include <bits/stdc++.h>
using namespace std;

static double A, B, C, D;
static double f(double x) { return ((A * x + B) * x + C) * x + D; }

int main() {
    if (scanf("%lf %lf %lf %lf", &A, &B, &C, &D) != 4) return 0;

    const long long LIMIT = 10000000;               // ⚠ 安全阀，见上面
    for (int i = -100; i < 100; i++) {
        double l = i, r = i + 1;
        if (f(l) * f(r) >= 0) continue;
        long long t = 0;
        while (l < r) {                             // ⚠ 就是这一行
            double mid = (l + r) / 2;
            if (f(l) * f(mid) <= 0) r = mid;
            else l = mid;
            if (++t >= LIMIT) {
                printf("在 [%d, %d] 里转了 %lld 次还没停：l = %.20f，r = %.20f，r - l = %.3e\n",
                       i, i + 1, t, l, r, r - l);
                return 0;
            }
        }
        printf("%.2f ", l);
    }
    printf("\n");
    return 0;
}

// 换一把尺子：二分转几次才够，以及「转 100 次」里有多少次是白转的
//
// 用法：./p1024Count [csv]
//
// ① **要几次才够**：区间长 1，每次减半，t 次之后长 2⁻ᵗ。
//    题目要「精确到小数点后 2 位」⇒ 误差得小于 0.005 ⇒ 2⁻ᵗ < 0.005 ⇒ t >= 8。
//    保险起见常写 100 —— 那么多出来的 92 次买到了什么？
//
// ② ★ **什么都没买到。** double 的尾数只有 52 位：区间缩到大约 2⁻⁵² 之后，
//    (l + r) / 2 算出来的 mid 会直接等于 l 或 r，区间**再也不动了**，
//    循环剩下的每一轮都在原地。这份程序把「第几次之后 l 和 r 不再变化」实测出来。
//
// ⇒ 结论不是「别写 100」（写 100 完全没问题，也不慢），而是：
//   **知道它在第几次就已经停住了** —— 这样才敢在别的题上判断「转多少次够」。

#include <bits/stdc++.h>
using namespace std;

static double A, B, C, D;
static double f(double x) { return ((A * x + B) * x + C) * x + D; }

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");
    A = 1; B = -5; C = -4; D = 20;                  // 就用样例那组：根 -2 / 2 / 5

    /* 拿 [4, 5] 这一段（根是 5，落在右端点）—— 换成任何一段结论都一样 */
    double l = 4, r = 5;
    int firstStable = -1, needFor2dp = -1;
    double prevL = l, prevR = r;
    for (int t = 1; t <= 200; t++) {
        double mid = (l + r) / 2;
        if (f(l) * f(mid) <= 0) r = mid; else l = mid;
        if (needFor2dp < 0 && (r - l) < 0.005) needFor2dp = t;
        if (firstStable < 0 && l == prevL && r == prevR) firstStable = t;
        prevL = l; prevR = r;
    }
    int wasted = 100 - firstStable;

    if (csv) {
        printf("needFor2dp,%d\nfirstStable,%d\nwastedOf100,%d\n", needFor2dp, firstStable, wasted);
        printf("finalGap,%.3e\n", r - l);
        return 0;
    }
    printf("区间长 1，每次减半：\n\n");
    printf("  要「精确到小数点后 2 位」（误差 < 0.005）  第 %d 次就够了\n", needFor2dp);
    printf("  区间再也缩不动（mid 已经等于端点）        第 %d 次\n", firstStable);
    printf("  ⇒ 常写的「转 100 次」里，后 %d 次一步都没动。\n", wasted);
    printf("\n  转完 200 次的区间长度：%.3e（不是 0，是 double 的分辨率到头了）\n", r - l);
    return 0;
}

// ★ 验算：走一条和二分**完全无关**的路 —— 三角函数版求根公式
//
// 第 7 章 P1147 学到的：验算最好别用同一套思路的另一种写法，
// 那样两边会一起错。这里干脆用**数学公式**把三个根直接算出来，
// 和「切区间 + 二分」没有一个字是共用的。
//
// 三次方程 a x³ + b x² + c x + d = 0，先消去二次项（令 x = t − b/(3a)）：
//     t³ + p t + q = 0，   p = (3ac − b²) / (3a²)，  q = (2b³ − 9abc + 27a²d) / (27a³)
// 判别式 Δ = (q/2)² + (p/3)³ < 0 时**恰好有三个不同实根**（正是本题的情形），
// 这时不能用卡尔达诺的立方根（会掉进复数），要用三角形式：
//     t_k = 2√(−p/3) · cos( θ/3 − 2πk/3 )，  θ = arccos( (3q)/(2p) · √(−3/p) )，k = 0,1,2
//
// ⚠ 这一版**不是**用来交题的（考场上没人现推这个），它只干一件事：
//   给对拍当参照物。⇒ 两条路算出来的三个根必须逐字节相同。

#include <bits/stdc++.h>
using namespace std;

int main() {
    double a, b, c, d;
    if (scanf("%lf %lf %lf %lf", &a, &b, &c, &d) != 4) return 0;

    double p = (3 * a * c - b * b) / (3 * a * a);
    double q = (2 * b * b * b - 9 * a * b * c + 27 * a * a * d) / (27 * a * a * a);
    double shift = -b / (3 * a);

    double t = (3 * q) / (2 * p) * sqrt(-3 / p);
    t = max(-1.0, min(1.0, t));                     // 浮点误差可能让它擦出 [-1,1]
    double th = acos(t);
    double r = 2 * sqrt(-p / 3);

    double x[3];
    for (int k = 0; k < 3; k++) x[k] = r * cos(th / 3 - 2 * M_PI * k / 3) + shift;
    sort(x, x + 3);
    /* ⚠ 这一句不是装饰：根恰好是 0 时公式算出来是 −1×10⁻¹⁷ 那样的数，
       而 printf("%.2f") 会**保留符号**，打成 `-0.00` —— 评测机按文本比，当场 WA。
       200 组对拍里有 3 组栽在这儿（而且栽的是这份「参照物」，不是被测的那版）。
       ★ p1024.cpp 反而躲过了：整根走的是「直接输出 (double)i」那条路，没有负零。 */
    for (int k = 0; k < 3; k++) if (fabs(x[k]) < 1e-9) x[k] = 0;
    printf("%.2f %.2f %.2f \n", x[0], x[1], x[2]);
    return 0;
}

// 数据生成器（P1024 对拍用）：`./p1024Gen <seed> [level]`
//
// ★ 这道题的生成器不能「随机四个系数」—— 随机系数的三次方程多半只有一个实根，
//   而题目**保证有三个不同实根、且两两相差 >= 1**。造出不满足前提的数据，
//   两个程序会一致地输出垃圾，看着全绿其实什么都没验
//   （第 5 章 P1618 那条：**先把「有答案」造出来**）。
//
// ⇒ 所以反着造：**先挑三个根，再把系数乘出来**。
//     a(x − x₁)(x − x₂)(x − x₃) = a x³ − a(x₁+x₂+x₃) x² + a(x₁x₂+x₁x₃+x₂x₃) x − a x₁x₂x₃
//
//   level 0（默认）**整数根**：x_i 取整数 ⇒ 专抓 p1024Sign（f(端点) = 0，严格异号判不出来）
//   level 1        **非整数根**：x_i 取到 0.5 ⇒ 三个根都落在区间内部，
//                  Sign 那一版在这一档上**完全正确** —— 它的盲区对照
//   level 2        ★ **网格外的根**：x_i 取到 1/3 ⇒ 专抓 p1024Enum（扫描版）。
//                  0 和 1 两档的根都是 0.001 的整数倍，**正好落在扫描点上**，
//                  于是 |f(x)| 在那儿精确等于 0，扫描版怎么调都对 ——
//                  这不是它对，是**数据替它对的**。1/3 不是 0.001 的整数倍，
//                  扫描点永远差那么一点，它才现原形。
//
// ⚠ 两个档位互为盲区（第 7 章 P1638 / P1873 那条的又一次复现）。
// ⚠ 系数必须用 %.3f 打印，不能是 %.1f —— 根取到 .5 时，
//   c 是 0.25 的倍数、d 是 **0.125** 的倍数，一位小数会把它们四舍五入掉，
//   造出来的方程根就不再是挑好的那三个了（这个错不报警，只是让对拍验了别的题）。
// ⚠ level 2 的 1/3 本来就不是有限小数，%.6f 之后方程的根会**离 k+1/3 差一点点** ——
//   这不要紧：对拍比的是「两个程序读同一份系数算出来的根」，参照物是 p1024Formula，
//   它读的是同一行。这一档要的只是「根不落在 0.001 的网格上」，这一点 %.6f 完全守得住。
//
// ⚠ a 也随机取正负（包括负数），因为 a < 0 时 f 的走向整个翻过来 ——
//   「符号变了就有根」对 a 的正负是不敏感的，但值得让对拍替我们确认这件事。

#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);

    /* 三个根：先在 [-20, 20] 上挑三个两两相差 >= 1 的（level 1 再各加 0.5） */
    double x[3];
    while (true) {
        int v[3] = { ri(-20, 20), ri(-20, 20), ri(-20, 20) };
        sort(v, v + 3);
        if (v[1] - v[0] >= 1 && v[2] - v[1] >= 1) {
            double off = (level == 1) ? 0.5 : (level == 2 ? 1.0 / 3.0 : 0.0);
            for (int i = 0; i < 3; i++) x[i] = v[i] + off;
            break;
        }
    }
    double a = ri(1, 3) * (ri(0, 1) ? 1 : -1);
    double b = -a * (x[0] + x[1] + x[2]);
    double c =  a * (x[0] * x[1] + x[0] * x[2] + x[1] * x[2]);
    double d = -a * x[0] * x[1] * x[2];

    printf("%.6f %.6f %.6f %.6f\n", a, b, c, d);
    return 0;
}