E D R , A S I H C RSS

Hanoi Tower Troubles Again!

원문보기
----
인기도:B(A,B,C), 성공률:높음(낮음,보통,높음), 레벨:3(1~4)

About HanoiTowerTroublesAgain!

하노이의 탑 문제를 변형시킨 문제들 중에도 흥미로운 문제들이 많이 있다. 이 문제는 N개의 기둥과 1부터 무한대까지의 정수가 적혀있는 공에 관한 문제다. 두 공에 적힌 번호의 합이 완전제곱수(어떤 정수를 제곱한 수)가 아니면 그 두 공 사이에는 서로 맞닿아있을 수 없을 만큼 큰 척력이 작용하게 된다.
http://online-judge.uva.es/p/v102/p10276.jpg
공을 한 번에 하나씩, 번호가 커지는 순서로 기둥에 끼우는 게임을 한다(즉 1번을 끼우고 나서 2번을 끼우고, 그리고 나서 3번을 끼우고 하는 식으로 공을 기둥에 끼움). 더 이상 서로 밀어내지 않도록 공을 끼울 수 없게 되면 게임이 끝난다. 게임의 목표는 최대한 많은 개수의 공을 끼우는 것이다. 위에 있는 그림에는 기둥이 네 개인 경우에 최대한 많은 공을 끼운 결과가 나와 있다.

Input

첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 T(1≤T≤50)가 입력된다. 각 테스트 케이스마다 쓸 수 있는 기둥의 개수를 나타내는 정수 N(1≤N≤50)이 입력된다.

Output

각 테스트 케이스에 대해 기둥에 끼울 수 있는 공의 최대 개수를 나타내는 정수를 출력한다. 끼울수 있는 공의 개수가 무한대면 '-1'을 출력한다.

Sample Input

{{| 2
4
25 |}}

Sample Output

{{| 11
337 |}}

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 10분 HanoiTowerTroublesAgain!/문보창
황재선 Java 50분 HanoiTowerTroublesAgain!/황재선
하기웅 C++ 원랜 1시간, 문보창 XXX 때문에 말렸음ㅡㅡ; HanoiTowerTroublesAgain!/하기웅
이도현 C++ Closed Form 구하는 데(1시간 30분), 코딩 5분 HanoiTowerTroublesAgain!/이도현
조현태 C++ ? HanoiTowerTroublesAgain!/조현태

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1893 sec