10276 - Hanoi Tower Troubles Again!(思维,模拟)
People stopped moving discs from peg to peg after they know the number of steps needed to complete the entire task. But on the other hand, they didn't not stopped thinking about similar puzzles with the Hanoi Tower. Mr.S invented a little game on it. The game consists of N pegs and a LOT of balls. The balls are numbered 1,2,3... The balls look ordinary, but they are actually magic. If the sum of the numbers on two balls is NOT a square number, they will push each other with a great force when they're too closed, so they can NEVER be put together touching each other.
The player should place one ball on the top of a peg at a time. He should first try ball 1, then ball 2, then ball 3... If he fails to do so, the game ends. Help the player to place as many balls as possible. You may take a look at the picture above, since it shows us a best result for 4 pegs.
Input
The first line of the input contains a single integer T, indicating the number of test cases. (1<=T<=50) Each test case contains a single integer N(1<=N<=50), indicating the number of pegs available.
Output
For each test case in the input print a line containing an integer indicating the maximal number of balls that can be placed. Print -1 if an infinite number of balls can be placed.
Sample Input
2
4
25
Sample Output
11
337
思路: 定义一个数组用来储存柱子上的数字,如果数字满足条件则a[i] = num 否则 i++
AC代码:
1 #include<iostream>
2 #include<string.h>
3 #include<math.h>
4 using namespace std;
5
6 int main()
7 {
8 int a[50], b[50];
9 int times, peg, temp;
10 int n = 1;
11 int num = 1;
12 int i = 0, j;
13 cin >> times;
14 while(times--)
15 {
16 cin >> peg;
17 memset(a, 0, sizeof(a));
18 while(1)
19 {
20 if(i == peg)
21 {
22 cout << num - 1 << endl;
23 num = 1, i = 0;
24 break;
25 }
26 if(a[i] == 0)
27 {
28 a[i] = num++;
29 i = 0;
30 continue;
31 }
32 else
33 {
34 j = (int)sqrt(a[i] + num);
35 if(j * j == (a[i] + num))
36 {
37 a[i] = num++;
38 i = 0;
39 continue;
40 }
41 else
42 {
43 i++;
44 }
45 }
46 }
47 }
48
49 return 0;
50 }
最新文章
- SVNKit支持SSH连接
- <;<;<; ajax在jsp中对于https跨域不能访问
- mysql存储过程中 乱码问题解决办法
- bin/sh^M: bad interpreter: No such file or directory解决
- java程序保护如何知识产权,特别提供一个java 开发的java 源代码级的混淆器
- POJ - 1978 Hanafuda Shuffle
- 坚持不懈之linux haproxy的配置文件关键字查询手册
- Ubuntu系统的安装
- Learning Java 8 Syntax (Java in a Nutshell 6th)
- Entity Framework Core 2.0 新特性
- 动态代理:JDK动态代理和CGLIB代理的区别
- 探索从 MVC 到 MVVM + Flux 架构模式的转变
- Ubuntu 18.04编译AOSP源码
- Linux拉你入门
- ZZNU 2095 : 我只看看不写题
- netcore 2.0 部署 到iis
- python读写剪贴板
- android kl文件
- css中实现ul两端的li对齐外面边缘
- Android 桌面Widget开发要点(时间日期Widget)