main.cpp

#include <bits/stdc++.h>
#include "json.hpp"  // nlohmann/json header
using json = nlohmann::json;
using namespace std;

struct Share {
    int x;
    int base;
    string value;
};

// Convert value from given base to decimal
long double convertToDecimal(const string &val, int base) {
    long double num = 0;
    for (char c : val) {
        int digit;
        if (isdigit(c)) digit = c - '0';
        else digit = 10 + (tolower(c) - 'a'); // handle a-f
        num = num * base + digit;
    }
    return num;
}

// Lagrange interpolation at x=0
long double lagrangeConstant(const vector<pair<int,long double>> &pts, int k) {
    long double secret = 0.0;
    for (int i = 0; i < k; i++) {
        long double xi = pts[i].first;
        long double yi = pts[i].second;
        long double term = yi;
        for (int j = 0; j < k; j++) {
            if (i != j) {
                long double xj = pts[j].first;
                term *= (0 - xj) / (xi - xj);
            }
        }
        secret += term;
    }
    return secret;
}

// Evaluate polynomial at given x
long double evaluatePolynomial(const vector<pair<int,long double>> &pts, int k, long double x_val) {
    long double val = 0.0;
    for (int i = 0; i < k; i++) {
        long double xi = pts[i].first;
        long double yi = pts[i].second;
        long double term = yi;
        for (int j = 0; j < k; j++) {
            if (i != j) {
                long double xj = pts[j].first;
                term *= (x_val - xj) / (xi - xj);
            }
        }
        val += term;
    }
    return val;
}

int main() {
    ifstream inFile("input.json");
    if (!inFile) {
        cout << "Cannot open input.json" << endl;
        return 1;
    }

    json j;
    inFile >> j;

    int n = j["keys"]["n"];
    int k = j["keys"]["k"];

    vector<Share> shares;
    for (auto &el : j.items()) {
        if (el.key() == "keys") continue;
        int x = stoi(el.key());
        int base = stoi(el.value()["base"].get<string>());
        string value = el.value()["value"];
        shares.push_back({x, base, value});
    }

    vector<pair<int,long double>> points;
    for (auto s : shares) {
        long double y = convertToDecimal(s.value, s.base);
        points.push_back({s.x, y});
    }

    long double secret = lagrangeConstant(points, k);

    vector<int> wrongShares;
    for (int i = 0; i < n; i++) {
        long double y_est = evaluatePolynomial(points, k, points[i].first);
        if (abs(y_est - points[i].second) > 1e-6) {
            wrongShares.push_back(points[i].first);
        }
    }

    cout << "Secret: " << llround(secret) << endl;
    if (wrongShares.empty()) {
        cout << "Wrong shares: None" << endl;
    } else {
        cout << "Wrong shares: ";
        for (int x : wrongShares) cout << x << " ";
        cout << endl;
    }

    return 0;
}