KOI 전국 2006 중1- 수열 > 문제은행 : 정보올림피아드&알고리즘




1453 : 수열

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
7 회   
시도횟수
16 회   

문제

우리는 양의 정수들이 나열된 수열 을 구하는 다음과 같은 두 문제를 풀려고 한다. 수열의 길이는 수열에 포함된 정수들의 개수 n이라고 정의한다.




문제 A: 양의 정수 M이 주어질 때, a1+a2+...+an=M을 만족하면서 a1*a2*...an의 값이 가장 크게 되는 수열 을 구하시오.
          단, a1*a2*...*an의 값이 가장 크게 되는 서로 다른 길이의 수열이 두 개 이상 존재할 경우, 수열의 길이 n이 최대인 수열을 구하시오.




문제 B: 양의 정수 M이 주어질 때, a1*a2*...*am=M을 만족하면서 a1+a2+...+am의 값이 가장 작게 되는 수열 을 구하시오. 

         단, a1+a2+...+a의 값이 가장 작게 되는 서로 다른 길이의 수열이 두 개 이상 존재할 경우, 수열의 길이 m이 최소인 수열을 구한다.

 

문제 A에서 구한 수열의 길이 n과 문제 B에서 구한 수열의 길이 m을 출력하는 프로그램을 작성하시오.

 

예를 들어, M=6이면, 문제 A에서 구한 수열은 <3,3>이므로 이 수열의 길이는 2이고, 문제 B에서 구한 수열은 <2,3>이므로 이 수열의 길이는 2이다.


입력형식

첫째 줄에 정수 M이 주어진다. 1<=M<=1,000,000 이다.

출력형식

첫째 줄에 문제 A에서 구한 수열의 길이 n과 문제 B에서 구한 수열의 길이 m을 한 개의 빈칸을 사이에 두고 차례대로 출력한다.

입력 예

6

출력 예

2 2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP