Spoiler Alert

Hackmd:

https://hackmd.io/@stephit/normallights

Hint:

Gọi \(s1\), \(s2\) là biểu diễn chuỗi kí tự của hai số \(a\), \(b\).
Việc đầu tiên là cần phải thêm khung cho đến khi hai số này có số lượng khung bằng nhau.

Ta có thể \(while\) và thêm khung cho đến khi đủ số lượng.

Đặt \(coin = 2 * max(len(s1), len(s2)) - (len(s1) + len(s2))\) để tìm ra chi phí thêm khung.

Tiếp theo, ta đổi \(s1[i]\) thành \(s2[i]\) lần lượt rồi tính tổng chi phí mỗi lần đổi. Việc đổi \(s1[i]\) thành \(s2[i]\) là đổi một chữ số qua một chữ số khác.

Ta có bản vẽ sau:

Với \(0\) biểu diễn cho thanh ngang ở trên cùng, \(1\) biểu diễn cho thanh dọc ở bên trái trên cùng đầu tiên,..., \(6\) biểu diễn cho thanh ngang ở dưới cùng.

Ta dùng mảng \(binary\) có \(7\) phần tử biểu diễn các thanh của chữ số \(x\) \((0 \leq x \leq 9)\)
với \(binary[i] \in [0, 1]\)

• \(binary[i] = 1\) thì chữ số \(x\) có thanh thứ \(i\) (theo bản vẽ).
• \(binary[i] = 0\) thì chữ số \(x\) không có thanh thứ \(i\) (theo bản vẽ).

VD: Biểu diễn của số \(0\) là \(binary = [1, 1, 1, 0, 1, 1, 1]\)

Ta sẽ dùng nó để đổi một chữ số qua một chữ số khác, ở đây là \(s1[i]\) qua \(s2[i]\).

• Gọi \(binary1\) là biểu diễn của \(s1[i]\), \(binary2\) là biểu diễn của \(s2[i]\).
• Duyệt \(j\) từ \(0 \rightarrow 6\), nếu \(binary1[j] \neq binary2[j]\) thì ta phải thêm/xóa thanh thứ \(j\) của \(s1[i]\) \(\Rightarrow\) mất \(1\) chi phí (coin += 1).

VD:

• \(s1[i] = 0 \Rightarrow binary1 = [1, 1, 1, 0, 1, 1, 1]\)
• \(s2[i] = 1 \Rightarrow binary2 = [0, 0, 1, 0, 0, 1, 0]\)
               \(\uparrow\) \(\uparrow\)   \(\uparrow\)  \(\uparrow\)
• Thì có tất cả \(4\) vị trí khác nhau, vậy chi phi đổi từ \(0\) qua \(1\) là \(4\) Coin.

Khi tính được chi phí đổi từ \(s1[i]\) qua \(s2[i]\), ta có thể dễ dàng cộng dồn lại, cộng với chi phí thêm khung và in ra kết quả.

Còn với cách tính \(u\) và \(v\), ta định nghĩa \(sticks[i]\) là số lượng thanh của chữ số \(i\) \((0 \leq i \leq 9)\).

Ta cũng cộng dồn lại như cách tính chi phí, nhưng cần để hai biến riêng biệt.

Một số cách tính chi phí đổi từ \(s1[i]\) qua \(s2[i]\) như cách ngồi nháp hết ra 😃 (có nhiều nhất 100 cái \(if\) chứ mấy), nhưng vì mình lười nên mình làm cách này 😆

Optimize:

• Ta thấy cách biễu diễn các thanh của mỗi chữ số dưới dạng mảng \(0/1\) giống như cách biểu diễn số nhị phân, vậy thì ta đổi nó ra luôn số thập phân.
  VD: \(0 \Rightarrow binary = 1110111_2 = 119_{10}\)
• Thay vì \(for\) trong mảng để xét có bao nhiêu vị trí khác nhau, ta dùng toán tử XOR.

Example Code:

Click here...