SPOJ.com - Problem COWGIRL

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

COWGIRL - Cô gái chăn bò

Trên một thảo nguyên nhỏ bé có 1 gia đình gồm 3 anh em: 2 người anh trai là Nvutri và Andorea còn người em gái là Lola. Cuộc sống gia đình khá giả nhưng gia đình có truyền thống chăn nuôi và muốn để các con tự lập nên cha mẹ 3 người quyết định để các con hằng ngày sẽ đi chăn 1 số bò nào đó (tùy ý 3 người con).

Thảo nguyên là 1 cánh đồng chia làm M*N ô vuông, mỗi con bò chỉ đứng trong 1 ô và mỗi ô chỉ chứa 1 con bò.Chỉ có 1 quy tắc duy nhất là không bao giờ được để 4 con bò tạo thành 1 hình vuông 2*2 hoặc để trống 1 khu đất 2*2.

Hai người anh mải chơi nên đã hối lộ kem để Lola chăn bò 1 mình. Lola muốn biết tất cả có bao nhiêu cách xếp bò thỏa mãn quy tắc trên để đề phòng mọi trường hợp. Vì con số này rất lớn nên hãy giúp Lola tính toán con số này.

Input

Dòng đầu gồm 1 số T duy nhất là số test (T ≤ 111)

T dòng tiếp theo gồm 2 số M, N cho biết kích thước của thảo nguyên (M*N ≤ 30)

Output

Gồm T dòng, mỗi dòng ứng với 1 test là số cách xếp bò của test đó.

Example

Input:
1
1 1

Output:
2

Submit solution!

Được gửi lên bởi:	Nguyen Minh Hieu
Ngày:	2007-07-22
Thời gian chạy:	1s
Giới hạn mã nguồn:	10000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:	Thank to Nguyễn Trần Nam Khánh and Nguyễn Hoàng Nghĩa

hide comments

2020-05-23 05:03:00
Hoang Son sạch
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair <int,int>
#define pl pair <ll,ll>
#define fr(i,x,y) for (int i=x;i<=y;i++)
#define ft(i,x,y) for (int i=y;i>=x;i--)
#define N 100005
using namespace std ;
int n,m,f[34][500],res,T;
int get_bit(int t,int k)
{
return (t>>(k))&1;
}
int turn_off(int t,int k)
{
return (t^(1<<(k)));
}
void inp()
{
freopen("cowgirl.inp","r",stdin) ;
freopen("cowgirl.out","w",stdout);
cin>>T;
}
bool check(int x,int y)
{
fr(i,0,n-2)
{
int x1 = get_bit(x,i);
int x2 = get_bit(x,i+1);
int yy1 = get_bit(y,i);
int yy2 = get_bit(y,i+1);
if (x1==x2 and yy1==yy2 and x1==yy1) return false ;
}
return true;
}
void sub1()
{
cin>>n>>m;
if (n>m)
swap(n,m);
fr(i,1,m)
fr(j,0,(1<<n)-1)
f[i][j]=0;
fr(i,0,(1<<n)-1) f[1][i]=1;
fr(i,2,m)
{
fr(x,0,(1<<n)-1)
{
fr(y,0,(1<<n)-1)
{
if (check(x,y))
f[i][x]+=f[i-1][y];
}
}
}
fr(i,0,(1<<n)-1)
res+=f[m][i];
cout<<res<<"\n";
res = 0 ;
}
int main()
{
inp();
fr(iii,1,T)
{
sub1();
}
}

2019-10-24 05:11:06
quy hoạch động trạng thái rất khó. quay lui dễ hơn. đây là lời giải quay lui tối ưu full test
#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;
using ll = long long;
bool check(ll a, ll b, ll n)
{
for (ll i = 0; i < n - 1; i++)
{
if ((a & (1 << i)) && (a & (1 << (i + 1))) && (b & (1 << i)) && (b & (1 << (i + 1))))
return false;
if (!(a & (1 << i)) && !(a & (1 << (i + 1))) && !(b & (1 << i)) && !(b & (1 << (i + 1))))
return false;
}
return true;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("cowgirl.inp", "r", stdin);
#endif
ll t;
cin >> t;
while (t--)
{
ll m, n;
cin >> m >> n;
if (m < n)
swap(m, n);
vector<vector<ll>> adjacent(1 << n);
vector<ll> possible_states;
for (ll i = 0; i < (1 << n); i++)
for (ll j = 0; j < (1 << n); j++)
{
bool invalid_state = false;
if (!check(i, j, n))
continue;
adjacent[i].push_back(j);
}
for (ll i = 0; i < (1 << n); i++)
if (adjacent[i].size() > 0)
possible_states.push_back(i);
vector<vector<ll>> M(m, vector<ll>(1 << n, -1));
function<ll(ll, ll)> bt = [&](ll row, ll state) {
if (M[row][state] != -1)
return M[row][state];
ll sum = 0;
if (row == m - 1)
return M[row][state] = 1LL;
for (auto next : adjacent[state])
sum += bt(row + 1, next);
return M[row][state] = sum;
};
ll count = 0;
for (auto x : possible_states)
count += bt(0, x);
cout << count << "\n";
}
}

2019-09-14 03:43:24
trau cx AC :v
duonght_pro_xinhgainhathemattroi_:)

Last edit: 2019-09-26 00:54:32

2019-09-14 03:41:20
nhat hao ko sach

2019-09-14 03:40:41
hathuyduong bi dien hahaha

2019-09-14 03:39:50
HLD ez game ez life

2019-09-14 03:39:45
nhật hào sạch

2019-09-14 03:39:22
hahaha

2019-08-13 02:42:13
3 đấm mới AC =>>> nhớ long long nhé mấy bác

2019-07-16 16:10:05
nếu khó quá vào link này surviv.io

Giải bài trực tuyến

COWGIRL - Cô gái chăn bò

Input

Output

Example