#include "testlib.h" #include #include #include #include using namespace std; // Helper function to generate a random char from 'a' to 'a' + char_range - 1 // Ensures char_range is at least 1. char random_char(int char_range) { ensure(char_range >= 1); // Precondition for rnd.next return (char)('a' + rnd.next(0, char_range - 1)); } // Helper function to check if a string is a palindrome bool is_palindrome(const string& s) { string reversed_s = s; reverse(reversed_s.begin(), reversed_s.end()); return s == reversed_s; } // Helper function to check if a string is a pseudo-palindrome // (Can become a palindrome by removing exactly one character) bool is_pseudo(const string& s) { int n = s.length(); // Problem constraint: length >= 3, so n will be at least 3 // and removing one character leaves length >= 2. for (int i = 0; i < n; ++i) { // Create string with character i removed string temp = s.substr(0, i) + s.substr(i + n - 1); // Corrected substr usage if (is_palindrome(temp)) { return true; } } return false; } int main(int argc, char* argv[]) { registerGen(argc, argv, 1); // Initialize testlib generator // --- Generation Hyperparameters --- // 1. String Length (N) // Keep it small for easy verification (e.g., 3 to 15) // Problem constraints: 3 <= N <= 100,000 int min_len = 3; int max_len = 15; // Small max length for easy verification int N = rnd.next(min_len, max_len); // 2. Target Type (0: Palindrome, 1: Pseudo-palindrome, 2: Neither) // Randomly choose which type of string to generate. int target_type = rnd.next(0, 2); // 0, 1, or 2 // 3. Character Range Size (char_range) // How many distinct characters to potentially use (from 'a' up to 'a'+char_range-1) // Range: 1 to 26 int min_char_range = 1; int max_char_range = 26; int char_range = rnd.next(min_char_range, max_char_range); // --- Adjust Hyperparameters for Consistency --- // If target is Pseudo (1) or Neither (2), we need at least 2 distinct characters // Otherwise, only palindromes (like "aaaa") are possible. if ((target_type == 1 || target_type == 2) && char_range == 1) { // Force char_range to be at least 2 if possible if (max_char_range >= 2) { char_range = rnd.next(2, max_char_range); } else { // This case shouldn't happen with max_char_range=26, but if it did, // we'd be forced to generate a palindrome. target_type = 0; } } // --- String Generation Logic --- string s = ""; bool generated = false; // Flag used for type 2 generation loop // Generate Type 0: Palindrome if (target_type == 0) { string first_half = ""; int half_len = (N + 1) / 2; // Equivalent to ceil(N/2.0) for (int i = 0; i < half_len; ++i) { first_half += random_char(char_range); } s = first_half; // Start with the first half string second_half = first_half; if (N % 2 == 1) { // If N is odd, the middle char shouldn't be duplicated second_half.pop_back(); } reverse(second_half.begin(), second_half.end()); // Reverse for the second half s += second_half; generated = true; } // Generate Type 1: Pseudo-palindrome // Strategy: Create a palindrome, then change one character ensuring it's no longer a palindrome. else if (target_type == 1) { // Need at least char_range > 1 to guarantee a change is possible. This was handled above. ensure(char_range > 1); // Assert the condition adjusted earlier // Generate base palindrome of length N string base_palindrome = ""; string first_half = ""; int half_len = (N + 1) / 2; for (int i = 0; i < half_len; ++i) { first_half += random_char(char_range); } base_palindrome = first_half; string second_half = first_half; if (N % 2 == 1) { second_half.pop_back(); } reverse(second_half.begin(), second_half.end()); base_palindrome += second_half; s = base_palindrome; // Try to change one character to break the palindrome property. // Retry if the change accidentally creates another palindrome (rare). int attempts = 0; const int MAX_CHANGE_ATTEMPTS = 20; // Safety limit do { s = base_palindrome; // Reset to original palindrome for retry int change_pos = rnd.next(0, N - 1); // Index to change char original_char = s[change_pos]; char new_char; // Find a different character to put at change_pos do { new_char = random_char(char_range); } while (new_char == original_char); // Ensure the character actually changes s[change_pos] = new_char; // Apply the change attempts++; } while (is_palindrome(s) && attempts < MAX_CHANGE_ATTEMPTS); // If after many attempts we still have a palindrome (highly unlikely), // fall back to generating a Type 2 (which guarantees non-palindrome). if (is_palindrome(s)) { target_type = 2; // Fall through to Type 2 generation logic below } else { generated = true; // Successfully generated a non-palindrome string by one change // This generated string is *likely* a pseudo-palindrome. // A perfect generator might verify is_pseudo(s) here, but this is usually sufficient. } } // Generate Type 2: Neither Palindrome nor Pseudo-palindrome // Strategy: Generate random strings until one is found that fits Type 2. // This also handles fallbacks from Type 1 generation failure. if (target_type == 2 && !generated) { // We need char_range > 1. This was handled above. if (char_range <= 1) { // If somehow still here with char_range=1, create a palindrome (only option) string first_half = ""; int half_len = (N + 1) / 2; for (int i = 0; i < half_len; ++i) first_half += random_char(char_range); // Will be 'a' s = first_half; string second_half = first_half; if (N % 2 == 1) second_half.pop_back(); reverse(second_half.begin(), second_half.end()); s += second_half; } else { // Generate random strings and check until Type 2 is found int attempts = 0; const int MAX_RANDOM_ATTEMPTS = 100; // Safety limit do { s = ""; for (int i = 0; i < N; ++i) { s += random_char(char_range); } attempts++; } while ((is_palindrome(s) || is_pseudo(s)) && attempts < MAX_RANDOM_ATTEMPTS); // If we failed after many attempts (e.g., N=3, char_range=2 makes Type 2 impossible) // the loop terminates, and we output the last generated string 's', // which might be Type 0 or 1 in those rare edge cases. For most N/char_range, // this will successfully generate a Type 2 string. } generated = true; } // --- Final Checks and Output --- // Ensure generated string meets length constraints (should always be true here) ensure(s.length() >= min_len && s.length() <= 100000); // Check against problem statement broader constraint too ensure(s.length() == N); // Output the single test case (T=1) println(1); println(s); return 0; }

코드 #2194