피타고라스 세 쌍

면접 대비

시간 제한1초메모리 제한128 MB

요약
서로 다른 양의 정수 50개 이하가 주어질 때, 집합 안에 있는 피타고라스 삼조 x<y<z를 모두 사전순으로 나열하고, 없으면 없다고 출력한다.
난이도

보통10점 중 4점

유형
해시맵, 수학, 정렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

어벤져스가 로키의 은신처 중 하나에 도착했지만, 잠긴 키패드가 앞을 가로막고 있습니다. 토르는 그 열쇠가 근처 벽에 적힌 수열에서 고른 세 수로 이루어진 피타고라스 세 쌍이라고 확신합니다. 이 세 쌍을 모두 찾아 주세요.

서로 다른 세 정수의 집합 {x,y,z}\{x, y, z\}(x<y<zx < y < z)가 x2+y2=z2x^2 + y^2 = z^2을 만족하면 이를 피타고라스 세 쌍이라고 부릅니다. 예를 들어 {3,4,5}\{3, 4, 5\}는 피타고라스 세 쌍이지만 {1,2,3}\{1, 2, 3\}은 아닙니다.

서로 다른 양의 정수로 이루어진 수열 x1,x2,…,xnx_1, x_2, \dots, x_n이 주어질 때, 이 수열의 원소들로 만들 수 있는 모든 피타고라스 세 쌍을 찾으세요.

입력

첫째 줄에 테스트 케이스의 수 TT(T<100T < 100)가 주어집니다.

이어지는 TT개의 각 줄에 하나의 테스트 케이스가 주어집니다. 각 줄은 수열의 길이 nn(3≤n≤503 \le n \le 50)으로 시작하고, 그 뒤에 수열을 이루는 서로 다른 양의 정수 nn개가 임의의 순서로 주어집니다. 각 수는 2242^{24}을 넘지 않습니다.

출력

각 테스트 케이스의 답을 입력과 같은 순서로 한 줄씩 출력합니다.

수열에 피타고라스 세 쌍이 하나 이상 있으면, 지정된 키워드 다음에 공백 두 칸을 두고 모든 세 쌍을 출력합니다. 각 세 쌍은 {x y z} 형식으로 쓰며(x<y<zx < y < z, 숫자 사이는 공백 한 칸), 서로 다른 세 쌍 사이에는 공백 한 칸을 둡니다. 세 쌍은 xx, 그다음 yy, 그다음 zz의 오름차순으로 나열합니다. 출력 줄은 정확히 다음 형식입니다.

Found Pythogorean triples:  {x y z} {x y z} ...

수열에 피타고라스 세 쌍이 하나도 없으면 다음을 정확히 출력합니다.

No Pythogorean triples found in the sequence.

출력 키워드는 위와 똑같이 Pythogorean으로 표기합니다.

예제1

  1. 예제 1

    입력
    4 
    6 6 5 4 3 2 1 
    3 3000000 5000000 4000000
    5 13 12 3 4 5
    6 1 2 4 8 16 32
    
    예상 출력
    Found Pythogorean triples:  {3 4 5}
    Found Pythogorean triples:  {3000000 4000000 5000000}
    Found Pythogorean triples:  {3 4 5} {5 12 13}
    No Pythogorean triples found in the sequence.