Bạn được yêu cầu cài đặt một thuật toán có thể coi là quan trọng nhất: tìm kiếm nhị phân. Cụ thể, bạn có một mảng đối tượng đã sắp xếp và một đối tượng mới cần chèn. Để tìm vị trí chèn, bạn có thể so sánh đối tượng mới với các đối tượng trong mảng. Mỗi phép so sánh trả về “greater”, nghĩa là đối tượng mới phải được chèn bên phải đối tượng đang xét, hoặc “less”, nghĩa là phải chèn bên trái. Để đơn giản, phép so sánh không bao giờ trả về “equal”.

Đề bảo đảm rằng nếu đối tượng mới lớn hơn một đối tượng trong mảng thì nó cũng lớn hơn mọi đối tượng nằm bên trái đối tượng ấy; tương tự, nếu nó nhỏ hơn một đối tượng thì nó cũng nhỏ hơn mọi đối tượng nằm bên phải. Nếu mảng có \(n\) phần tử, thuật toán có \(n+1\) kết quả (vị trí chèn) khả dĩ.

Trong bài này, các phép so sánh không có cùng chi phí. So sánh đối tượng mới với phần tử thứ \(i\) tốn \(a_i\), là một số nguyên từ 1 đến 9.

Trong trường hợp xấu nhất, tổng chi phí tìm kiếm nhị phân là bao nhiêu? Giả sử bạn dùng chiến lược tối ưu nhằm cực tiểu hóa tổng chi phí trong trường hợp xấu nhất.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test là chuỗi chữ số liền nhau, chữ số thứ \(i\) là \(a_i\); độ dài chuỗi là \(n\).

Dữ liệu ra

In Case #x: y, với \(y\) là chi phí tệ nhất tối ưu.

Ràng buộc

• \(1\le T\le50\); mọi chữ số từ 1 đến 9.

Phân nhóm

• Nhỏ: \(1\le n\le10^4\).
• Lớn: \(1\le n\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
111
1111
1111111
1111119

Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 10

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Costly Binary Search.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.