joj 1031 Hanoi Tower Troubles Again!문제 풀이 보고서

 1031: Hanoi Tower Troubles Again!

Result
TIME Limit
MEMORY Limit
Run Times
AC Times
JUDGE
3s
8192K
1034
606
Standard
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

이 문제는 인터넷에 많은 소들이 이분도의 사상으로 풀었는데, 으...안타깝게도 나는 초보자이기 때문에 최저급의 규칙을 찾는 생각으로 풀었을 뿐이다. 해결하고 보니 이 문제가 규칙을 찾으면 사실은 매우 간단하다. N=1시 결과는 1, N=2시 결과는 3이고, 이후에 N=7시까지 결과는 7, 11, 17, 23, 31이다. 이때 규칙은 이미 드러났다. N=1시와 N=2는 결과 차이이다. 앞으로 결과는 4, 4, 6, 6, 8, 8의 차이가 난다...그래서 이 규칙에 따라 문제의 답안을 내놓을 수 있다.
코드:
언어: c++
#include using namespace std; int main() { int n,t; cin>>t; for(int i=1;i<=t;++i) { cin>>n; if(n==1) cout<<1<