首页 > 其他分享 >UVa 524 Prime Ring Problem (数论&DFS)

UVa 524 Prime Ring Problem (数论&DFS)

时间:2023-04-12 11:38:53浏览次数:47  
标签:Prime circles int 50 DFS 524 numbers circle include


524 - Prime Ring Problem

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=465

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 

 into each circle separately, and the sum of numbers in two adjacent circles should be a prime.



Note: the number of first circle should always be 1.

Input

n (0 < n <= 16)

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.

You are to write a program that completes above process.

Sample Input


68


Sample Output


Case 1:1 4 3 2 5 61 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2



完整代码:

/*0.268s*/

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n, A[50], isp[50], vis[50];

int is_prime(int x)
{
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)
			return 0;
	return 1;
}

void dfs(int cur)
{
	if (cur == n && isp[A[0] + A[n - 1]])///递归边界,别忘了测试第一个数和最后一个数
	{
		printf("%d", A[0]);
		for (int i = 1; i < n; i++)
			printf(" %d", A[i]);///打印方案
		putchar('\n');
	}
	else
	{
		for (int i = 2; i <= n; i++)///尝试放置每个数i
			if (!vis[i] && isp[i + A[cur - 1]])///如果i没有用过,并且与前一个数之和为素数
			{
				A[cur] = i;
				vis[i] = 1;///使用此数并传入后续计算
				dfs(cur + 1);
				vis[i] = 0;///撤销此数的使用
			}
	}
}

int main(void)
{
	int k = 0;
	int first = 0;
	while (~scanf("%d", &n))
	{
		if (first)
			putchar('\n');
		printf("Case %d:\n", ++k);
		memset(A, 0, sizeof(A));
		memset(isp, 0, sizeof(isp));
		for (int i = 2; i <= n * 2; i++)
			isp[i] = is_prime(i);
		memset(vis, 0, sizeof(vis));
		A[0] = 1;
		dfs(1);
		first = 1;
	}
	return 0;
}




标签:Prime,circles,int,50,DFS,524,numbers,circle,include
From: https://blog.51cto.com/u_5535544/6185325

相关文章

  • UVa 10004 Bicoloring (DFS&二分图)
    10004-BicoloringTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=945In1976the``FourColorMapTheorem"wasprovenwiththeassistanceofacomput......
  • Semi-prime H-numbers UVA - 11105
     所有形如4n+1(n为非负整数)的数叫H数。定义1是唯一的单位H数,H素数是指本身不是1,且不能写成两个不是1的H数的乘积。H-半素数是指能写成两个H素数的乘积的H数(这两个数可以相同也可以不同)。 例如,25是H-半素数,但125不是。输入一个H数h(h≤1000001),输出1~h之间有多少个H-半素数。......
  • CF698F Coprime Permutation 题解
    题意给定一个未填满的数组\(p\),求有多少种\(1\simn\)的排列\(p\)满足对于任意\(i<j\),都有\([\gcd(i,j)=1]=[\gcd(p_i,p_j)=1]\),答案对\(10^9+7\)取模。题解部分参考这篇题解(感觉这篇题解应该是目前为止最详细的吧)。记\(P\)为\([1,n]\)中所有素数与\(1\)构成......
  • dfs入门习题
    主要记录一下个人遇见过的一些dfs的一些入门题目。有需要的可以跟着题单往下做。题单根据自己的刷题不定时更新。 第一题:https://codeforces.com/problemset/problem/510/B一道比较经典的dfs模板题。需要注意一下记忆化搜索。 **点击查看代码......
  • Sum of Consecutive Prime Numbers UVA - 121
     #include<iostream>#include<cstring>#include<cmath>#include<algorithm>usingnamespacestd;constintM=1e4+33;intb[M],c[M],tot;ints[M];voidinit(inttop){memset(b,1,sizeofb);b[1]=0;inti,j;......
  • Sum of Different Primes UVA - 1213
     选择K个质数,使它们的和等于N。问有多少种方案?例如,n=24,k=2时有3种方案:5+19=7+17=11+13=24 #include<iostream>#include<cstring>#include<cmath>#include<algorithm>usingnamespacestd;constintM=1e6+33;intb[M],c[M],tot;intn,m,f[2000][20];......
  • c++Primer 14 重载运算符与类型转换
    除了重载的函数调用运算符operator()之外,其他重载运算符不能含有默认实参。      泛型算法中调用的几元谓词是看函数对象的调用运算符的参数个数。而不是构造函数的参数个数。    转换构造函数只能有一个参数,如果他有多个参数,就无法判断是将哪个参数转......
  • Leetcode(剑指offer专项训练)——DFS/BFS专项(2)
    课程顺序题目现在总共有numCourses 门课需要选,记为 0 到 numCourses-1。给定一个数组 prerequisites,它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i]=[ai,bi] 表示想要学习课程ai ,需要先完成课程bi 。请根据给出的......
  • HJ67_24点游戏算法_多维递归_DFS(深度优先搜索)
    思路:多维递归,深度有限遍历加减乘除四种情况。知识点:1、多维递归不能对传递的变量进行修改,否则无法回溯。应该传递一个新地址的变量,如代码所示,传递切片的列表,不修改列表  2、搜索遗漏。两括号比如((9-4)-1)*6选取任意一个数作为第一个运算数与24运算,不能找出所有24点的计算......
  • C++primer第五章
    5.1 简单语句表达式语句的作用是执行表达式并丢弃掉求值结果。最简单h的语句是空语句,空语句中只有一个单独的分号。复合语句是指用花括号括起来的语句和声明序列,复合语句也被称为块。一个块就是一个作用域。5.2 语句作用域定义在控制结构内的变量作......