SHARE
TWEET

Tuenti Contest 3 (Pablo Moreno)

Nbrevu Jun 20th, 2011 841 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.         Author: Pablo Moreno Olalla
  3.         Email address: darthbrevu@yahoo.es
  4. */
  5. #include <map>
  6. #include <set>
  7. #include <list>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <string>
  11. #include <numeric>
  12. #include <sstream>
  13. #include <utility>
  14. #include <iostream>
  15.  
  16. using namespace std;
  17.  
  18. //I've REALLY looked for efficiency on this one, although I feel that "addRangeDataSym" could have been better on that respect.
  19.  
  20. bool isPrime(unsigned long long ull)    {
  21.         unsigned long long sq=static_cast<unsigned long long>(ceil(sqrt(static_cast<long double>(ull))));
  22.         for (unsigned long long i=3;i<=sq;++i) if (ull%i==0) return false;
  23.         return true;
  24. }
  25.  
  26. inline unsigned long long reverse(unsigned long long ull)       {
  27.         unsigned long long res=0;
  28.         while (ull)     {
  29.                 res*=10;
  30.                 res+=ull%10;
  31.                 ull/=10;
  32.         };
  33.         return res;
  34. }
  35.  
  36. class EmirpRange        {
  37. public:
  38.         char first;
  39.         char last;
  40.         char total;
  41.         inline EmirpRange(unsigned long long f,unsigned long long l,unsigned long long t):first(static_cast<char>(f)),last(static_cast<char>(l)),total(static_cast<char>(t))    {}
  42.         inline bool operator<(const EmirpRange &er) const       {
  43.                 if (total<er.total) return true;
  44.                 else if (er.total<total) return false;
  45.                 else if (first<er.first) return true;
  46.                 else if (er.first<first) return false;
  47.                 else return last<er.last;
  48.         }
  49. };
  50.  
  51. //An object of this kind will be used so that calculations are not repeated. In this kind of problems, we
  52. //need speed! Otherwise it would take TOO long to calculate a large enough string of numbers.
  53. typedef map<EmirpRange,pair<set<unsigned long long>,unsigned long long> > EmirpMap;
  54.  
  55. inline unsigned long long numberOfDigits(unsigned long long ull,unsigned long long &first)      {
  56.         unsigned long long res=0;
  57.         while (ull)     {
  58.                 if (ull<10) first=ull;
  59.                 ull/=10;
  60.                 ++res;
  61.         }
  62.         return res;
  63. }
  64.  
  65. typedef list<pair<EmirpRange,bool> > RangeList;
  66.  
  67. inline void generateEmirpRange(unsigned long long ull,RangeList &out)   {
  68.         static unsigned long long emirpable[]={1,3,7,9};
  69.         unsigned long long firstDigit;
  70.         unsigned long long digits=numberOfDigits(ull,firstDigit);
  71.         size_t maxSearch=0;
  72.         for (size_t i=1;i<4;++i) if (emirpable[i]<=firstDigit) ++maxSearch;
  73.         else break;
  74.         if (digits<2) return;
  75.         for (unsigned long long i=2;i<digits;++i) for (size_t a=0;a<4;++a) for (size_t b=0;b<4;++b) out.push_back(make_pair(EmirpRange(emirpable[a],emirpable[b],i),true));
  76.         for (size_t a=0;a<maxSearch;++a) for (size_t b=0;b<4;++b) out.push_back(make_pair(EmirpRange(emirpable[a],emirpable[b],digits),true));
  77.         for (size_t b=0;b<4;++b) out.push_back(make_pair(EmirpRange(emirpable[maxSearch],emirpable[b],digits),false));
  78. }
  79.  
  80. inline unsigned long long power10(unsigned long long exp)       {
  81.         unsigned long long res=1;
  82.         //I could have used floating arithmetic, but I don't like its small lack of precision.
  83.         while (exp>0)   {
  84.                 res*=10;
  85.                 --exp;
  86.         }
  87.         return res;
  88. }
  89.  
  90. void addRangeDataSym(EmirpMap &data,const EmirpRange& er)       {
  91.         set<unsigned long long> &sNorm=data[er].first;
  92.         unsigned long long n=static_cast<unsigned long long>(er.last)+power10(static_cast<unsigned long long>(er.total-1))*static_cast<unsigned long long>(er.first);
  93.         unsigned long long maxData=power10(static_cast<unsigned long long>(er.total-2));
  94.         unsigned long long r;
  95.         for (size_t i=0;i<maxData;++i)  {
  96.                 r=reverse(n);
  97.                 if (n!=r)       {
  98.                         if (isPrime(n)&&isPrime(r))     {
  99.                                 sNorm.insert(n);
  100.                                 sNorm.insert(r);
  101.                         }
  102.                 }
  103.                 n+=10;
  104.         }
  105.         data[er].second=accumulate(sNorm.begin(),sNorm.end(),0);
  106. }
  107.  
  108. void addRangeData(EmirpMap &data,const EmirpRange &er)  {
  109.         if (er.first==er.last)  {
  110.                 addRangeDataSym(data,er);
  111.                 return;
  112.         }
  113.         EmirpRange revEr=er;
  114.         swap(revEr.first,revEr.last);
  115.         set<unsigned long long> &sNorm=data[er].first;
  116.         set<unsigned long long> &sRev=data[revEr].first;
  117.         unsigned long long n=static_cast<unsigned long long>(er.last)+power10(static_cast<unsigned long long>(er.total-1))*static_cast<unsigned long long>(er.first);
  118.         unsigned long long maxData=power10(static_cast<unsigned long long>(er.total-2));
  119.         unsigned long long r;
  120.         for (size_t i=0;i<maxData;++i)  {
  121.                 if (isPrime(n)) {
  122.                         r=reverse(n);
  123.                         if (isPrime(r)) {
  124.                                 sNorm.insert(n);
  125.                                 sRev.insert(r);
  126.                         }
  127.                 }
  128.                 n+=10;
  129.         }
  130.         data[er].second=accumulate(sNorm.begin(),sNorm.end(),0);
  131.         data[revEr].second=accumulate(sRev.begin(),sRev.end(),0);
  132. }
  133.  
  134. unsigned long long sumEmirpsUpTo(unsigned long long in,EmirpMap &data)  {
  135.         RangeList ranges;
  136.         generateEmirpRange(in,ranges);
  137.         unsigned long long res=0;
  138.         for (RangeList::const_iterator it=ranges.begin();it!=ranges.end();++it) {
  139.                 if (data.count(it->first)==0) addRangeData(data,it->first);
  140.                 if (it->second) res+=data[it->first].second;
  141.                 else    {
  142.                         set<unsigned long long> &container=data[it->first].first;
  143.                         res+=accumulate(container.begin(),container.upper_bound(in),0);
  144.                 }
  145.         }
  146.         return res;
  147. }
  148.  
  149. int main(int argc,char **argv)  {
  150.         //The first two lines are not strictly necessary, but make the code a little more handy.
  151.         if (argc>=2) freopen(argv[1],"r",stdin);
  152.         if (argc>=3) freopen(argv[2],"w",stdout);
  153.         string tmp;
  154.         unsigned long long ull;
  155.         EmirpMap data;
  156.         do      {
  157.                 getline(cin,tmp);
  158.                 istringstream iss(tmp);
  159.                 iss>>ull;
  160.                 if (!iss.fail()) cout<<sumEmirpsUpTo(ull,data)<<endl;
  161.         }       while (!cin.eof());
  162.         return 0;
  163. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top