http://iceja.net/ сервер решения полиномов

// validator.c - ULTRA-FAST with hash table and CORRECT degree calculation
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
 
#define MAX_DEGREE 30
#define MAX_LINE 65536
#define MAX_ROOTS 100
#define TOLERANCE 1e-3
#define PROGRESS_INTERVAL 10000
#define MAX_POLYS 2000000
#define HASH_SIZE 2097152
 
typedef struct {
    int id;
    double coeffs[MAX_DEGREE + 1];
    int degree;  // actual degree (count - 1)
    int coeff_count;  // number of coefficients
} InputPoly;
 
typedef struct {
    int id;
    int root_count;
    double roots_left[MAX_ROOTS];
    double roots_right[MAX_ROOTS];
} OutputPoly;
 
typedef struct HashNode {
    int id;
    int index;
    struct HashNode *next;
} HashNode;
 
HashNode *hash_table[HASH_SIZE] = {NULL};
 
int hash_function(int id) {
    return ((unsigned int)id * 2654435761u) % HASH_SIZE;
}
 
void hash_insert(int id, int index) {
    int slot = hash_function(id);
    HashNode *node = malloc(sizeof(HashNode));
    node->id = id;
    node->index = index;
    node->next = hash_table[slot];
    hash_table[slot] = node;
}
 
int hash_lookup(int id) {
    int slot = hash_function(id);
    HashNode *node = hash_table[slot];
    while (node != NULL) {
        if (node->id == id) return node->index;
        node = node->next;
    }
    return -1;
}
 
void hash_free() {
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode *node = hash_table[i];
        while (node != NULL) {
            HashNode *next = node->next;
            free(node);
            node = next;
        }
        hash_table[i] = NULL;
    }
}
 
double eval_poly(double *coeffs, int count, double x) {
    double result = coeffs[0];
    for (int i = 1; i < count; i++) {
        result = result * x + coeffs[i];
    }
    return result;
}
 
int parse_line_with_id(const char *line, int *id, double *coeffs) {
    const char *p = line;
    while (isspace(*p)) p++;
 
    if (strncmp(p, "ID=", 3) == 0) {
        p += 3;
        char *endptr;
        *id = (int)strtol(p, &endptr, 10);
        if (p == endptr) {
            *id = -1;
            return 0;
        }
        p = endptr;
    } else {
        *id = -1;
        return 0;
    }
 
    int count = 0;
    while (*p && count <= MAX_DEGREE) {
        while (isspace(*p)) p++;
        if (!*p || *p == '\n') break;
 
        char *endptr;
        coeffs[count] = strtod(p, &endptr);
        if (p == endptr) break;
        count++;
        p = endptr;
    }
 
    return count;
}
 
int parse_output_line(const char *line, int *id, int *root_count,
                      double *roots_left, double *roots_right) {
    const char *p = line;
    while (isspace(*p)) p++;
 
    if (strncmp(p, "ID=", 3) == 0) {
        p += 3;
        char *endptr;
        *id = (int)strtol(p, &endptr, 10);
        if (p == endptr) {
            *id = -1;
            return -1;
        }
        p = endptr;
    } else {
        *id = -1;
        return -1;
    }
 
    while (isspace(*p)) p++;
 
    char *endptr;
    *root_count = (int)strtol(p, &endptr, 10);
    if (p == endptr) return -1;
    p = endptr;
 
    int parsed = 0;
    for (int i = 0; i < *root_count && i < MAX_ROOTS; i++) {
        while (isspace(*p)) p++;
        if (!*p) break;
 
        roots_left[i] = strtod(p, &endptr);
        if (p == endptr) break;
        p = endptr;
 
        while (isspace(*p)) p++;
        roots_right[i] = strtod(p, &endptr);
        if (p == endptr) break;
        p = endptr;
 
        parsed++;
    }
 
    if (parsed != *root_count) {
        fprintf(stderr, "ID=%d claims %d roots but only %d pairs found in line\n",
                *id, *root_count, parsed);
        return -1;
    }
 
    return parsed;
}
 
void print_progress(int current, int total, double elapsed) {
    if (total == 0) return;
    int percent = (int)(100.0 * current / total);
    double rate = current / elapsed;
    double eta = (total - current) / rate;
    printf("\rProgress: %d/%d (%d%%) | %.2f poly/sec | ETA: %.1fs",
           current, total, percent, rate, eta);
    fflush(stdout);
}
 
int main(int argc, char **argv) {
    const char *input_path = (argc >= 2) ? argv[1] : "input.txt";
    const char *output_path = (argc >= 3) ? argv[2] : "output.txt";
    int precision = (argc >= 4) ? atoi(argv[3]) : 0;
 
    printf("[OK] Loading input polynomials...\n");
 
    if (precision > 0) {
        printf("[PRECISION] Truncating to %d decimal places\n", precision);
    } else {
        printf("[PRECISION] Full (no truncation)\n");
    }
 
    FILE *in = fopen(input_path, "r");
    if (!in) {
        fprintf(stderr, "ERROR: cannot open %s\n", input_path);
        return 1;
    }
 
    InputPoly *input_polys = malloc(MAX_POLYS * sizeof(InputPoly));
    if (!input_polys) {
        fprintf(stderr, "ERROR: cannot allocate memory\n");
        fclose(in);
        return 1;
    }
 
    char line[MAX_LINE];
    int input_count = 0;
 
    while (fgets(line, sizeof(line), in) && input_count < MAX_POLYS) {
        const char *p = line;
        while (isspace(*p)) p++;
        if (!*p || *p == '\n') continue;
 
        int id;
        int coeff_count = parse_line_with_id(line, &id, input_polys[input_count].coeffs);
 
        if (coeff_count == 0) {
            fprintf(stderr, "WARNING: Skipping invalid input line (ID=%d)\n", id);
            continue;
        }
 
        // CRITICAL FIX: degree = coefficient_count - 1
        int degree = coeff_count - 1;
 
        if (degree > MAX_DEGREE) {
            fprintf(stderr, "ERROR: Polynomial ID=%d has degree %d > MAX_DEGREE %d\n",
                    id, degree, MAX_DEGREE);
            fprintf(stderr, "\n%s\n", line);
            free(input_polys);
            fclose(in);
            return 1;
        }
 
        input_polys[input_count].id = id;
        input_polys[input_count].degree = degree;
        input_polys[input_count].coeff_count = coeff_count;
        input_count++;
    }
 
    fclose(in);
    printf("[OK] Loaded %d input polynomials\n", input_count);
 
    printf("[OK] Loading output results and building hash table...\n");
 
    FILE *out = fopen(output_path, "r");
    if (!out) {
        fprintf(stderr, "ERROR: cannot open %s\n", output_path);
        free(input_polys);
        return 2;
    }
 
    OutputPoly *output_polys = malloc(MAX_POLYS * sizeof(OutputPoly));
    if (!output_polys) {
        fprintf(stderr, "ERROR: cannot allocate memory\n");
        fclose(out);
        free(input_polys);
        return 1;
    }
 
    int output_count = 0;
    long output_line_num = 0;
 
    while (fgets(line, sizeof(line), out) && output_count < MAX_POLYS) {
        output_line_num++;
        const char *p = line;
        while (isspace(*p)) p++;
        if (!*p || *p == '\n') continue;
 
        int id, root_count;
        int parsed = parse_output_line(line, &id, &root_count,
                                       output_polys[output_count].roots_left,
                                       output_polys[output_count].roots_right);
 
        if (parsed < 0) {
            fprintf(stderr, "ERROR: Failed to parse output line %ld\n", output_line_num);
            free(input_polys);
            free(output_polys);
            fclose(out);
            return 1;
        }
 
        output_polys[output_count].id = id;
        output_polys[output_count].root_count = parsed;
        hash_insert(id, output_count);
        output_count++;
    }
 
    fclose(out);
    printf("[OK] Loaded %d output results\n", output_count);
 
    printf("\n=== STURM ROOT VALIDATOR (Hash-based, Ultra-fast) ===\n");
    printf("[OK] Validating...\n");
 
    int total_polys = 0;
    int total_roots = 0;
    int valid_roots = 0;
    int invalid_roots = 0;
    int polys_with_errors = 0;
    int missing_ids = 0;
 
    double start_time = (double)clock() / CLOCKS_PER_SEC;
    double last_update = start_time;
 
    for (int i = 0; i < input_count; i++) {
        int input_id = input_polys[i].id;
 
        int out_idx = hash_lookup(input_id);
        if (out_idx == -1) {
            printf("\nNo output found for input ID=%d\n", input_id);
            missing_ids++;
            continue;
        }
 
        int poly_has_errors = 0;
        int poly_error_count = 0;
 
        for (int j = 0; j < output_polys[out_idx].root_count; j++) {
            double mid = (output_polys[out_idx].roots_left[j] +
                         output_polys[out_idx].roots_right[j]) / 2.0;
 
            // Use coeff_count for eval_poly
            double f_val = eval_poly(input_polys[i].coeffs,
                                    input_polys[i].coeff_count, mid);
 
            total_roots++;
 
            if (fabs(f_val) < TOLERANCE) {
                valid_roots++;
            } else {
                invalid_roots++;
                if (!poly_has_errors) {
                    printf("\nID=%d (degree %d): ERRORS FOUND\n",
                           input_id, input_polys[i].degree);
                    poly_has_errors = 1;
                }
                printf("  Root %d: x ∈ [%.6f, %.6f], f(%.6f) = %.2e [ERROR]\n",
                       j, output_polys[out_idx].roots_left[j],
                       output_polys[out_idx].roots_right[j], mid, f_val);
                poly_error_count++;
            }
        }
 
        if (poly_has_errors) {
            printf("  → %d invalid roots in this polynomial\n", poly_error_count);
            polys_with_errors++;
        }
 
        total_polys++;
 
        double now = (double)clock() / CLOCKS_PER_SEC;
        if ((total_polys % PROGRESS_INTERVAL == 0) || (now - last_update >= 1.0)) {
            double elapsed = now - start_time;
            print_progress(total_polys, input_count, elapsed);
            last_update = now;
        }
    }
 
    double end_time = (double)clock() / CLOCKS_PER_SEC;
    double elapsed = end_time - start_time;
 
    hash_free();
    free(input_polys);
    free(output_polys);
 
    printf("\n[OK] Done. Validated %d polynomials\n", total_polys);
    printf("[PERFORMANCE] Total time: %.2f seconds (%.2f poly/sec)\n",
           elapsed, total_polys / elapsed);
    printf("\n");
 
    printf("==============================================\n");
    printf("            VALIDATION SUMMARY               \n");
    printf("==============================================\n");
    printf("Polynomials tested:      %d\n", total_polys);
    printf("Total roots tested:      %d\n", total_roots);
    printf("Valid roots:             %d (%.1f%%)\n",
           valid_roots, total_roots > 0 ? 100.0 * valid_roots / total_roots : 0.0);
    printf("Invalid roots:           %d (%.1f%%)\n",
           invalid_roots, total_roots > 0 ? 100.0 * invalid_roots / total_roots : 0.0);
    printf("Polynomials with errors: %d\n", polys_with_errors);
    if (missing_ids > 0) {
        printf("Missing output IDs:      %d\n", missing_ids);
    }
    printf("==============================================\n");
 
    if (invalid_roots == 0 && missing_ids == 0) {
        printf("✓ VALIDATION PASSED\n");
        return 0;
    } else {
        if (invalid_roots > 0) {
            printf("✗ VALIDATION FAILED: %d invalid roots found\n", invalid_roots);
        }
        if (missing_ids > 0) {
            printf("✗ VALIDATION FAILED: %d missing output IDs\n", missing_ids);
        }
        return 1;
    }
}