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

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.

Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)

• Đề THT bảng B - BRVT - 2016: Editorial
  • Bài 1: Màu của kí tự
    • Tóm tắt đề bài:
    • Lời giải
  • Bài 2: Đặt mìn
    • Tóm tắt đề bài:
    • Lời giải

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

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)$.

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

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(N^2\ast 2^N)$.

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;
}