首页 > 代码库 > Project Euler problem 68

Project Euler problem 68

题意需要注意的一点就是,

序列是从外层最小的那个位置顺时针转一圈得来的。并且要求10在内圈

所以,这题暴力的话,假定最上面那个点一定是第一个点,算下和更新下就行。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <map>
#define MAXN 111
#define MAXM 55555
#define INF 1000000007
using namespace std;
int a[12];
int sum[6];
string ans, tmp;
int main()
{
    int n = 10;
    int first = 1;
    ans = "", tmp = "";
    for(int i = 1; i <= n; i++) a[i] = i;
    do {
        int pos = 1;
        for(int i = 1; i <= 5; i++) {
            if(a[i] < a[pos]) pos = i;
            int z = i + 6;
            if(z > 10) z = z - 5;
            sum[i] = a[i] + a[i + 5] + a[z];
        }
        if(pos != 1) continue;
        int flag = 1;
        for(int i = 2; i <= 5; i++)
            if(sum[i] != sum[i - 1]) flag = 0;
        if(sum[1] != sum[5]) flag = 0;
        for(int i = 6; i <= 10; i++) {
            if(a[i] == 10) flag = 0;
        }
        tmp = "";
        if(flag) {
            for(int i = 1; i <= 5; i++) {
                int z = i + 6;
                if(z > 10) z = z - 5;
                tmp += (a[i] + 'a');
                tmp += (a[i + 5] + 'a');
                tmp += (a[z] + 'a');
            }
            if(!first) {
                if(ans < tmp) ans = tmp;
            } else {
                ans = tmp;
                first = 1;
            }

        }
    }while(next_permutation(a + 1, a + n + 1));
    for(int i = 0; i < 15; i++) printf("%d", ans[i] - 'a');
	return 0;
}


Project Euler problem 68