끔찍한 수열
시간 제한2초메모리 제한128 MB
합이 M인 수열 중 곱이 최대인 경우와 곱이 M인 수열 중 합이 최소인 경우 각각의 최대, 최소 길이를 구하는 문제입니다.
문제
양의 정수로 이루어진 수열 <a_1, a_2, ..., a_k>의 길이는 수열에 들어 있는 정수의 개수 k이다. 양의 정수 M이 주어질 때, 다음 두 문제를 각각 생각한다.
- 문제 A: 합
a_1 + a_2 + ... + a_n = M을 만족하는 양의 정수 수열 중에서 곱a_1 × a_2 × ... × a_n이 최대가 되는 수열을 찾는다. 최대 곱을 만드는 수열 중 길이가 서로 다른 수열이 여러 개라면, 가능한 길이n의 최댓값과 최솟값을 모두 구한다. - 문제 B: 곱
a_1 × a_2 × ... × a_m = M을 만족하는 양의 정수 수열 중에서 합a_1 + a_2 + ... + a_m이 최소가 되는 수열을 찾는다. 최소 합을 만드는 수열 중 길이가 서로 다른 수열이 여러 개라면, 가능한 길이m의 최댓값과 최솟값을 모두 구한다.
문제 A에서 가능한 길이의 최댓값과 최솟값, 문제 B에서 가능한 길이의 최댓값과 최솟값을 출력하는 프로그램을 작성하라.
입력
첫째 줄에 정수 M이 주어진다. (1 ≤ M ≤ 1,000,000)
출력
첫째 줄에 네 정수를 공백으로 구분해 출력한다. 순서대로 문제 A에서 가능한 최대 길이 n, 문제 A에서 가능한 최소 길이 n, 문제 B에서 가능한 최대 길이 m, 문제 B에서 가능한 최소 길이 m이다.