Show all threads Hide all threads Show all messages Hide all messages |
Hint O(n*10^3) | 👾_challenger128_[PermSU] | 1586. Threeprime Numbers | 31 Mar 2021 20:33 | 1 |
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 |
WA#7 | pavelkaryukov | 1586. Threeprime Numbers | 22 Mar 2021 02:32 | 2 |
WA#7 pavelkaryukov 14 Apr 2020 10:00 I had int32 overflow for the sum, switched to long and it worked |
CLARIFICATION ABOUT 204 as Solution for n = 4 !!!!! | Sahil | 1586. Threeprime Numbers | 9 Nov 2020 11:43 | 1 |
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 |
Doubt about my AC. | ajay jadhav | 1586. Threeprime Numbers | 5 May 2020 00:31 | 1 |
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. |
WA#5 | pavelkaryukov | 1586. Threeprime Numbers | 14 Apr 2020 10:01 | 2 |
WA#5 pavelkaryukov 10 Apr 2020 10:08 Achtung! Time limit exceeded Error :( does anyone knows test 5? thank you! Re: WA#5 pavelkaryukov 14 Apr 2020 10:01 big number(10000 maybe) and time more 1 sec. |
What is three prime number? | Nikola | 1586. Threeprime Numbers | 20 Dec 2017 20:54 | 6 |
Can anyone help me please? I don't understand what is three prime number? :S My english is not good... Let my try to explane you on example: ************************************** 1274 - not this is not three prime number because 127 - this is 3.-digit prime nubmer , but 274 - this is not 3.-digit prime number... *************************************** 1137 - is this is three prime number because 113 - this is 3.-digit prime number, and 137 - this is 3.-digit prime number *************************************** So every 3 consecutive digits in number X must be 3.-digit prime number... I hope this help... It's not true number is three digits prime number if any three digits are prime "Pasha calls an integer a threeprime number if any three consecutive digits of this integer form a three-digit prime number." So if we write number A as A[1]A[2]...A[n] (A[i] - i-th digit of this number), than whole number A will be 'threeprime' if and only if for each i=1,2..., n-2 number A[i]A[i+1]A[i+2] is prime number. I understand now. Thanks a lot guys. The problem won't be problem anymore :) Edit: Except one more thing? 3 digit number is threeprime only if the number is prime right? Example: 101 is prime number so that means it's also a threeprime number right? Or that's not always right? Edited by author 04.05.2008 06:39 Edited by author 04.05.2008 06:47 |
Сверхъестественная разница в скорости работы между Python и C++ | Mahilewets | 1586. Threeprime Numbers | 22 Jul 2017 01:01 | 1 |
Один и тот же алгоритм и практически один и тот же код, с учётом схожести синтаксиса языков, даёт : AC 15 ms C++14 Clang TLE #9 Python 2.7/3.4 |
WA#6 | Vladyabra (TNU) | 1586. Threeprime Numbers | 20 Jul 2017 12:57 | 2 |
WA#6 Vladyabra (TNU) 10 Feb 2016 01:48 WA#6 => check if you use module (1e9 + 9) |
C# solution | InDevRus | 1586. Threeprime Numbers | 9 Jun 2017 07:03 | 1 |
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)); } } } |
No subject | Yogendra Singh Chouhan | 1586. Threeprime Numbers | 8 Sep 2016 11:52 | 1 |
No subject Yogendra Singh Chouhan 8 Sep 2016 11:52 Edited by author 08.09.2016 11:56 |
Why if n=4, the answer is 204 | plague | 1586. Threeprime Numbers | 9 Feb 2015 19:41 | 3 |
Explain me please, why if n=4, the answer is 204. I get 2513. 1031 is not a THREE-PRIME nummber. 103 is THREE-PRIME nummber, but 031 isn't, it's TWO-PRIME number Thank you for question and answers. It help to understand the task. |
What is mean of "any three consecutive digits"? | stat958 | 1586. Threeprime Numbers | 11 Aug 2013 12:09 | 2 |
" 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 ! yes. In general: For an n-digit number = a(1)a(2)a(3)a(4)...a(n-1)a(n) define p(i) = 3-digit number a(i)a(i+1)a(i+2) where 1 <= i <= n-2. Then each p(i) has to be a prime number *AND* for each p(i) holds: 100 <= p(i) <= 999 Edited by author 11.08.2013 12:11 |
If WA2 | Vas | 1586. Threeprime Numbers | 26 Nov 2012 18:07 | 1 |
then check carefully your solution for n=3 :) |
Help me 'Crash (stack overflow)' | hhiepit | 1586. Threeprime Numbers | 24 Nov 2012 17:29 | 1 |
My solutions is stack overflow in test 9. Help me, please. |
hello | Peca | 1586. Threeprime Numbers | 2 Nov 2012 23:15 | 2 |
hello Peca 21 Sep 2012 21:37 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. |
wa3 | Peca | 1586. Threeprime Numbers | 22 Sep 2012 04:10 | 1 |
wa3 Peca 22 Sep 2012 04:10 does anyone knows test 3? thank you! |
module 10^9 + 9 | TrickY | 1586. Threeprime Numbers | 2 Mar 2012 02:43 | 4 |
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 There are too many solutions for larger input data, so instead of outputting "solution", you should output "solution mod 1000000009" - if you do not do that during the calculations, the number of solutions will exceed the maximum long size (approximately 2*10^9), therefore crashing your program.22 Req Ganesh R 2 Feb 2012 21:43 I cant understand the o/p. What is the procedure actually.. How can we get 204 on the i/p 4. Can u pls explain There is last limit of programming language! It will be incorrect when you not use 1000000009!!!! (only 1000000009) |
Help me WA 9 | spark-roman | 1586. Threeprime Numbers | 11 Dec 2011 16:50 | 2 |
You probably didnt MOD correctly. I got wa in case 9 for this |
Use this to get AC! | Tigran92[RAU_902] | 1586. Threeprime Numbers | 5 Nov 2010 01:30 | 1 |
|
Clarification | DixonD (Lviv NU) | 1586. Threeprime Numbers | 24 Jul 2009 19:37 | 4 |
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... "Pasha calls an integer a threeprime number if ANY( !!! ) three consecutive digits of this integer form a three-digit prime number" Read the statement. For the first time i didn't understand too :-))) Finally understand it. Thanks a lot! Edited by author 27.10.2007 16:19 if all three consecutive letters..... bla bla .... any is clearly not very clear.... |