TLEOJ Contest #10 - Mã Kekma - TLEOJ: TLE Online Judge

TLEOJ Contest #10 - Mã Kekma

Điểm: 1500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

2tk

Dạng bài

Ở Trái Đất, cấu trúc của ADN được cấu tạo từ sự liên kết của $2$ chuỗi nucleotit, trong đó mỗi chuỗi gồm $1$ trong $4$ nucleotit mang tên $A,T,G,X,$ còn ở hành tinh penguin, tồn tại $26$ loại nucleotit tương ứng với $26$ chữ cái tiếng Anh viết hoa: $A,B,\dots,Z$ .

Hành tinh penguin rất tân tiến, vậy nên các nhà khoa học đã tạo ra một loại nucleotit mới rất bí ẩn, đặt tên là ?. Bên cạnh đó, họ cũng tìm ra công nghệ chỉnh sửa, chèn vào thứ tự của dãy nucleotit đã có sẵn các loại nucleotit bí ẩn kia.

Ví dụ, có dãy nucleotit $A-B-C$ , các nhà khoa học có thể tạo ra vô hạn dãy mới nhờ thêm vào một vị trí bất kỳ $1$ nucleotit ? ấy, điển hình như $A-?-B-C-?,...$

Nhờ công nghệ thần kỳ kia, và sự đa dạng trong các kiểu hình nucleotit, cộng thêm nucleotit bí ẩn mang tên ? được phát minh ra, các nhà khoa học đã có thể chữa mọi loại bệnh tật, tăng tuổi thọ, cho con người những khả năng đặc biệt!

Sau quá trình nghiên cứu, 2tk nhận ra một chuỗi ADN có mã Kekma càng nhỏ, thì lợi ích của nó cho con người càng lớn, trong đó mã Kekma được tính như sau:

Cách tính

Với 2 dãy nucleotit $a$ và $b$ có cùng độ dài $n$ , công thức được tính như sau:

Với vị trí $i$ , nếu cả $a_i$ và $b_i$ đều là 1 trong 26 ký tự tiếng Anh viết hoa ( $A,B,\dots,Z$ ) thì giá trị của vị trí thứ $i$ được tính như sau:
- Gọi $x$ là giá trị của nucleotit thứ $i$ trong dãy 1, $y$ là giá trị của nucleotit thứ $i$ trong dãy $2$ (Trong đó A tương ứng với $1$ , B tương ứng với $2$ , ..., Z tương ứng với $26$ )
- Khi đó giá trị của vị trí thứ $i$ là $|x-y|$ .
Ngược lại (tức là 1 trong 2 ký tự là ?) thì giá trị của vị trí thứ $i$ là hằng số Kekma $k$ (được 2tk tìm ra).
Mã Kekma của 2 dãy $a$ và $b$ là tổng giá trị của mọi vị trí $i$ từ $1$ đến $n$ .

Ví dụ

VD1: ADN có dạng:

$A-B-C$
$C-A-B$

Xét vị trí đầu tiên, có 2 ký tự $A,C$ không phải là nucleotit đặc biệt ? nên giá trị của vị trí đầu tiên là $|1-3|=2$ .
Xét vị trí thứ hai, có giá trị của vị trí thứ hai là $|2-1|=1$ .
Xét vị trí thứ ba, có giá trị của vị trí thứ ba là $|3-2|=1$ .
Mã Kekma của nó là $2+1+1=4$ .

VD2: ADN có dạng:

$A-B-?$
$C-?-B$

Giả sử hằng số Kekma $k=3$ .
Xét vị trí đầu tiên, có giá trị của vị trí đầu tiên là $|1-3|=2$ .
Xét vị trí thứ hai, có ký tự ? ở vị trí thứ hai trong nucleotit thứ hai nên giá trị của vị trí thứ hai là $k=3$ .
Xét vị trí thứ ba, có ký tự ? ở vị trí thứ ba trong nucleotit thứ nhất nên giá trị của vị trí thứ ba là $k=3$ .
Mã Kekma của nó là $2+3+3=8$ .

Vì tìm ra được lý thuyết ấy, 2tk được cả thế giới tôn vinh và giao cho một trọng trách lớn lao là tìm được mã Kekma nhỏ nhất của $1$ ADN được tạo thành từ $2$ chuỗi nucleotit đã được xử lý.

Biết rằng ban đầu $2$ chuỗi nucleotit có độ dài bất kỳ, chỉ chứa các nucleotit $A,B,\dots,Z$ , và 2tk cần xử lý chúng bằng cách cho thêm một số nucleotit bí ẩn mang tên ? vào một số vị trí bất kỳ trong $2$ chuỗi nucleotit đó. Chú ý là sau khi thực hiện thao tác thì 2 dãy phải có độ dài bằng nhau.

Vì 2tk bận nghiên cứu thêm về mã Kekma tại web Kekma, nó đã bị ẩn đi do đó là thông tin mật, vậy nên anh ấy đã giao nhiệm vụ lớn lao kia cho bạn, hãy giúp 2tk tạo ra 1 ADN thỏa mãn yêu cầu.

Input, Output và Subtask

Input

Dòng thứ nhất: $2$ chuỗi Nucleotit chỉ gồm các ký tự từ $A,B,\dots,Z$ tương ứng các nucleotit, độ dài không quá $3000$ .
Dòng tiếp theo: hằng số Kekma, gọi tắt là $k$ $(0 \le k \le 1000)$

Output

Gồm $1$ dòng duy nhất là kết quả thỏa mãn.

Example

Input

AAA
CCC
0

Output

Note

Ta có thể xử lý $2$ chuỗi như sau:

$A-?-A-?-A-?$
$?-C-?-C-?-C$

Khi đó, dễ dàng tính được mã Kekma là $0$ .

Bình luận

Không có bình luận nào.