N different palindromes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A palindrome is a string that reads same in both directions: forwards and backwards. For example, the strings radar and noon are palindromes, whereas the string chef is not a palindrome as being read backwards is becomes equal to fehc, which is not equal to chef.
Let's say that the pair of indices (i, j) denotes a palindrome in some string S iff i ≤ j and the substring starting at the i-th character and ending at the j-th character of S is a palindrome.
Given an integer N. Your task is to construct a string S such that there are exactly N different pairs (i, j) that denotes a palindrome.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the sought number of pairs that denote palindrome.
For each test case, output a single line containing a string S, consisting of lowecase Latin letters, and having exactly N distinct palindrome-denoting pairs. If there's a few such strings, output any one.
If such string S doesn't exist, output -1 instead of it.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 104
Input: 3 6 7 2 Output: noon radar ab
Example case 1. In the string "noon", the pairs that denote a palindrome are (1-indexed): (1, 1), (1, 4), (2, 2), (2, 3), (3, 3), (4, 4).
Example case 2. In the string "radar", the pairs that denote a palindrome are (1-indexed): (1, 1), (1, 5), (2, 2), (2, 4), (3, 3), (4, 4), (5, 5).
Example case 3. In the string "ab", the pairs denoting a palindrome are : (1, 1), (2, 2)
|Tags||ad-hoc dynamic-programming easy palindrome snckpa16 strings xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.