# Đề THT bảng B - BRVT - 2016: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2015 - 2016.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_thtb_15_24).
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Màu của kí tự

### Tóm tắt đề bài:

Cho xâu $s =$***"HOITHITINHOCTRETINHBARIAVUNGTAULANTHUXX"***, với kí tự **đầu** tô màu **xanh**, kí tự **2** tô màu **đỏ**, kí tự **3** tô màu **tím**, kí tự **4** tô màu **vàng**, kí tự **5** tô màu **xanh**, ...

Ta nối liên tiếp các xâu $s$ vô hạn lần đã được tô màu tạo thành xâu $t$

**Yêu cầu:** Cho $k$ là vị trí của kí tự nằm ở vị trí $k$ trong xâu $t$, tìm kí tự thứ $k$ và màu của kí tự đó, giả sử thứ tự các kí tự bắt đầu từ $0$

**Dữ liệu đảm bảo:**
- $0 < k \le 10^9$.

### Lời giải

>[!Tip] Nhận xét
>1. Xâu $s$ có tối đa 39 kí tự và xâu dễ thấy xâu $t$ có tính chu kì
>Ta biết rằng nếu 1 xâu có tính chu kì, kí tự $i$ sẽ giống kí tự $i$ $mod$ $n$
>
>2. Tương tự với màu của nó, tuy nhiên tại điểm giao giữa 2 chu kì, tức tại vị trí của kí tự cuối cùng ở chu kì $i$ và kí tự đầu của chu kì $i+1$, ta thấy rằng màu của chúng sẽ phải là T và X chứ không phải 2 màu liên tiếp nhau, do đó công thức sẽ là ($k$ $mod$ $39$) $mod$ $4$ để lấy được vị trí trong xâu $s$, từ đó tìm màu của kí tự đó

Nếu ta khai báo trước xâu $s$ và xâu $color =$ "$XDTV$", ta có thể ==sử dụng các công thức ở trên để lấy kí tự ở vị trí đó==.

**Độ phức tạp thời gian:** $O\left( 1 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int n;
string s, t;

int main() {
    cin >> n;
    s = "HOITHITINHOCTRETINHBARIAVUNGTAULANTHUXX";
    t = "XDTV";
    int m = s.size();
    cout << s[n % m] << "\n" << t[(n % m) % 4];

    return 0;
}

:::

## Bài 2: Đặt mìn

### Tóm tắt đề bài:
Cho bảng $A$ và bảng $B$ gồm $N$x$N$ phần tử chỉ gồm các số $0$ và $1$

Cần tác động một số lần để bảng $A$ trở thành bảng $B$. Mỗi lần tác động ô $[i,j]$ thì ô $[i,j]$ sẽ bị lật giá trị ($0$ thành $1$ hoặc $1$ thành $0$) các ô xung quanh nó là ô $[i-1,j]$, $[i+1,j]$, $[i,j-1]$, $[i,j+1]$ dù không được tác động cũng sẽ bị lật giá trị

**Yêu cầu:** Kiểm tra xem có tồn tại cách tác động một số ô để bảng $A$ trở thành bảng $B$ hay không. Nếu có, in ra số lần tác động tối thiểu, ngược lại in ra $-1$

**Dữ liệu đảm bảo:**
- $N \le 16$.
- $0 \le A_i, B_i \le 1$

### Lời giải

>[!Tip] Nhận xét
>Nếu toàn bộ hàng $1$ đến hàng $i-1$ đã được lật giống với bảng $B$, để hàng $i$ giống trong bảng $B$ và $i < N$, ta có thể ưu tiên sử dụng hàng $i+1$ để lật hàng $i$

Đối với hàng $N$, do không có hàng $N+1$ để lật hàng $N$, ta không còn cách để lật hàng $N$ nếu hàng này chưa giống với hàng trong bảng $B$. Do đó, với mỗi cách lật thỏa mãn, ta chỉ cần ==kiểm tra xem hàng $N$ đã được lật đúng với trong bảng $B$ hay chưa==

Đối với hàng $1$, ngoài việc được lật bằng hàng $2$, ta cũng có thể lật chính nó bằng cách tác động vào các ô trong hàng $1$, ==có $2^N$ cách để hàng $1$ tự lật==

> Sử dụng thuật toán quay lui để tự lật hàng $1$, và từ hàng $2$ đến hàng $N$, ta sẽ thao tác giống như ở trên

**Độ phức tạp thời gian:** $O\left( N^2*2^N \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int n;
int a[20][20], b[20][20], grid[20][20];
int firstRowPress[20]; // Lưu trạng thái nhấn tại hàng đầu tiên
long long ans = INF;

// Hàm nhấn ô (i, j) và các ô kề (trên, dưới, trái, phải)
void press(int i, int j) {
    grid[i][j] = 1 - grid[i][j];
    if (i > 1) grid[i - 1][j] = 1 - grid[i - 1][j];
    if (i < n) grid[i + 1][j] = 1 - grid[i + 1][j];
    if (j > 1) grid[i][j - 1] = 1 - grid[i][j - 1];
    if (j < n) grid[i][j + 1] = 1 - grid[i][j + 1];
}

// Hàm quay lui để thử tất cả các cấu hình nhấn ở hàng đầu tiên
void backtrack(int col) {
    // Nếu đã xét hết các cột
    if (col > n) {
        // Copy lưới ban đầu a[][] sang lưới làm việc grid[][]
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                grid[i][j] = a[i][j];

        int cnt = 0; // Đếm số lần nhấn

        // Áp dụng cấu hình nhấn ở hàng đầu tiên
        for (int j = 1; j <= n; j++) {
            if (firstRowPress[j]) {
                press(1, j);
                cnt++;
            }
        }

        // Tự động nhấn ở các hàng sau dựa vào sự khác biệt với hàng trên
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i - 1][j] != b[i - 1][j]) {
                    press(i, j);
                    cnt++;
                }
            }
        }

        // Kiểm tra lưới cuối cùng có khớp với b[][] không
        bool match = true;
        for (int i = 1; i <= n && match; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][j] != b[i][j]) {
                    match = false;
                    break;
                }
            }
        }

        // Nếu đúng, cập nhật đáp án nhỏ nhất
        if (match) ans = min(ans, (long long)cnt);
        return;
    }

    // Thử nhấn và không nhấn ô (1, col)
    firstRowPress[col] = 1;
    backtrack(col + 1);

    firstRowPress[col] = 0;
    backtrack(col + 1);
}

int main() {
    // Nhập kích thước lưới
    cin >> n;

    // Nhập lưới ban đầu a[][]
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    // Nhập lưới mong muốn b[][]
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> b[i][j];

    // Bắt đầu quay lui từ cột 1 của hàng đầu tiên
    backtrack(1);

    // In kết quả
    if (ans == INF)
        cout << -1 << "\n"; // Không có cách nào
    else
        cout << ans << "\n"; // Số lần nhấn ít nhất

    return 0;
}

:::