17278번 - 이진 문자열 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 185 | 5 | 5 | 20.833% |
문제
0과 1로만 이루어진 길이 n의 이진 문자열 S가 주어져 있다.
S의 인덱스는 1부터 시작하며, S[a : b]는 인덱스 a 이상 b 이하까지의 S의 부분 문자열로 정의하자.
이 때, 이 문자열에, 기존 문자열의 부분 문자열을 반전시켜 삽입하는 연산을 m번 적용한다.
조건들은 다음과 같다.
- 삽입 연산은 2개의 정수 파라미터 x ≤ y를 받는다. 이 때 m번의 연산 각각에 사용되는 x, y 값들은 다를 수 있다.
- 삽입할 문자열은 S[x : y]의 0/1을 반전시킨 것이다.
- 이 문자열을 삽입할 위치는 S의 y번째 문자 바로 뒤이다. 삽입된 이후 S의 길이는 y - x + 1만큼 증가한다.
- 삽입 연산시마다 S는 업데이트된다. 즉, 두 번째 삽입 연산을 시작할 때는 첫 번째 삽입 연산이 끝나고 업데이트된 새로운 문자열 S를 사용한다.
이 문제의 목적은, 연산 m번을 모두 적용한 후 마지막 결과 S에 대해, S의 최초 k개의 문자를 맞추는 것이다.
예를 들어 S = 01010110 이고 n = 8, m = 2, k = 12 그리고 두 연산 (x= 2, y = 4)와 (x = 3, y = 5) 를 순서대로 적용한다면 아래와 같은 순서로 S가 변경된다.
- 첫 번째 연산을 적용하면 S[2:4] = 101 이니 이를 반전시켜 삽입하여 S = 01010100110 을 얻게 된다 (굵은 표시가 된 부분이 삽입된 부분).
- 두 번째 연산을 적용하면 S[3:5] = 010 이니 이를 반전시켜 삽입하여 S = 01010101100110 를 얻게 된다 (굵은 표시가 된 부분이 삽입된 부분).
- k=12 이므로 처음 12글자인 “010101011001” 가 답이 된다.
입력으로 n, m, k, 시작 문자열 S, 그리고 m번의 연산에 사용되는 x, y 값들을 입력 받아 모든 연산을 적용한 후 얻어지는 S의 처음 k개의 글자를 출력하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스의 첫 줄에는 n, m, k가 공백으로 구분되어 주어진다.
두 번째 줄에는 길이가 n인 문자열이 주어지며 각 문자는 0 혹은 1이다.
다음 m줄에 걸쳐 한 줄에 두 개의 정수 x[i], y[i]가 주어진다. 입력으로 주어지는 x[i], y[i]는 언제나 다음 조건을 만족한다: 1 ≤ x[i] ≤ y[i] ≤ i번째 연산을 적용하기 직전의 문자열 S의 길이.
마찬가지로, k는 m번의 연산을 모두 적용한 후 마지막에 얻은 문자열 S의 길이와 106 중 작은 값을 넘지 않는다.
출력
각 테스트 케이스에 대해 한 줄에 길이가 k인 문자열을 출력한다.
서브태스크 1 (5점)
- 1 ≤ n ≤ 103, 1 ≤ m ≤ 103, 1 ≤ k ≤ 105
서브태스크 2 (23점)
- 1 ≤ n ≤ 106, 1 ≤ m ≤ 104, 1 ≤ k ≤ 106
예제 입력 1
3 8 2 12 01010110 2 4 3 5 4 1 4 1010 1 1 8 2 16 10101100 1 2 2 8
예제 출력 1
010101011001 1001 1001101111001000
힌트
- 케이스 2: 1010 → 10010 (k = 4 이므로 맨 처음 4자리만 출력)
- 케이스 3: 10101100 → 1001101100 → 10011011110010000 (k = 16 이므로 맨 처음 16자리만 출력)
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호