คำว่า “สถาปัตยกรรม Harvard” ใช้กับคอมพิวเตอร์ที่มีหน่วยความจำสำหรับคำสั่งและข้อมูลแยกจากกันทางกายภาพ คำนี้มีที่มาจากคอมพิวเตอร์ Harvard Mark I ที่ IBM ส่งมอบในปี 1944 ซึ่งใช้เทปกระดาษสำหรับคำสั่งและรีเลย์สำหรับข้อมูล

ไมโครคอนโทรลเลอร์สมัยใหม่บางรุ่นใช้สถาปัตยกรรม Harvard แต่ไม่ได้ใช้เทปกระดาษและรีเลย์! หน่วยความจำข้อมูลแบ่งเป็นแบงก์ โดยแต่ละแบงก์มีรายการข้อมูลจำนวนเท่ากัน คำสั่งอ้างอิงข้อมูลแต่ละคำสั่งมีออฟเซตไบต์ $f$ ภายในแบงก์ และบิต $a$ ที่ใช้เลือกแบงก์ที่จะอ้างอิง หาก $a$ เป็น $0$ จะอ้างอิงแบงก์ $0$ หาก $a$ เป็น $1$ ค่าในรีจิสเตอร์เลือกแบงก์ (BSR) จะระบุแบงก์ที่ใช้ สมมติว่าทุกคำสั่งใช้เวลาทำงานเท่ากัน และมีคำสั่งที่ตั้งค่า BSR ได้

ภาพจาก Wikimedia Commons

ตัวอย่างเช่น สมมติว่ามี 4 แบงก์ แบงก์ละ 8 ไบต์ หากต้องการเข้าถึงตำแหน่ง $5$ สามารถใช้คำสั่งเดียวที่มี $a = 0$ และ $f = 5$ หรือใช้หนึ่งคำสั่งตั้ง BSR เป็น $0$ แล้วใช้คำสั่งที่มี $a = 1$ และ $f = 5$ วิธีแรกเร็วกว่าเพราะไม่ต้องตั้งค่า BSR

ทีนี้สมมติว่าในหน่วยความจำเดิม ตำแหน่งที่ต้องการเข้าถึงคือ $20$ จะมีเพียงวิธีเดียวที่ใช้ได้ คือทำคำสั่งตั้ง BSR เป็น $2$ (เว้นแต่ BSR มีค่า $2$ อยู่แล้ว) แล้วใช้คำสั่งที่มี $a = 1$ และ $f = 4$

โปรแกรมคือลำดับของการดำเนินการ แต่ละการดำเนินการเป็นอย่างใดอย่างหนึ่งดังนี้

• การอ้างอิงตัวแปร เขียนเป็น Vi โดย $i$ เป็นจำนวนเต็มบวก หรือ

• การทำซ้ำ เขียนเป็น Rn <program> E โดย $n$ เป็นจำนวนเต็มบวก และ <program> เป็นโปรแกรมใด ๆ การดำเนินการนี้เทียบเท่ากับการมี <program> ต่อกันตามลำดับ $n$ ครั้ง

งานของคุณคือหาระยะเวลาทำงานน้อยที่สุดของโปรแกรม โดยเฉพาะ เมื่อกำหนดจำนวนและขนาดของแบงก์หน่วยความจำและโปรแกรมที่จะทำงาน จงหาจำนวนคำสั่งน้อยที่สุด (ซึ่งอ้างอิงตำแหน่งหน่วยความจำและอาจตั้งค่า BSR) ที่ต้องทำเพื่อรันโปรแกรม คุณต้องหาการจับคู่ตัวแปรกับแบงก์หน่วยความจำที่ให้เวลาทำงานน้อยที่สุด แล้วรายงานเวลานั้น ซึ่งก็คือจำนวนการอ้างอิงหน่วยความจำและการตั้งค่ารีจิสเตอร์ BSR ที่จำเป็น ค่าเริ่มต้นของ BSR ไม่ได้กำหนดไว้ และจะเปลี่ยนเฉพาะเมื่อคำสั่งตั้งค่าอย่างชัดเจนเท่านั้น

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีกรณีทดสอบเดียวซึ่งประกอบด้วยสองบรรทัด บรรทัดแรกมีจำนวนเต็มสองค่า $b$ และ $s$ โดย $1 \le b \le 13$ คือจำนวนแบงก์หน่วยความจำ และ $1 \le s \le 13$ คือจำนวนตัวแปรที่เก็บได้ในแต่ละแบงก์ บรรทัดที่สองมีโปรแกรมที่ไม่ว่าง ซึ่งมีองค์ประกอบคั่นด้วยช่องว่างไม่เกิน 1 000 องค์ประกอบ (แต่ละ Rn, Vi และ E นับเป็นหนึ่งองค์ประกอบ)

คุณสามารถสมมติได้ดังนี้:

• ในการทำซ้ำ Rn จำนวนครั้งที่ทำซ้ำเป็นไปตาม $1 \le n \le 10^6$

• ในการวนซ้ำ Rn <program> E ส่วนของโปรแกรมในลูป <program> ไม่ว่าง

• ในการอ้างอิงตัวแปร Vi ดัชนีตัวแปรเป็นไปตาม $1 \le i \le \min(b \cdot s, 13)$

• จำนวนการอ้างอิงตัวแปรทั้งหมดในการทำงานของโปรแกรมหนึ่งครั้งไม่เกิน $10^{12}$

ข้อมูลส่งออก

แสดงจำนวนคำสั่งน้อยที่สุดที่ต้องทำเพื่อให้โปรแกรมเสร็จสมบูรณ์

ตัวอย่าง

ข้อมูลนำเข้า 1

1 2
V1 V2 V1 V1 V2

ข้อมูลส่งออก 1

5

ข้อมูลนำเข้า 2

2 1
V1 V2 V1 V1 V2

ข้อมูลส่งออก 2

6

ข้อมูลนำเข้า 3

1 2
R10 V1 V2 V1 E

ข้อมูลส่งออก 3

30

ข้อมูลนำเข้า 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

ข้อมูลส่งออก 4

17