Informatica Online Judge

  공 모으기 [0854 / 0356]

Time Limit(Test case) : 3000 (ms)
Number of users who solved : 2   Total Tried : 100


The Champion of this Problem (C++) : sutekine - 73ms / 937byte
My Best Submission (C++) : N/A

[]

Background

이번이 마지막 공 게임이다.

경곽이는 1부터 n까지의 번호가 매겨진 공바구니를 n개 가지고 있다.

각 바구니에는 a1, a2, ... , an 개의 공들이 들어있다. ak는 k번째 바구니에 들어있는 공의 수를 나타낸다.

이 게임의 목적은 모든 바구니의 공들을 2개의 바구니로 모으는 것이다.

공을 바구니로 옮길 때에는 다음 규칙을 따라야 한다.

- 먼저 2개의 바구니 i와 j를 고른다.
- 만약 ai >= aj라면 i번 바구니에서 공 aj개를 j바구니로 옮길 수 있다.
- 만약 ai <= aj라면 j번 바구니에서 공 ai개를 i바구니로 옮길 수 있다.

위와 같은 옮기기 작업을 c번 해서 모든 공을 2개의 바구니로 모을 수 있도록 경곽이를 도와주자.

단, c의 최솟값을 찾을 필요는 없다. 하지만 c가 1 000 000을 초과해서도 안된다.

Input

첫 번째 줄에 바구니의 수 n이 입력된다.
다음 줄에 각 바구니의 공의 갯수 a1, a2, .. an이 공백으로 구분되어 입력된다.

입력값들의 정의역은 다음과 같다.

1 <= n <= 1000
a1 + a2 + ... an <= 1 000 000

(단, 모든 값은 음이아닌 정수이다.)

Output

두 바구니로 모으는데 필요한 횟수 c를 첫째 줄에 출력한다.
두 번째 줄부터 c줄에 걸쳐서 옮겨질 바구니와 옮길 바구니의 번호를 공백으로 구분하여 출력한다.
단, 옮길 수 없는 경우라면 -1을 출력한다.

단, c는 1 000 000을 초과할 수 없다.

IO Example

입력
3
3 6 9

출력
2
2 3
1 3

입력2
3
0 1 0

출력2
-1

입력3
4
0 1 1 0

출력3
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]