Project-Euler/Problem44.cpp at master · krishnaanaril/Project-Euler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
    Krishna Mohan
    Project Euler - Problem 44
    Date: 3/24/2015
*/
#include <bits/stdc++.h>

using namespace std;

#define fo(i, n) for(int (i)=0;(i)<(n); (i)++)
#define MAX 100000001
#define pb push_back


bitset<MAX> isPent;
vector<int> pents;

void init()
{
    isPent.reset();
    int tn, i=1;
    while(true)
    {
        tn=(i*(3*i-1))/2;
        if(tn>=MAX)
            break;
        isPent[tn]=1;
        pents.pb(tn);
        i++;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    init();
    int sz=pents.size();
    int s, d, minVal=INT_MAX;
    for(int i=0;i<sz-1;i++)
    {
        for(int j=i+1;j<sz;j++)
        {
            s=pents[i]+pents[j];
            d=abs(pents[i]-pents[j]);
            if(s>=MAX || d>=MAX)
                break;
            if(isPent[s] && isPent[d])
            {
                cout<<"D: "<<d<<endl;
                minVal=min(minVal, d);
            }
        }
    }
    cout<<"Ans: "<<minVal<<endl;
    return 0;
}