Nbrevu

Tuenti Contest 3 (Pablo Moreno)

Jun 20th, 2011
1,005
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