아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

세 아들

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

요약
정수 n을 a < b < c인 세 양의 정수로 나누어 제곱의 합이 최소가 되도록 하는 a, b, c를 구한다.
난이도

보통10점 중 5점

유형
수학, 그리디, 구현
정답자
아직 제출이 없습니다

문제

플랫란디아 왕의 영지에는 길이가 nn킬로미터인 직선 도로가 있고, 도로의 한쪽에는 거대한 숲이 있다. 플랫란디아 왕은 자연 보호 사상에 감명을 받아 숲을 보호구역으로 만들기로 했다. 하지만 아들들이 반대했다. 그들은 이 땅을 상속받고 싶어 했다.

왕에게는 세 아들이 있다: 막내, 둘째, 장남. 왕은 아들들에게 상속으로 남겨 줄 숲의 구역은 보호구역에 포함되지 않는다고 정했다. 유언장을 작성할 때 왕은 구역들이 다음 조건을 만족하기를 원한다:

  • 각 구역은 정사각형이어야 하고, 한 변의 길이는 양의 정수로 표현되어야 한다. 각 정사각형의 한 변은 도로 위에 놓여야 한다. 구역들의 크기를 a×aa \times a, b×bb \times b, c×cc \times c라 하자.
  • 정사각형들의 변은 도로를 완전히 덮어야 한다: a+b+ca + b + c의 값이 nn과 같아야 한다.
  • 막내 아들의 구역은 둘째 아들의 구역보다 엄격히 작아야 하고, 둘째 아들의 구역은 다시 장남의 구역보다 엄격히 작아야 한다. 즉 a<b<ca < b < c가 성립해야 한다.
  • 구역들의 넓이의 합 a2+b2+c2a^2 + b^2 + c^2이 최소가 되어야 한다.

주어진 도로의 길이에 따라 왕의 아들들에게 나누어 줄 구역의 크기를 구하는 프로그램을 작성해야 한다.

입력

입력 파일에는 정수 nn이 하나 주어진다 (6≤n≤1096 \le n \le 10^9).

출력

출력 파일에는 공백으로 구분된 세 개의 양의 정수 aa, bb, cc를 출력한다. 이는 각각 막내, 둘째, 장남 아들에게 나누어 줄 구역의 한 변의 길이이다. 최적의 해가 여러 개라면 아무거나 출력해도 된다.

힌트

예제1

  1. 예제 1

    입력
    6
    
    예상 출력
    1 2 3