All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Mike likes strings. He is also interested in algorithms. A few days ago he discovered for himself a very nice problem:
You are given a digit string S. You need to count the number of substrings of S, which are palindromes.
Do you know how to solve it? Good. Mike will make the problem a little bit more difficult for you.
You are given a digit string S. You need to count the number of substrings of S, which are palindromes without leading zeros and can be divided by 3 without a remainder.
A string is a palindrome if it reads the same backward as forward. A string is a palindrome without leading zeros if it reads the same backward as forward and doesn't start with symbol '0'. A string is a digit string, if it doesn't contain any symbols except '0', '1', '2', ..., '9'.
Please, note that you should consider string "0" as a palindrome without leading zeros.
The first line of the input contains a digit string S.
Your output should contain the only integer, denoting the number of substrings of S, which are palindromes without leading zeros and can be divided by 3 without a remainder.
1 ≤ |S| ≤ 1 000 000
Input: 1045003 Output: 4
In the example you should count S[2..2] = "0", S[5..5] = "0", S[6..6] = "0" and S[7..7] = "3".
|Tags||cook44, kostya_by, manacher, medium, string|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.