結果

問題 No.178 美しいWhitespace (1)
ユーザー qwewe
提出日時 2025-05-14 13:14:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 5,770 bytes
コンパイル時間 732 ms
コンパイル使用メモリ 75,536 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:15:46
合計ジャッジ時間 1,713 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>  // For input (std::cin) and output (std::cout)
#include <vector>    // For std::vector to store initial widths
#include <algorithm> // For std::max to find the maximum width

int main() {
    // Optimize standard C++ streams for faster Input/Output operations.
    // This is often helpful in competitive programming to avoid Time Limit Exceeded.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Variable to store the number of lines in the source code
    std::cin >> n; // Read the number of lines from standard input

    // Vector to store the initial width of each line.
    // Using 'long long' is important because the width (a + 4*b) can potentially
    // exceed the maximum value of a 32-bit integer, given that a_i and b_i can be up to 10^7.
    // Max width could be around 10^7 + 4 * 10^7 = 5 * 10^7, which fits in a 32-bit int,
    // but the sum of differences might exceed it. Using long long throughout for safety.
    std::vector<long long> initial_widths(n);

    // Variable to keep track of the maximum initial width encountered among all lines.
    // Initialized to 0. Using 'long long' for consistency.
    long long max_initial_width = 0LL;

    // Variable to store the parity (0 for even, 1 for odd) required for all lines.
    // We determine this from the first line and check consistency with subsequent lines.
    // Initialized to -1 to indicate that the required parity hasn't been determined yet.
    int required_parity = -1;

    // Boolean flag to track if it's possible to make all lines have the same width.
    // We initially assume it is possible and set it to false if we find a contradiction.
    bool possible = true;

    // First pass: Read input, calculate initial widths, find the maximum width,
    // and check if all initial widths have the same parity.
    for (int i = 0; i < n; ++i) {
        int a; // Number of spaces on the current line
        int b; // Number of tabs on the current line
        std::cin >> a >> b; // Read the counts of spaces and tabs for line i

        // Calculate the initial width of the current line using the formula: a + 4*b.
        // Use '4LL' (long long literal) to ensure the multiplication is done using 64 bits,
        // preventing potential overflow before adding 'a'.
        long long current_width = (long long)a + 4LL * b;

        // Store the calculated initial width in the vector at the corresponding index.
        initial_widths[i] = current_width;

        // Update the maximum initial width if the current line's width is greater
        // than the maximum found so far.
        max_initial_width = std::max(max_initial_width, current_width);

        // Check the parity of the current width, but only if we haven't already
        // determined that it's impossible.
        if (possible) {
            int current_parity = current_width % 2; // Calculate parity (0 for even, 1 for odd)

            // If the required parity hasn't been set yet (this is the first line processed,
            // effectively), set the required parity based on this line.
            if (required_parity == -1) {
                required_parity = current_parity;
            }
            // If the required parity has already been set, compare the current line's parity to it.
            // If they differ, it's impossible to make all lines have the same width by adding
            // full-width spaces (since each adds 2, preserving parity).
            else if (current_parity != required_parity) {
                possible = false; // Mark as impossible. No need to check parity further.
            }
        }
    }

    // After processing all lines, check the 'possible' flag.
    if (!possible) {
        // If it was determined to be impossible (due to inconsistent parities),
        // print -1 followed by a newline, as required by the problem statement.
        std::cout << -1 << std::endl;
    } else {
        // If it is possible (all initial widths have the same parity), calculate
        // the total minimum number of full-width spaces needed.
        long long total_full_width_spaces = 0LL; // Initialize the total count to 0.

        // The target width for all lines must be at least the maximum initial width.
        // To minimize the number of added full-width spaces, we choose the smallest
        // possible target width, which is exactly the 'max_initial_width'.
        // This target width is achievable for all lines because:
        // 1. target_width >= initial_width[i] for all i.
        // 2. target_width and initial_width[i] have the same parity for all i,
        //    so (target_width - initial_width[i]) is always an even non-negative number.
        long long target_width = max_initial_width;

        // Second pass: Iterate through the stored initial widths of all lines.
        for (long long width : initial_widths) {
            // Calculate the difference between the target width and the current line's initial width.
            // This difference represents the total width that needs to be added to this line.
            long long diff = target_width - width;

            // Since each full-width space contributes 2 to the width, the number of
            // full-width spaces needed for this specific line (c_i) is half the difference.
            // Integer division (diff / 2) gives the correct number of spaces.
            total_full_width_spaces += diff / 2;
        }

        // Print the calculated total minimum number of full-width spaces required
        // across all lines, followed by a newline.
        std::cout << total_full_width_spaces << std::endl;
    }

    // Indicate successful program execution by returning 0.
    return 0;
}
0