ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1586. Threeprime Numbers

Need help
Posted by Georgiy Savchenko 6 Nov 2007 14:49
Hey all, could onyone point my error out?

I have solved the problem for n = 4 and got right result, but I cannot go ahead to n = 5.
At each step from 4 to n inclusive I am keeping how many treeprime numbers exist for all possible two last digits - function Count (for instance, treeprimenumbers end with AB: Count(AB) = X; end with CD: Count(CD) = Y).
To go aheah to n = n + 1 I am trying to add digit L from the set {1, 3, 7, 9} (all possible end digits for prime numbers) at the end of each possible last digits cases, getting ABL, CDL, and so on. Then I check if the result number ABL, CDL, ... is a prime one. If yes, then I define a new function CountNew, writing CountNew(BL) = CountNew(BL) + Count(AB) (explanation: increase number of treeprime numbers that end with BL, increasing is the number of treeprime numbers end with AB).
Having completed the step, I perform Count = NewCount.

This approach gives right result for n=3 and 4, but not 5 (I found it out by a bruteforce solution)

Am I missing something?

Edited by author 06.11.2007 14:49

Edited by author 06.11.2007 14:50
Re: Need help
Posted by Georgiy Savchenko 12 Nov 2007 20:16
Finally got it. Had a pretty stupid error, the described approach is correct :)