About HanoiTowerTroublesAgain! ¶
하노이의 탑 문제를 변형시킨 문제들 중에도 흥미로운 문제들이 많이 있다. 이 문제는 N개의 기둥과 1부터 무한대까지의 정수가 적혀있는 공에 관한 문제다. 두 공에 적힌 번호의 합이 완전제곱수(어떤 정수를 제곱한 수)가 아니면 그 두 공 사이에는 서로 맞닿아있을 수 없을 만큼 큰 척력이 작용하게 된다.
http://online-judge.uva.es/p/v102/p10276.jpg
공을 한 번에 하나씩, 번호가 커지는 순서로 기둥에 끼우는 게임을 한다(즉 1번을 끼우고 나서 2번을 끼우고, 그리고 나서 3번을 끼우고 하는 식으로 공을 기둥에 끼움). 더 이상 서로 밀어내지 않도록 공을 끼울 수 없게 되면 게임이 끝난다. 게임의 목표는 최대한 많은 개수의 공을 끼우는 것이다. 위에 있는 그림에는 기둥이 네 개인 경우에 최대한 많은 공을 끼운 결과가 나와 있다.
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 |}}
4
25 |}}
Sample Output ¶
{{| 11
337 |}}
337 |}}
풀이 ¶
| 작성자 | 사용언어 | 개발시간 | 코드 |
| 문보창 | C++ | 10분 | HanoiTowerTroublesAgain!/문보창 |
| 황재선 | Java | 50분 | HanoiTowerTroublesAgain!/황재선 |
| 하기웅 | C++ | 원랜 1시간, 문보창 XXX 때문에 말렸음ㅡㅡ; | HanoiTowerTroublesAgain!/하기웅 |
| 이도현 | C++ | Closed Form 구하는 데(1시간 30분), 코딩 5분 | HanoiTowerTroublesAgain!/이도현 |
| 조현태 | C++ | ? | HanoiTowerTroublesAgain!/조현태 |
