Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
Palindrome-k
Palindrome is a text which is read from left to
right and from right to left the same. For
example, 121 is a palindromic number. 122
is not a palindromic number because it
becomes 221 when it is read from right to left.
Assume that, distortion is allowed until certain value
(k). For example, if k is 1, 122 can be accepted as
palindrome because with 1 correction it can be turned
to be a palindrome. On the other hand, 1234 cannot
be a palindrome number if only 1 distortion is
allowed. It may be turned to a palindrome if two
distortions are allowed. Note: Assume that uppercase
and lowercase chars may be accepted the same.
Question:
Write a program that reads a text with the number
of distortions allowed for each. Return how many
of them are accepted as palindromes with the
given number of distortions.
Input specification:
You will be given an integer (n) in the beginning.
The following n lines will have an integer (k)
and a string with at most 2000 characters long
where 0 ≤ k ≤ 100 and 0 < n < 1000.
Output specification:
Show one integer, the number of Palindrome-k
numbers (or palindrome-k text).
Sample Input
3
1 SEven
1 1234
0 122
|
Sample Output
1
|
Explanation:
SEven can be turned to a palindrome if 1 distortion
is applied. However, 122 is not a Palindrome number
because no distortions (0) are allowed.
Thus only SEven is palindrome-k text.
Для отправки решений необходимо выполнить вход.
|