시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (하단 참고) | 512 MB | 104 | 26 | 21 | 30.000% |
Albert는 그 동안 모은 n개의 오래된 장난감을 모두 팔아버리기로 했다. 편의상 장난감은 0부터 n-1까지 번호가 붙어있고, i번 장난감의 판매가격은 v[i] 이다. Albert는 한 명의 구매자에게 모든 장난감을 팔아버리고 새로운 장난감을 사고 싶어 하는데, 마침 Alice가 소식을 듣고 모든 장난감을 구매하기로 했다. Alice가 모든 장난감을 사는 대신, 아래와 같은 "묶음 할인"을 받을 수 있도록 요청했다:
항상 Alice의 술수에 손해를 보는 Albert이지만, 장난감을 모두 팔기위해 Alice의 제안을 승낙하는 대신 조건을 하나 추가했다. n개의 장난감 중 번호가 3의 배수인 것 중 하나를 Albert가 임의로 고르면 Alice는 해당 장난감은 판매 가격 그대로 사야하며, 대신 나머지 장난감들에 대해 원하는대로 묶음 할인을 적용할 수 있게 했다. Alice도 잠시 고민을 한 후, 제안을 받아들이기로 했다.
예를 들어, n = 7이고 v = [1 2 3 100 10 20 30] 이라고 하자.
모든 경우를 따져보면, Albert는 당연히 3번 장난감을 팔아야 하고, 이 때 Alice도 최선을 다해 최소한의 가격을 지불하려 한다면 133을 지불하게 된다.
Alice는 항상 꼼꼼하게 모든 경우를 따져보기 때문에, Albert는 당신에게 도움을 요청했다.
입력으로 n과 v가 주어졌을 때, Albert가 어떤 장난감 하나를 임의로 골라 Alice에 팔아야 최대한 많은 돈을 받을 수 있는지 구해보자.
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어진다.
테스트 케이스의 첫 줄에 n이 주어지며 (장난감의 수) 둘째 줄에 n개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 나타내는 정수 두 개를 공백으로 구분하여 각 줄에 출력한다.
첫 수는 Albert가 처음 팔아야하는 장난감의 번호이고 (0이상 n-1이하), 두 번째 수는 이 때 Alice가 지불해야하는 총 금액이다.
총 금액이 같은 답이 여럿 존재하는 경우, 장난감의 번호가 가장 작은 경우를 출력한다.
4 4 5 1 3 2 4 10 8 5 7 7 1 2 3 100 10 20 30 7 1000 1000 1000 1000 1000 1000 1000
0 8 0 22 3 133 0 5000
예제 1: 추가 설명 없음.
예제 2: Albert가 0번 장난감을 먼저 팔면 Alice는 나머지 세 장난감을 묶어 총 10 + (5+7) = 22를 지불한다.
예제 3: 본문에서 다루었다.
예제 4: 답이 여럿 존재하는 경우 Albert가 처음 팔아야 하는 장난감 번호가 작은 것을 출력한다