ProjectEuler/P61.cpp at master · AbhishekYMCA/ProjectEuler · 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<fstream>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<iomanip>
#define MAXN 9999
#define LL long long
#define eps 1e-6
#define inf 0x3f3f3f3f
using namespace std;

typedef struct
{
    int index, val;
} node;
node p[7][100][100];
node rec[7];
bool vis[7];

int Formulae(int p, int n)
{
    switch(p)
    {
    case 1:
        return n * (n + 1) / 2;
    case 2:
        return n * n;
    case 3:
        return n * (3 * n - 1) / 2;
    case 4:
        return n * (2 * n - 1);
    case 5:
        return n * (5 * n - 3) / 2;
    case 6:
        return n * (3 * n - 2);
    default:
        printf("impossible\n");
        return 0;
    }
}

bool check(int a, int b)
{
    if(6 == a)
        return true;
    if(6 == b)
        return check(a + 1, a + 2);
    if(rec[a].index == rec[b].index)
        return false;
    return check(a, b + 1);
}
bool isSuit(int pos, int c)
{
    vis[pos] = true;
    if(c == 6)
    {
        for(int i = 1; i <= p[pos][rec[pos].val][0].val; i++)
            if(p[pos][rec[pos].val][i].val == rec[1].val && check(1, 2))
            {
                rec[pos].index = p[pos][rec[pos].val][i].index;
                return true;
            }
        vis[pos] = false;
        return false;
    }
    for(int i = 1; i <= p[pos][rec[pos].val][0].val; i++)
    {
        rec[pos].index = p[pos][rec[pos].val][i].index;
        for(int j = 1; j <= 6; j++)
            if(!vis[j])
        {
            rec[j].val = p[pos][rec[pos].val][i].val;
            if(isSuit(j, c + 1))
             return true;
        }
    }
    vis[pos] = false;
    return false;
}

int main()
{
    double duration;
    clock_t start = clock();
    int temp;
    for(int i = 1; i <= 6; i++)
        for(int j = 1; ; j++)
        {
            temp = Formulae(i, j);
            if(temp < 1000)
                continue;
            if(temp > MAXN)
                break;
            if(temp % 100 >= 10)
            {
                p[i][temp / 100][++p[i][temp / 100][0].val].val = temp % 100;
                p[i][temp / 100][p[i][temp / 100][0].val].index = j;
            }
        }
    for(rec[1].val = 10; rec[1].val < 100; rec[1].val++)
        if(isSuit(1, 1))
            break;
    int sum = 0;
    for(int i = 1; i <= 6; i++)
        sum += Formulae(i, rec[i].index);
    printf("%d\n", sum);
    duration = (double)(clock() - start) / CLOCKS_PER_SEC;
    printf("time cost: %lf\n", duration);
    return 0;
}