結果

問題 No.509 塗りつぶしツール
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:14:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,564 bytes
コンパイル時間 571 ms
コンパイル使用メモリ 73,848 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:15:20
合計ジャッジ時間 1,652 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector> // Not strictly needed for this specific code, but often useful

// Define hole counts for digits 0 through 9 using a const array.
// The index corresponds to the digit value. For example, holes[0] is the count for digit '0'.
// Based on the shapes provided in the problem description (visually inferred):
// - Digits 0, 4, 6, 9 have one enclosed white area (hole).
// - Digit 8 has two enclosed white areas (holes).
// - Digits 1, 2, 3, 5, 7 have no enclosed white areas (no holes).
const int holes[] = {
    1, // Digit 0: 1 hole
    0, // Digit 1: 0 holes
    0, // Digit 2: 0 holes
    0, // Digit 3: 0 holes
    1, // Digit 4: 1 hole
    0, // Digit 5: 0 holes
    1, // Digit 6: 1 hole
    0, // Digit 7: 0 holes
    2, // Digit 8: 2 holes
    1  // Digit 9: 1 hole
}; 

int main() {
    // Optimize C++ standard streams for faster Input/Output operations.
    // This is a common practice in competitive programming to avoid Time Limit Exceeded.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    // Declare input variable. The input n can be up to 10^9.
    // A standard int typically suffices, but long long is safer for potentially larger inputs.
    long long n_val; 
    // Read the input integer from standard input.
    std::cin >> n_val;
    
    // Handle the special case where the input number is 0.
    // The image will display a single digit '0'.
    if (n_val == 0) {
        // The digit '0' has N=1 digit count and H=1 hole count.
        // Using the derived formula 2*N + H + 1: 2*1 + 1 + 1 = 4 operations.
        std::cout << 4 << std::endl;
    } else {
        // For positive numbers n > 0.
        // Convert the number to its string representation to easily iterate through its digits.
        std::string s = std::to_string(n_val);
        
        // N stores the total number of digits in the number n.
        int N = s.length();
        
        // H stores the total count of holes across all digits of n. Initialize to 0.
        int H = 0;
        // Iterate through each character (representing a digit) in the string representation.
        for (char c : s) {
            // Convert the character digit (e.g., '8') into its integer value (e.g., 8).
            // This is done by subtracting the ASCII value of '0'.
            int digit_val = c - '0'; 
            // Add the number of holes corresponding to this digit value by looking up in the `holes` array.
            H += holes[digit_val]; 
        }
        
        // Calculate the minimum required fill operations using the derived formula: 2*N + H + 1.
        // The formula was derived by considering a 3-stage strategy using an auxiliary color
        // to prevent merging of regions during color changes.
        // Stage 1: Change all Black regions (digit bodies) to Grey (N ops).
        // Stage 2: Change all White regions (background + holes) to Black (1 + H ops).
        // Stage 3: Change all Grey regions (digit bodies) to White (N ops).
        // Total ops = N + (1+H) + N = 2N + H + 1.
        // Use 2LL literal to ensure the multiplication is performed using long long type, 
        // preventing potential overflow if N was extremely large (though N<=10 here, it's good practice).
        long long result = 2LL * N + H + 1; 
        
        // Print the calculated minimum number of operations followed by a newline character.
        std::cout << result << std::endl;
    }
    
    // Return 0 to indicate successful program execution.
    return 0;
}
0