Editorial Đèn Bình Dương (normallights)

Đề bài

https://lqdoj.edu.vn/problem/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\ast 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\le x\le 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\to 6$, nếu
  $binary1[j]\ne 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\le i\le 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 :D (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 XD

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…