---
tags: Propose for Bedao
---
# Lật Domino

## Statement
Sau những giờ học căng thẳng, Quân và Hiển chơi Domino để xốc lại tinh thần. Mỗi quân Domino là một tấm thẻ gồm hai nửa dính liền vào nhau, trên mỗi nửa ghi các chấm với số lượng từ $1$ đến $6$. Hiện Quân và Hiển đang có $n$ tấm Domino, quân thứ $i$ có ghi $a_i$ chấm ở nửa trên và $b_i$ chấm ở nửa dưới.
Độ chênh lệch của các quân Domino được tính bằng trị tuyệt đối hiệu số lượng các chấm ở nửa trên và nửa dưới. Ví dụ trong hình trên; tổng số chấm ở nửa trên là $1+1+2+1=5$, tổng số chấm ở nửa dưới là $2+2+4+3=11$; độ chênh lệch là $|11-5|=6$.

Vì là người không thích sự chênh lệch, Quân muốn đảo một số quân Domino (Tức nửa trên thành nửa dưới, nửa dưới thành nửa trên) sao cho độ chênh lệch sau cùng là bé nhất có thể.

<b>Yêu cầu:</b> Bạn hãy giúp Quân tìm độ chênh lệch bé nhất đó nhé.

## Input

- Dòng đầu tiên chứa số nguyên dương $n$ $(1\le n\le 10^5)$ là số quân Domino.
- Dòng thứ hai chứa n số nguyên dương $a_1,a_2,…,a_n$ $(1\le a_i\le 6)$ mô tả số chấm ghi ở nửa trên của các quân Domino.
- Dòng thứ ba chứa n số nguyên dương $b_1,b_2,…,b_n$ $(1\le b_i\le 6)$ mô tả số chấm ghi ở nửa dưới của các quân Domino.

## Output
In ra hai dòng:
- Trên dòng đầu tiên in ra một số nguyên dương là chênh lệch trong phương án tìm được.
- Dòng thứ hai in ra chỉ số của các Domino cần đảo, nếu không cần đảo Domino nào thì in ra duy nhất một số `0`.

Nếu có nhiều phương án đảo thu được chênh lệch tối ưu thì in ra một đáp án bất kì. Trong trường hợp chỉ tìm ra được chênh lệch bé nhất mà không chỉ ra được phương án đảo thì bạn được $20\%$ số điểm của test.

## Example

| Input | Output |
| --------- | ------ |
| <p>4 <p>2 1 2 1 <p>2 2 4 3 |<p>1 <p> 4 |

## Scoring

- Có 15% số điểm của bài với $n\le 20$
- Có 25% số điểm khác với $n\le 40$
- Có 20% số điểm khác với $n\le 1000$
- Còn lại không có điều kiện gì thêm

# Solution

Ta giả sử $a_i \le b_i$ với mọi $i$. Khi đó gọi $w_1, w_2, ..., w_m$ là các tổng có thể tạo được ở hàng 1.
Vậy để tìm hiệu bé nhất, ta cần tìm $w_i$ lớn nhất thỏa mãn $w_i\le \frac{a_1+a_2+..+a_n+b_1+b_2+...+b_n}{2}$

Mà $a_i,b_i\le6 \Rightarrow |w_i-w_{i+1}|\le5$.
Theo đó, ta chỉ cần duyệt từ $sum=\frac{a_1+a_2+..+a_n+b_1+b_2+...+b_n}{2}$ giảm dần và kiểm tra có thể tạo được tổng có giá trị như vậy hay không bằng cách giải hệ:

$$x_1+2x_2+3x_3+4x_4+5x_5=sum$$ $$x_1< v_1 + 1,x_2< v_2 + 1,x_3< v_3 + 1,x_4< v_4 + 1,x_5< v_5 + 1$$

Trong đó:
- $v_x$ là số vị trí $i$ mà tại đó $b_i-a_i=x$

Sử dụng Digit DP:
- $f(id, j, carry, mask)$: Có thể tạo được số mà khớp đến chữ số thứ $id$ của $sum$ đồng thời số thứ $j$ trong 5 số; biến nhớ đang nhớ một lượng là $carry$, và $mask$ mô tả trạng thái của 5 biến (Bit thứ $t$ mô tả $x_t$ đã bé hơn $v_t+1$ hay chưa)
- Có thể chứng minh $carry \le 225$, vì vậy tại một trạng thái mà $carry \ge 255$ thì ta biết trạng thái đó không thỏa mãn.
- Gọi $d$ là số chữ số của $sum$ và $x$ là chữ số ở vị trí cao nhất của $sum$, đáp án là $f(d - 1,5, x,2^5-1)$

Code: https://ideone.com/7tuP5e (Hì, em sẽ update sau ạ)