| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 24 | 13 | 10 | 50.000% |
Albert는 "0-9" 사이의 숫자가 적힌 카드 $M$ 장과 '+' (덧셈 기호)가 적힌 카드를 이용하여 덧셈 놀이를 하고 있다. 편의상 길이가 $M$인 정수문자열 $X$를 이용하여 좌측부터 우측으로 놓인 숫자 카드들을 표현하자.
예를 들어 아래 그림처럼 $M = 4$ 장의 카드를 나열한 경우 $X = $"2024" 로 표현할 수 있다. Albert는 항상 인접한 숫자 카드 쌍 사이에 공백을 충분히 두어 덧셈 카드를 넣을 수 있도록 배열하는데, 아래 그림에서 이러한 "빈 칸"이 총 $M-1 = 3$ 개 임을 확인할 수 있다.
Albert는 이제 각 빈칸에 덧셈 기호를 넣을지 말지 정하여 총 2ドル^{M-1} = 8$ 가지 다른 덧셈 공식을 얻을 수 있고, 아래 규칙에 따라 이 공식들을 정렬해보았다:
이 방법으로 위와 같은 예제에서 8개의 공식을 정렬한 결과는 아래와 같다. 가령 3번째 공식과 4번째 공식의 첫 번째 빈칸은 서로 같지만, 두 번째 빈칸이 최초로 다른데 3번째 공식에는 덧셈 카드가 있으므로 정렬시 앞선다. 1번째와 2번째 공식도 같은 이유로 정렬시 순서가 정해진다.
Albert의 놀이를 지켜보던 Bob은 아래와 같은 문제를 냈다:
가령 위의 예제에서 $N = 4$이고 $V = [1, 3, 5, 7]$인 경우:
입력으로 $N,ドル $X,ドル 그리고 $V$가 주어졌을 때, Albert를 도와 $W_s, W_p$ 값을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어지는데 첫 번째 줄에 $N$과 정수 문자열 $X$가 공백으로 구분되어 주어진다. 이 때 문자열 $X$의 길이인 $M$은 유추 가능하므로 입력으로 주어지지 않는다. 둘째 줄에는 배열 $V$의 원소 $N$개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답인 $W_s, W_p$를 공백으로 구분하여 각 줄에 출력한다.
5 4 123 1 2 3 4 4 2024 1 3 5 7 4 01234 2 3 14 15 4 01234 1 1 1 2 2 999999999999999 16384 16384
168 4 266 8 1498 8 40 15 1999999999999998 0
예제 1: 4개의 공식을 정렬한 결과는 아래와 같다.
예제 2: 본문에서 다루었다.
예제 3: 정렬 후 2, 3, 14, 15번째 공식은 아래와 같다.
예제 4: $V$ 배열의 원소에 중복이 있을 수 있음에 유의하자.
예제 5: 추가 설명 없음.