JOI 2018 Snake Escaping- 독사의 탈주 > 문제은행 : 정보올림피아드&알고리즘




3164 : 독사의 탈주

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
1 회   
시도횟수
11 회   

문제

조이연구소에서는 2^L 마리의 독사를 기르고 있으며, 각각 0, 1, ..., 2^L-1의 번호가 매겨져있다

모든 독사는 머리부터 발끝까지 L개의 부분으로 나누어져 있으며, 각 부분은 파랑 또는 빨간색이 칠해져 있다

특별히 i번째 독사의 생김새는 i2진수로 표기했을 때, k번째 자릿수가 0이라면 k번째 부분은 파란색, 1이라면 빨간색이다

예를 들어, L=3인 경우 0번째 뱀은 모든 부분이 파란색이고, 6번째 뱀은 빨강, 빨강, 파랑 순서대로 칠해져 있다.

각 독사는 위험도가 0 이상 9 이하의 정수 값으로 정해져 있다

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 이루어진 길이 2^L의 문자열 S가 주어지며, i번째 글자 (1i 2^L)i-1번째 독사의 위험도를 나타낸다.

조이연구소에서는 독사들이 매우 잘 탈출한다

때문에 조이연구소는 하루에 한 번씩 탈출한 독사의 정보를 수집한 뒤, 그 정보를 바탕으로 위험도를 계산하여 독사 회수에 필요한 장비를 준비하고 있다.

당신은 Q일 동안 탈출한 독사들에 대한 정보가 주어진다

 

d일째 (1 d Q)에 접수 된 정보는 0, 1, ?로 이루어진 길이 L인 문자열 S_d로 표현되고, 각 글자는 다음과 같은 의미를 가진다.

S_dj번째 문자가 0인 경우는 d일째에 탈출한 모든 독사의 j번째 부분이 파란색이다.

S_dj번째 문자가 1인 경우는 d일째에 탈출한 모든 독사의 j번째 부분이 빨간색이다.

S_dj번째 문자가 ?인 경우는 d일째에 탈출한 모든 독사의 j번째 부분에 대한 정보가 없다. (빨간색일수도, 파란색일수도 있다)

탈출한 독사는 조이연구소의 직원이 모두 당일에 회수하며, 탈출했다가 돌아온 독사가 다음날 이후에 다시 탈출할 수 있다.

당신의 임무는 Q일 동안 주어지는 독사의 정보에 대해, 각 날마다 그 날 탈출한 가능성이 있는 독사들의 위험도 총합을 계산하는 것이다.

 

메모리 제한이 작은 것에 유의하자. 


입력형식

첫 번째 줄에 뱀의 길이 L과 날짜 수를 나타내는 자연수 Q가 주어진다. 두 번째 줄에는 길이 2^L의 문자열 S가 주어진다. 이 문자열은 독사의 위험도를 나타낸다. 세 번째 줄부터 Q개의 줄에는 길이 L의 문자열 S_d가 주어진다. d번째 줄에는 d번째 날에 탈출한 독사에 대한 정보를 나타낸다. [제한] 모든 입력 데이터는 다음을 만족한다. • 1 ≦ L ≦ 20. • 1 ≦ Q ≦ 1,000,000. • S는 길이가 2^L인 문자열이다. • 문자열 S는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 구성된다. • T_d는 길이가 L인 문자열이다. (1 ≦ d ≦ Q) • 문자열 T_d는 0, 1, ?로 구성된다. (1 ≦ d ≦ Q) 부분문제 1 [5 점] • L ≦ 10 • Q ≦ 1,000 부분문제 2 [7 점] • L ≦ 10 부분문제 3 [10 점] • L ≦ 13 부분문제 4 [53 점] • Q ≦ 50,000 부분문제 5 [25 점] • 추가 제한은 없다.

출력형식

각각의 정보에 대해, 그 날 탈출할 수 있는 독사의 위험도 총합을 Q개의 줄에 하나씩 출력한다.

입력 예

3 5
12345678
000
0??
1?0
?11
???

출력 예

1
10
12
12
36

입력 예

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

출력 예

9
18
38
30
14
15
20
80

Hint!

첫 번째 예제에서는 세 부분으로 구성된 독사가 총 2^3 = 8 마리 있다. 5일 동안 탈출할 수 있는 독사의 정보는 다음과 같다.

 

• 1일째에 탈출한 가능성이 있는 독사는 독사 0 뿐이다. 위험도 총합은 1이다. 

• 2일째에 탈출한 가능성이 있는 독사는 독사 0,1,2,3이다. 위험도 총합은 10이다. 

• 3일째에 탈출한 가능성이 있는 독사는 독사 4,6이다. 위험도 총합은 12이다. 

• 4일째에 탈출한 가능성이 있는 독사는 독사 3,7이다. 위험도 총합은 12이다. 

• 5일째에 탈주한 가능성이 있는 독사는 독사 0,1,2,3,4,5,6,7이다. 

 

위험도 총합은 36이다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP