16001번 - 보물 상자 열기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 256 MB | 222 | 34 | 27 | 20.930% |
문제
어피치는 전설 속의 보물을 찾기 위해 여행을 떠났고, 여러 관문을 돌파한 끝에 보물이 들어 있으리라 추정되는 상자를 찾았다. 하지만 그 상자는 잠금이 걸려 있었고, 거기에는 “상자를 열려면 상자 아래의 글자들을 잘 바꾸어 앞으로 읽으나 뒤로 읽으나 똑같아지도록 하라”라는 글귀가 쓰여 있었다.
상자 근처를 탐색해 보니 상자 아래에 알파벳이 쓰여 있는 석판 여러 장이 일렬로 놓여 있었다. 또한 상자의 주위에는 알파벳이 쓰여 있는 석판이 매우 많이 있었다. 아무래도 석판들을 잘 교체하여 상자 아래 일렬로 놓인 석판들을 회문(앞에서 뒤로 읽으나 뒤에서 앞으로 읽으나 똑같은 낱말이나 숫자 또는 문장)으로 만들면 상자가 열리는 듯하다. 어피치는 체력이 얼마 없기 때문에, 소모하는 체력을 최소로 하여 보물을 얻고자 한다. 각 석판은 교체하는 데 소모되는 체력이 다르다. 또한, 한 번 이동하는 데 c 만큼 체력이 소모된다. 즉, 이전 위치가 i 번째 석판이었는데 이번에 j 번째 석판을 교체하고자 한다면 그 위치까지 이동하는 동안 c * |j - i| 의 체력이 소모된다. N 개의 석판에 대해, 각각의 석판이 있는 위치에서 시작할 때 보물을 얻기 위해 소모되는 최소 체력을 구하시오.
입력
첫 줄에 테스트 케이스의 개수 T 가 주어진다. (1 ≤ T ≤ 100,000)
다음 줄부터 T 개의 테스트 케이스가 다음과 같은 형식으로 주어진다.
첫째 줄에 상자 아래 석판의 개수 N(1 ≤ N ≤ 1,000,000)과 한 칸 이동할 때 소모되는 체력 c 가 주어진다. (1 ≤ c ≤ 109)
둘째 줄에 길이 N 인 문자열이 주어진다. 문자열의 i 번째 문자는 i 번째 석판에 쓰여 있는 문자를 나타낸다. 각 문자는 알파벳 대문자이다.
셋째 줄에는 N 개의 수가 주어진다. i 번째 수는 i 번째 석판을 교체하는 데 소모되는 체력을 나타낸다. 하나의 석판을 교체할 때 소모되는 체력은 1 이상 109 이하이다.
주어지는 모든 N 의 합은 1,000,000을 초과하지 않는다.
출력
각 테스트 케이스에 대해, 각 석판이 있는 위치에서 시작했을 때 어피치가 소모해야 하는 최소 체력을 공백을 사이에 두고 한 줄로 출력한다.
예제 입력 1
2 5 1 ABCDE 7 1 4 5 1 5 1 ABCDA 7 1 4 5 1
예제 출력 1
6 5 6 6 5 2 1 2 3 4
첫 번째 테스트 케이스에 대해, 시작 위치가 첫 번째 석판일 때 최적의 방법 중 하나는 오른쪽으로 1칸 이동하여 B를 D로 바꾼 후, 3칸 이동하여 E를 A로 바꾸는 것이다.
출처
Contest > 카카오 코드 페스티벌 > 카카오 코드 페스티벌 2018 E번
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 2: GP of ainta E번
- 문제를 만든 사람: ainta
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호