結果

問題 No.53 悪の漸化式
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:14:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 4,178 bytes
コンパイル時間 587 ms
コンパイル使用メモリ 91,368 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:15:47
合計ジャッジ時間 1,380 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // Required for input/output operations (std::cin, std::cout)
#include <cmath>    // Required for mathematical functions, although we use a custom power function
#include <iomanip>  // Required for output formatting (std::fixed, std::setprecision)

// Function to compute base^exp using exponentiation by squaring with long double
// This method computes base^exp efficiently in O(log exp) time complexity.
// Using 'long double' provides higher precision compared to 'double', which is beneficial
// for numerical computations requiring high accuracy.
// The function assumes exp is a non-negative integer.
long double power_ld(long double base, int exp) {
    long double res = 1.0L; // Initialize result to 1.0. 'L' suffix denotes long double literal.
    
    // The algorithm works by repeatedly squaring the base and multiplying the result
    // by the base if the corresponding bit in the exponent is set.
    while (exp > 0) {
        // If the current exponent is odd (least significant bit is 1)
        if (exp % 2 == 1) {
            // Multiply the result by the current base value
            res *= base;
        }
        // Square the base for the next iteration.
        // This corresponds to moving to the next higher power of 2 in the base.
        base *= base;
        // Integer division of the exponent by 2 (equivalent to right bit shift).
        // This moves to the next bit of the exponent.
        exp /= 2;
    }
    // When exp becomes 0, the loop terminates and 'res' holds the final value base^exp.
    return res;
}

int main() {
    // Optimize C++ standard streams for faster input/output operations.
    // std::ios_base::sync_with_stdio(false) disables synchronization with C's stdio library.
    // std::cin.tie(NULL) unties std::cin from std::cout.
    // These optimizations are common in competitive programming to speed up I/O.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Declare an integer variable N to store the input index (0 <= N <= 100).
    std::cin >> N; // Read the value of N from standard input.
    
    long double result; // Declare a long double variable to store the computed value A_N.
                       // 'long double' is used for potentially better precision.

    // The problem defines a sequence A_k with A_0 = 4, A_1 = 3, and 4*A_k = 19*A_{k-1} - 12*A_{k-2}.
    // The characteristic equation is 4x^2 - 19x + 12 = 0, with roots x=4 and x=3/4.
    // The general solution is A_k = C1 * 4^k + C2 * (3/4)^k.
    // Using initial conditions A_0=4, A_1=3, we find C1=0 and C2=4.
    // Thus, the closed-form solution is A_k = 4 * (3/4)^k.
    
    // We need to compute A_N = 4 * (3/4)^N.
    
    // The base for the exponentiation is 3/4, which is 0.75.
    // Use 0.75L to specify a long double literal. 0.75 has an exact finite binary representation (0.11_2),
    // so using it directly avoids representation error for the base.
    long double base = 0.75L; 
    
    // Compute base^N using our custom exponentiation by squaring function 'power_ld'.
    long double term_power = power_ld(base, N);
    
    // The final result is 4 multiplied by the computed power term. Use 4.0L for the long double literal 4.
    result = 4.0L * term_power;

    // Output the computed result.
    // std::fixed ensures the output is in fixed-point notation (e.g., 1.234).
    // std::setprecision(10) sets the number of digits to display after the decimal point to 10.
    // This formatting ensures the output meets the problem's requirement for absolute or relative error
    // up to 10^-9, and provides sufficient decimal places for verification.
    std::cout << std::fixed << std::setprecision(10) << result << std::endl;
    
    // The "trick" in this problem likely relates to numerical instability. Computing A_N iteratively using
    // the recurrence relation with floating-point arithmetic would likely fail for larger N due to the
    // amplification of small errors by the dominant term associated with the root x=4. The closed-form
    // solution avoids this instability.
    
    return 0; // Indicate successful program execution.
}
0