Bàn cờ 2 x n. Hàng 1: k1 ô đầu trắng. Hàng 2: k2 ô đầu trắng. Còn lại đen. Có w dominô trắng, b dominô đen (kích thước 2x1). Đặt dominô trắng lên 2 ô trắng, dominô đen lên 2 ô đen. Có thể đặt ngang hoặc dọc. Kiểm tra có đặt hết w+b dominô không.
Ví dụ
Với n=5, k1=4, k2=3, w=3, b=1, đầu ra True (1).
Giải thuật
Tổng ô trắng = k1+k2, cần 2w <= k1+k2. Tổng ô đen = 2n - (k1+k2), cần 2b <= 2n - k1 - k2. Cả hai điều kiện đều đúng thì có thể đặt.
Mã C++
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, int k1, int k2, int w, int b) {
if (2 * w <= (k1 + k2) && 2 * b <= (n - k1 + n - k2))
return true;
else
return false;
}
int main() {
int n = 5, k1 = 4, k2 = 3, w = 3, b = 1;
cout << solve(n, k1, k2, w, b) << endl;
}
Đầu vào / Đầu ra
Input: 5, 4, 3, 3, 1
Output: 1