Chef Hates Palindromes
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef's birthday is coming soon! His friend Fehc is going to send him a string of length N as a gift. Knowing that Chef doesn't like palindromes, Fehc wants the longest palindromic substring to be as short as possible. The string should only contain the first A latin letters(e.g. let A=2, then this string only contains 'a' and 'b'). Please help Fehc and find such a string. If multiple solution exists, you can print any.
- The first line of input is an integer T, denoting the number of test cases.
- T tests follow. For each test, there is a line containing two space-separated integers N and A.
For each test, print a number L and a string s, separated by one space. L is equal to the length of longest palindromic substring of s, and s is the string that Fehc will give to Chef. You must minimize L, but in the case of multiple s's, any valid s is OK.
- (sum of N in all test cases)≤105
Subtask #1 (21 points):
Subtask #2 (79 points):
- original constraints.
Input: 4 5 2 12 26 8 26 7 2 Output: 3 aaabb 1 hapybirthday 1 codechef 3 aaababb
Example case 1. There are multiple solutions. For example, "abaaa" is also correct. Note that "abbaa" is not a correct solution, since "abba" is a palindromic substring of length 4, which is not optimal.
|Tags||bruteforce, medium, nov17, r_64|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.