let dp[n][i][j] is cnt of three-primes numbers which 2 last digits is i and j, then dp[n+1][i][j]+=dp[n][k][i], if kij is three-prime number

Wrong answer.
Help pls.

Here any three consecutive numbers means every three consecutive numbers.
For Eg. if the four digit number is abcd then (abc) itself has to be a three digit prime and also (bcd) should also be a three digit prime.
Taking the example for n = 5 let the 5 digit number be abcde then (abc) itself has to be a three digit prime, (bcd) should also be a three digit prime and at last (cde) should also be a three digit prime.

If any of the problem setter reads this then please clarify clearly about this. As I was stuck on this for almost 2 days, by pondering how come the answer for n = 4 is 204 while even bruteforce was giving me 2513.

Edited by author 09.11.2020 11:45

Edited by author 09.11.2020 11:45

I have two loops which calls recursive function

for 1 to 9
  for 0 to 9
    ans+=f(n-2,j,i) // f(rem,prev,prev_prev)

function f(i,j,k) has dp[1001][10][10] memoized solution.why doesnt it timeout.
I'm having hard time understanding my own solution although it is ACd in one trial.

Achtung!
Time limit exceeded Error :(
does anyone knows test 5? thank you!

Can anyone help me please? I don't understand what is three prime number? :S

Один и тот же алгоритм и практически один и тот же код,  с учётом схожести синтаксиса языков,  даёт :

AC 15 ms C++14 Clang

TLE #9 Python  2.7/3.4

WA#6 => check if you use module (1e9 + 9)

using System;
using System.Collections.Generic;
using System.Linq;

namespace ThreeprimeNumbers
{
    public static class IntExtensions
    {
        public static bool IsPrime(this int number)
        {
            for (var divisor = 2; divisor < number; divisor++)
                if (number % divisor == 0)
                    return false;
            return true;
        }
    }
    internal static class Solver
    {
        private static Func<IEnumerable<int>> ThreeDigitPrimeNumbers =
            () => Enumerable.Range(100, 900).Where(number => number.IsPrime());
        private static Dictionary<int, IEnumerable<int>> PrefixCorrespondance(IEnumerable<int> primeNumbers)
        {
            return primeNumbers
                .GroupBy(number => number / 10)
                .ToDictionary(group => group.Key, group => group.Select(item => item));
        }
        internal static long Solve(int digitCount)
        {
            var table = new long[digitCount - 2, 90];
            var prefixes = PrefixCorrespondance(ThreeDigitPrimeNumbers());
            for (var counter = 10; counter < 100; counter++)
                table[0, counter - 10] = (prefixes.TryGetValue(counter, out var collection)) ? collection.Count() : 0;
            for (var counter = 1; counter <= digitCount - 3; counter++)
                foreach (var pair in prefixes)
                    foreach (var primeNumber in pair.Value)
                    {
                        var suffix = primeNumber % 100 - 10;
                        table[counter, pair.Key - 10] += (suffix < 0) ? 0 : table[counter - 1, suffix];
                        table[counter, pair.Key - 10] %= 1000000009;
                    }
            long sum = 0;
            for (var counter = 0; counter < 90; counter++)
                sum = (sum + table[digitCount - 3, counter]) % 1000000009;
            return sum;

        }
        public static void Main()
        {
            int.TryParse(Console.ReadLine(), out int digitCount);
            Console.Write(Solve(digitCount));
        }
    }
}

Edited by author 08.09.2016 11:56

Explain me please, why if n=4, the answer is 204.
I get 2513.

" Pasha calls an integer a threeprime number if any three consecutive digits of this integer form a three-digit prime number"?
For example,if a number a1a2a3a4, a1a2a3 is a prime number ,the number a2a3a4 must be a prime number??  yes or no, please help me!  thank you !

then check carefully your solution for n=3 :)

My solutions is stack overflow in test 9. Help me, please.

The answer I get for 5 is 41616. I do not understand why this is not good. Can anybody tell me the right answer for 5?
Thx.

does anyone knows test 3? thank you!

I did not quite understand this part.
"calculated modulo 10^9 + 9"
What does that mean, and what is it used for...?

I know what modulo is, but I don't know what am I supposed to do with it... :)

Edited by author 06.05.2008 01:54

Edited by author 06.05.2008 01:54

Edited by author 06.05.2008 01:54

res += value;
res %= mod;

Why answer for 4 is 204?

If we have 143 three-digit primes numbers each of them can create 10 four-digit threeprimes numbers!

a1a2a3 - three-digit prime number -> a1a2a3* - four-digit threeprime number

+some numbers *a1a2a3 which is not included early.
So answer must be larger than  204.
Whats wrong? I don't understand...