Istilah “arsitektur Harvard” berlaku untuk komputer yang memiliki memori terpisah secara fisik untuk instruksi dan data. Istilah ini berasal dari komputer Harvard Mark I, yang dikirimkan oleh IBM pada 1944, yang menggunakan pita kertas untuk instruksi dan relai untuk data.
Beberapa mikrokontroler modern menggunakan arsitektur Harvard, tetapi tidak menggunakan pita kertas dan relai! Memori data disusun dalam bank-bank yang masing-masing berisi jumlah item data yang sama. Setiap instruksi yang mengacu pada data memiliki offset byte $f$ dalam suatu bank, dan sebuah bit $a$ yang memilih bank yang akan diakses. Jika $a$ adalah $0$, bank $0$ diakses. Jika $a$ adalah $1$, nilai pada register pemilih bank (BSR) menentukan bank yang digunakan. Anggap setiap instruksi membutuhkan waktu eksekusi yang sama, dan tersedia instruksi yang dapat menetapkan nilai BSR.
Gambar dari Wikimedia Commons
Misalnya, anggap ada 4 bank yang masing-masing berukuran 8 byte. Untuk mengakses lokasi $5$, gunakan satu instruksi dengan $a = 0$ dan $f = 5$, atau tetapkan BSR menjadi $0$ dengan satu instruksi lalu gunakan instruksi dengan $a = 1$ dan $f = 5$. Cara pertama lebih cepat karena tidak memerlukan penetapan BSR.
Sekarang, dengan memori yang sama, anggap lokasi yang akan diakses adalah $20$. Hanya ada satu cara yang berhasil: jalankan instruksi yang menetapkan BSR menjadi $2$ (kecuali nilai BSR sudah $2$), lalu gunakan instruksi dengan $a = 1$ dan $f = 4$.
Program adalah urutan operasi. Setiap operasi berupa
referensi variabel, ditulis
Vi, dengan $i$ bilangan bulat positif, ataupengulangan, ditulis
Rn <program> E, dengan $n$ bilangan bulat positif dan<program>program sembarang. Operasi ini setara dengan $n$ kemunculan<program>secara berurutan.
Tugas Anda adalah menentukan waktu eksekusi minimum program. Secara khusus, diberikan jumlah dan ukuran bank memori serta program yang akan dijalankan, carilah jumlah minimum instruksi (yang mengakses lokasi memori dan mungkin menetapkan BSR) yang harus dijalankan untuk mengeksekusi program. Anda harus menemukan pemetaan variabel ke bank memori yang menghasilkan waktu eksekusi terkecil, lalu melaporkan waktu itu, yaitu jumlah referensi memori dan penetapan register BSR yang diperlukan. Nilai awal BSR tidak terdefinisi dan hanya berubah ketika sebuah instruksi secara eksplisit menetapkan nilainya.
Masukan
Masukan berisi satu kasus uji yang terdiri dari dua baris. Baris pertama berisi dua bilangan bulat $b$ dan $s$, dengan $1 \le b \le 13$ adalah jumlah bank memori dan $1 \le s \le 13$ adalah jumlah variabel yang dapat disimpan dalam setiap bank. Baris kedua berisi program tidak kosong dengan paling banyak 1 000 elemen yang dipisahkan spasi (setiap Rn, Vi, dan E dihitung sebagai satu elemen).
Anda boleh menganggap hal-hal berikut:
Dalam pengulangan
Rn, jumlah pengulangan memenuhi $1 \le n \le 10^6$.Dalam operasi perulangan
Rn <program> E, badan perulangan<program>tidak kosong.Dalam referensi variabel
Vi, indeks variabel memenuhi $1 \le i \le \min(b \cdot s, 13)$.Jumlah total referensi variabel yang dilakukan dalam satu eksekusi program paling banyak $10^{12}$.
Keluaran
Tampilkan jumlah minimum instruksi yang harus dijalankan untuk menyelesaikan program.
Contoh
Masukan 1
1 2 V1 V2 V1 V1 V2
Keluaran 1
5
Masukan 2
2 1 V1 V2 V1 V1 V2
Keluaran 2
6
Masukan 3
1 2 R10 V1 V2 V1 E
Keluaran 3
30
Masukan 4
4 1 V1 R2 V2 V4 R2 V1 E V3 E
Keluaran 4
17