E. 하버드

“하버드 아키텍처”라는 용어는 명령어와 데이터를 위한 메모리가 물리적으로 분리된 컴퓨터를 가리킨다. 이 용어는 1944년 IBM이 납품한 Harvard Mark I 컴퓨터에서 유래했는데, 이 컴퓨터는 명령어(instr\(uc- ti\)ons)에는 종이테이프를, 데이터에는 릴레이를 사용했다. 일부 현대 마이크로컨트롤러는 하버드 아키텍처를 사용한다. 물론 종이테이프와 릴레이는 아니다! 데이터 메모리는 뱅크로 조직되며, 각 뱅크는 같은 수의 데이터 항목을 담는다(c\(on- ta\)ining). 데이터를 참조하는(da\(ta-re\)ferencing) 각 명령어는 뱅크 내 바이트 오프셋 \(f\)와, 참조할 뱅크를 선택하는 데 쓰이는 비트 \(a\)를 가진다. \(a\)가 0이면 뱅크 0이 참조된다. \(a\)가 1이면 뱅크 선택 레지스터(BSR)의 값이 사용할 뱅크를 지정한다. 각 명령어의 실행 시간은 같다고 가정하고, BSR 값을 설정할 수 있는 명령어가 있다고 하자. 예를 들어 8바이트짜리 뱅크가 4개 있다고 하자. 위치 5에 접근하려면 \(a = 0\), \(f = 5\)인 명령어 하나를 쓰거나, 한 명령어로 BSR을 0으로 설정한 뒤 \(a = 1\), \(f = 5\)인 명령어를 쓰면 된다. 첫 번째 방법이 BSR 설정이 필요 없으므로 더 빠르다. 이제 (같은 메모리에서) 접근할 위치가 20이라고 하자. 여기서는 한 방법만 통한다. BSR을 2로 설정하는 명령어를 실행한 뒤(BSR이 이미 값 2를 갖고 있지 않다면) \(a = 1\), \(f = 4\)인 명령어를 쓰는 것이다. 프로그램은 연산들의 나열이다. 각 연산은 다음 중 하나이다.

• 변수 참조. V\(i\)로 쓰며, \(i\)는 양의 정수이다.

• 반복. R\(n ogr\(am> E\)로 쓰며, \(n\)은 양의 정수이고(a\(nd ogr\(am> is\)) 임의의 프로그램이다. 이 연산은 프로그램(\(of ogram>)이 \(n\)번 연속으로 나오는 것과 동등하다. 당신의 문제는 프로그램의 최소 실행 시간을 구하는 것이다. 구체적으로, 메모리 뱅크의 개수와 크기, 그리고 실행할 프로그램이 주어질 때, 프로그램을 실행하기 위해 실행되어야 하는 명령어(메모리 위치를 참조하고 경우에 따라 BSR을 설정하는)의 최소 개수를 구하시오. 이를 위해 실행 시간이 가장 짧아지는 변수의 메모리 뱅크 배정을 찾아, 그 실행 시간, 즉 필요한 메모리 참조와 BSR 레지스터 설정의 횟수를 보고해야 한다. BSR의 값은 처음에는 정의되어 있지 않으며, 명령어가 명시적으로 값을 설정할 때에만 바뀐다.

입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 두 정수 \(b\)와 \(s\)가 주어지며, \(1 \le b \le 13\)은 메모리 뱅크의 수이고 \(1 \le s \le 13\)은 각 메모리 뱅크에 저장할 수 있는 변수의 수이다. 둘째 줄에는 공백으로 구분된(spa\(ce-se\)parated) 원소가 최대 1 000개인 비어 있지 않은(n\(on-em\)pty) 프로그램이 주어진다(R\(n\), V\(i\), E 각각이 원소 하나로 센다). 다음을 가정해도 된다.

• 반복 R\(n\)에서 반복 횟수는 \(1 \le n \le 10^{6}\)을 만족한다.

• 루프 연산 R\(n ogr\(am> E\)에서 루프 본문(\(dy ogr\(am> is\))은 비어 있지 않다.

• 변수 참조 V\(i\)에서 변수 번호는 \(1 \le i \le mi\)n(\(b \cdot s\), 13)을 만족한다.

• 프로그램 실행이 수행하는 변수 참조의 총횟수는 최대 \(10^{12}\)이다.

프로그램을 완료하기 위해 실행되어야 하는 명령어의 최소 개수를 출력한다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2013