結果

問題 No.691 E869120 and Constructing Array 5
ユーザー qwewe
提出日時 2025-05-14 13:10:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,427 bytes
コンパイル時間 1,104 ms
コンパイル使用メモリ 95,476 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:11:47
合計ジャッジ時間 8,155 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // For input/output streams
#include <vector>   // Standard library vector, though not directly used in the final logic
#include <cmath>    // For mathematical functions like fabsl (absolute value for long double), sqrtl (sqrt for long double), llroundl (round to nearest long long for long double)
#include <iomanip>  // For output formatting, e.g., std::fixed, std::setprecision, useful for debugging floating point values

// Use 'long double' for higher precision floating point calculations, which is crucial for this problem's accuracy requirements.
using Real = long double;

// Function to compute the square root of a 'long double' value.
// Handles potentially small negative inputs due to floating point errors by returning 0.
Real sqrt_ld(Real x) {
    if (x < 0) return 0; 
    return sqrtl(x); // Use sqrtl from cmath for long double
}

// Function to round a 'long double' value to the nearest 'long long' integer.
// Ensures the result is non-negative, as required for the elements e_i.
long long round_ll(Real x) {
    // llroundl rounds to the nearest long long integer. Ties are rounded away from zero.
    long long rounded_val = llroundl(x);
    // If the result of rounding is negative (can happen if x is negative), return 0,
    // since e_i must be non-negative integers.
    if (rounded_val < 0) return 0LL; 
    return rounded_val;
}


int main() {
    // Optimize standard I/O operations for speed.
    std::ios_base::sync_with_stdio(false); // Disable synchronization with C standard streams
    std::cin.tie(NULL); // Untie cin from cout

    int Q; // Number of queries
    std::cin >> Q;

    // Process each query
    while (Q--) {
        Real P; // Target value for the query
        std::cin >> P;

        // --- N=1 Approach ---
        // Try to find a single non-negative integer k such that sqrt(k) is close to P.
        
        Real P2 = P * P; // Calculate P squared
        // Find the nearest integer k to P^2. Ensure k is non-negative.
        long long k = round_ll(P2); 
        
        // Calculate the square root of k
        Real sqrt_k = sqrt_ld(static_cast<Real>(k));
        // Calculate the absolute difference between sqrt(k) and P
        Real diff = fabsl(sqrt_k - P);

        // Define the required absolute error tolerance
        const Real tolerance_N1 = 1e-10L;
        
        // Check if the error is within the tolerance
        if (diff <= tolerance_N1) { 
            // If N=1 works, output the result: N=1 and the value k
            std::cout << 1 << " " << k << "\n";
        } else {
            // --- N=3 Approach ---
            // If N=1 fails, try to find three non-negative integers e1, e2, e3
            // of the form k_i * M, such that their square roots sum up close to P.
            // We use a scaling factor M = 1,000,000 = 1000^2.
            
            const Real F = 1000.0L; // Scaling factor F = sqrt(M)
            const long long M = 1000000LL; // M = F^2
            // The target sum for the scaled square roots (sqrt(k_i))
            Real target_T = P / F; 
            // The tolerance for the scaled sum is derived from the original tolerance.
            // The error in P should be at most 1e-10, so error in P/F should be at most 1e-10 / F.
            const Real tolerance_N3 = tolerance_N1 / F; 
            
            // Set a maximum value for k1, k2, k3 to limit the search space.
            // 150 is chosen heuristically; large enough to cover expected values but small enough for performance.
            const int K_max = 150; 
            bool found = false; // Flag to track if a solution is found

            // Iterate through possible integer values for k1
            for (int k1_int = 0; k1_int <= K_max; ++k1_int) {
                Real k1_real = static_cast<Real>(k1_int);
                Real sqrt_k1 = sqrt_ld(k1_real);
                
                 // Optimization: If sqrt(k1) alone is already too large, no need to check further.
                if (sqrt_k1 > target_T + tolerance_N3) continue;

                // Iterate through possible integer values for k2
                for (int k2_int = 0; k2_int <= K_max; ++k2_int) {
                     Real k2_real = static_cast<Real>(k2_int);
                     Real sqrt_k2 = sqrt_ld(k2_real);

                     // Optimization: If sqrt(k1) + sqrt(k2) is already too large, no need to check further.
                     if (sqrt_k1 + sqrt_k2 > target_T + tolerance_N3) continue; 

                     // Calculate the required value for sqrt(k3) to reach the target sum T.
                     Real T_prime = target_T - sqrt_k1 - sqrt_k2;

                     // T_prime must represent sqrt(k3), so it should be non-negative.
                     // Allow a tiny negative value due to floating point inaccuracies.
                     const Real neg_threshold = -1e-14L; // Small tolerance for negativity check
                     if (T_prime < neg_threshold) continue; // If substantially negative, this path is invalid.
                     if (T_prime < 0) T_prime = 0; // Clamp very small negatives to zero.

                     // Find the candidate integer k3 by rounding T_prime^2. Ensure non-negativity.
                     long long k3_ll = round_ll(T_prime * T_prime);
                     
                     // Check if the candidate k3 is within the allowed range [0, K_max].
                     if (k3_ll > K_max) continue; 

                     // Calculate the sum of square roots using the chosen k1, k2, and candidate k3.
                     Real k3_real = static_cast<Real>(k3_ll);
                     Real sqrt_k3 = sqrt_ld(k3_real);
                     Real S = sqrt_k1 + sqrt_k2 + sqrt_k3; // Calculated sum
                     
                     // Check if the calculated sum S is within the tolerance range of the target scaled sum T.
                     if (fabsl(S - target_T) <= tolerance_N3) {
                         // If the accuracy is met, we found a solution.
                         // Output N=3 and the corresponding e_i values (k_i * M).
                         std::cout << 3 << " " << (long long)k1_int * M << " " << (long long)k2_int * M << " " << k3_ll * M << "\n";
                         found = true; // Set flag
                         goto next_query; // Use goto to break out of nested loops and proceed to next query
                     }
                }
            }
            
            // This block is executed if the nested loops complete without finding a solution.
            // According to the problem statement and structure, a solution should always be found
            // either by N=1 or this N=3 strategy. If this block is reached, something unexpected happened.
             if (!found) {
                 // Output an error message to standard error for debugging purposes.
                 std::cerr << "Error: Solution not found for P = " << std::fixed << std::setprecision(15) << P << std::endl;
                 // As a fallback, output the N=1 result (integer k) calculated earlier. Even though it failed the initial accuracy test, 
                 // it might be the best guess or satisfy some weaker condition.
                 std::cout << 1 << " " << k << "\n";
             }

            next_query:; // Label for the goto statement
        }
    }

    return 0; // Indicate successful execution
}
0