연습문제

[한양대 HCPC 2023] Phi Squared

난이도
Lv. 3
제출
1,265 명
참가자
320 명
정답률
22.62 %
지원 언어
C#
C
C++
Java
Python
JavaScript
Kotlin
Swift
Go
Rust
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 1초 1024MB
JavaScript 5초 1024MB
C 1초 1024MB
Java 3초 1024MB
Python 5초 1024MB
Kotlin 3초 1024MB
Swift 1초 1024MB
C# 3초 1024MB
Go 1초 1024MB
Rust 1초 1024MB

선아는 최근에 어떤 미생물을 연구하고 있다. 선아는 연구 과정에서 이 미생물 여러 마리를 한 줄로 나열하면 미생물이 한 마리만 남을 때까지 다음 규칙들에 따라 미생물들이 서로 흡수한다는 사실을 알아냈다.


1. 하루에 한 번 줄의 맨 앞에 있는 미생물부터 각 미생물은 차례대로 인접한 미생물 중 자신보다 크기가 작거나 같은 것들을 전부 흡수한다. 다른 미생물을 흡수한 경우, 미생물의 크기는 흡수한 미생물의 크기의 합만큼 커진다.


2. 흡수당한 미생물은 사라지며 행동할 수 없다. 즉, 의 크기를 가지는 세 마리의 미생물들이 있는 경우 는 자신의 차례가 오기 전에 에게 흡수당하기 때문에 하루가 지난 후 남아있는 미생물들의 크기는 이 된다.


3. 흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다. 즉, 의 크기를 가지는 세 마리의 미생물들이 있고 의 차례인 경우 는 만 흡수한다. 가 을 흡수해서 이 된 후 같은 날 를 흡수하는 행동은 불가능하다. 따라서 하루가 지난 후 남아있는 미생물들의 크기는 가 된다.


선아에게는 이 미생물이 마리 있다. 이 마리의 미생물들이 한 줄로 나열되었을 때 마지막에 남는 미생물의 최종 크기와 초기 위치를 찾는 프로그램을 작성해 보자.

제약조건

각 미생물의 초기 크기는 1 이상 N 이하의 정수이다. 또한 같은 초기 크기를 가지는 두 미생물은 존재하지 않는다.

입력형식

첫 번째 줄에 미생물들의 수 이 주어진다.

두 번째 줄에 미생물들의 초기 크기를 나타내는 개의 정수 가 공백으로 구분되어 주어진다. 는 번째 미생물의 초기 크기를 나타낸다.

출력형식

첫 번째 줄에 마지막에 남는 미생물의 최종 크기를 출력한다.

두 번째 줄에 그 미생물의 초기 위치를 출력한다.

입력예제1

5
4 1 3 2 5
출력예제1

15
5

다음과 같은 순서로 미생물들이 합쳐지게 됩니다. (1, 3)은 초기 위치가 1인 미생물의 현재 크기가 3임을 의미합니다.

초기 상태: (1, 4) (2, 1) (3, 3) (4, 2) (5, 5)

1일 후: (1, 5) (5, 10)

2일 후: (5, 15)

따라서 답은 15 5 입니다.

입력예제2

3
1 2 3
출력예제2

6
3

목록