結果
問題 |
No.509 塗りつぶしツール
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }