시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 198 99 19 44.186%

문제

유닉스 계열의 운영체제에서는 파일을 읽기 위해 read()라는 시스템 함수(System Call)을 제공한다. 이 함수는 우리가 버퍼를 전달해주면 그 크기 만큼 파일을 읽어서 기록해준다. 만약 파일이 너무 크다면 read() 함수를 여러 번 호출해야 모두 읽을 수 있을 것이다.

민규는 리눅스에서 여러 개의 파일을 읽는 프로그램을 구현하려고 한다. 우리가 아는 사실은 버퍼의 크기가 K바이트일때 read() 함수가 수행되는데 걸리는 시간은 (T + K)라는 것이다. 여기서 T는 함수를 한 번 호출하는데 고정적으로 걸리는 시간이다. 이때 주의해야 할 점은 read()함수의 수행 시간은 버퍼의 크기에 의해서만 결정된다는 것이다. 예를 들어 버퍼의 크기가 10바이트라면 3바이트를 읽건 7바이트를 읽건 상관없이 (T + 10)의 시간이 걸린다.

위의 결과를 분석해보면 버퍼의 크기에 따라 전체 파일을 읽는데 걸리는 시간이 줄어들 수 있다는 것을 알 수 있다. 프로그래밍이 익숙치 않은 민규는 버퍼의 크기를 고정해놓고 코드를 짜기로 결정했는데, 버퍼의 크기를 얼마나 정해야 프로그램의 수행 시간을 최소화할 수 있을까?

입력

첫 줄에는 파일의 갯수 N이 주어진다. 두 번째 줄에는 각 파일의 크기를 나타내는 N개의 자연수 Fi가 주어진다. 이때 파일의 크기는 바이트 단위이다. 마지막 줄에는 T가 주어진다.

출력

주어진 파일을 읽는데 걸리는 가장 짧은 시간과 이를 달성하기 위해 지정해줘야 하는 버퍼의 크기를 출력한다. 만약 해당 시간에 가능한 경우가 여러 가지라면 버퍼의 크기가 가장 작은 경우를 출력한다.

Small (50점)

  • 1 ≤ N ≤ 1,000
  • 1 ≤ Fi ≤ 1,000
  • 0 ≤ T ≤ 500

Large (200점)

  • 1 ≤ N ≤ 20,000
  • 1 ≤ Fi ≤ 500,000
  • 0 ≤ T ≤ 10,000

예제 입력 1

3
1 2 3
1

예제 출력 1

12 1

예제 입력 2

4
10 20 40 40
10

예제 출력 2

180 20

예제 입력 3

5
155 116 19 136 21
0

예제 출력 3

447 1

힌트

Linux는 대표적인 유닉스 계열의 운영체제이다. 우리가 잘 아는 macOS 또한 유닉스 계열이다. 이외에도 FreeBSD, NetBSD, Solaris 등이 있다.

출처

University > 아주대학교 > 2018 Ajou Porgramming Contest: Division 1 F번