3717 - 六角幻方(2014决赛题C/C++A组第2题)

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>把 </span><span style="font-family:Arial;color:black;font-size:22pt;">1 2 3 ... 19 </span><span style="font-family:宋体;color:black;font-size:22pt;">共</span><span style="font-family:Arial;color:black;font-size:22pt;">19</span><span style="font-family:宋体;color:black;font-size:22pt;">个整数排列成六角形状，如下：</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>* * *</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp; </span>* * * *</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp; </span>* * * * *</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp; </span>* * * * </span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>* * *</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>要求每个直线上的数字之和必须相等。共有</span><span style="font-family:Arial;color:black;font-size:22pt;">15</span><span style="font-family:宋体;color:black;font-size:22pt;">条直线哦！</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>再给点线索吧！我们预先填好了</span><span style="font-family:Arial;color:black;font-size:22pt;">2</span><span style="font-family:宋体;color:black;font-size:22pt;">个数字，第一行的头两个数字是：</span><span style="font-family:Arial;color:black;font-size:22pt;">15 13</span><span style="font-family:宋体;color:black;font-size:22pt;">，参见图</span><span style="font-family:宋体;color:black;font-size:22pt;">【p1.png】</span><span style="font-family:宋体;color:black;font-size:22pt;">，黄色一行为所求。</span>

<img alt="" src="http://tk.hustoj.com:80/attached/image/20150425/20150425074351_53836.png" /><span style="font-family:宋体;color:black;font-size:22pt;"></span>&nbsp;

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>请你填写出中间一行的</span><span style="font-family:Arial;color:black;font-size:22pt;">5</span><span style="font-family:宋体;color:black;font-size:22pt;">个数字。数字间用空格分开。</span>

<span style="font-size:22pt;"><span>•</span></span><span style="font-family:Arial;color:black;font-size:22pt;"><span>&nbsp;&nbsp;&nbsp; </span>这是一行用空格分开的整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性的文字等）</span>

Input

Output

Examples

Input

Output

Solution C

#include<stdio.h>
int main()
{
	printf("9 6 5 2 16 ");
	return 0;
}

Solution C++

#include <iostream>
#include <cstring>
using namespace std;
#define  N 19
#define  M 5
bool vis[N+1];
int a[16];
bool valid(int t)//判断计算出来的数t是否合法 
{
	if(t>19||t<1) return false; 
	if(vis[t]) return false;//已使用，则不合法。 
	vis[t] =true;//合法，则标记其被使用了 
	return true;//合法 
} 
void perms(int p[],int start) //从数组p中索引号为start的元素开始进行全排列
{
	int i,t;
	if(start==M)
	{
		for(i=0;i<5;i++) 
		{
			a[i] = p[i];
			vis[p[i]] = true;
		}

		t = 38-15-a[0];
		if (valid(t)) a[6] = t;
		else return;
		
		t = 38-10-a[1];
		if (valid(t)) a[10] = t;
		else return;
		
		t = 38-a[6]-a[2];
		if (valid(t)) a[11] = t;
		else return;
		
		t = 38-a[2]-a[3];
		if (valid(t)) a[15] = t;
		else return;
		
		t = 38-a[3]-a[10];
		if (valid(t)) a[14] = t;
		else return;
		
		t = 38-13-a[4]-a[11];
		if (valid(t)) a[7] = t;
		else return;
		
		t = 38-a[0]-a[1]-a[4];
		if (valid(t)) a[5] = t;
		else return;
		
		t = 38-a[0]-a[7]-a[15];
		if (valid(t)) a[12] = t;
		else return;
		
		t = 38-13-a[5]-a[14];
		if (valid(t)) a[9] = t;
		else return;
		
		t = 38-a[11]-a[12]-a[14];
		if (valid(t)) a[13] = t;
		else return;
		
		t = 38-a[6]-a[7]-a[9]-a[10];
		if (valid(t)) a[8] = t;
		else return;
		
		//if(15+a[4]+a[8]+a[13]+a[3]!=38) return;//这三行可不判断 
		//if(10+a[5]+a[8]+a[12]+a[2]!=38) return;
		//if(a[1]+a[9]+a[13]+a[15]!=38) return;
		
		for(i=6;i<=10;i++)
			cout<<a[i]<<" ";
		return;
	}
	for(i=start;i<N;i++) 
	{
		swap(p[i],p[start]);
		perms(p,start+1);
		memset(vis,false,sizeof(vis));//
		vis[10] = vis[13] = vis[15]=true;//
		swap(p[start],p[i]);
	}
}
int main()
{
	int p[N];
	for(int i=0;i<N;i++) 
		p[i]=i+1;
	vis[10] = vis[13] = vis[15]=true;
	perms(p,0);
 	return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题