fp.cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
//#define debug printf
#define debug blackhole
void blackhole(...) {}
#define NP 12
int PENT[NP][25] = {
{
0,0,0,0,0,
0,0,1,1,0,
0,1,1,0,0,
0,0,1,0,0,
0,0,0,0,0
},
{
0,0,1,0,0,
0,0,1,0,0,
0,0,1,0,0,
0,0,1,0,0,
0,0,1,0,0
},
{
0,0,1,0,0,
0,0,1,0,0,
0,0,1,0,0,
0,0,1,1,0,
0,0,0,0,0
},
{
0,0,0,1,0,
0,0,0,1,0,
0,0,1,1,0,
0,0,1,0,0,
0,0,0,0,0
},
{
0,0,1,1,0,
0,0,1,1,0,
0,0,1,0,0,
0,0,0,0,0,
0,0,0,0,0
},
{
0,0,0,0,0,
0,1,1,1,0,
0,0,1,0,0,
0,0,1,0,0,
0,0,0,0,0
},
{
0,0,0,0,0,
0,1,0,1,0,
0,1,1,1,0,
0,0,0,0,0,
0,0,0,0,0,
},
{
0,0,0,0,0,
0,1,0,0,0,
0,1,0,0,0,
0,1,1,1,0,
0,0,0,0,0,
},
{
0,0,0,0,0,
0,1,0,0,0,
0,1,1,0,0,
0,0,1,1,0,
0,0,0,0,0
},
{
0,0,0,0,0,
0,0,1,0,0,
0,1,1,1,0,
0,0,1,0,0,
0,0,0,0,0
},
{
0,0,0,0,0,
0,0,1,0,0,
0,1,1,0,0,
0,0,1,0,0,
0,0,1,0,0
},
{
0,0,0,0,0,
0,1,1,0,0,
0,0,1,0,0,
0,0,1,1,0,
0,0,0,0,0
}
};
int rnd[10][10][2];
int hash(int what[10][10]) {
int h=4523;
for (int i=0;i<10;i++) {
for (int j=0;j<10;j++) {
h ^= rnd[i][j][what[i][j] ? 1 : 0];
}
}
return h;
}
bool connected(int both[10][10]) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (both[i][j] != 1) continue;
if (j > 0 && both[i][j-1] == 2) return true;
if (j < 9 && both[i][j+1] == 2) return true;
if (i > 0 && both[i-1][j] == 2) return true;
if (i < 9 && both[i+1][j] == 2) return true;
}
}
return false;
}
void make_pent(int res[5][5], int x) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
res[i][j] = PENT[x][i * 5 + j];
}
}
}
void dump(int res[5][5]) {
for (int i=0;i<5;i++) {
for (int j=0;j<5;j++) {
debug("%c", res[i][j] ? 'X' : ' ');
}
debug("\n");
}
debug("\n");
}
void rotate_pent(int res[5][5]) {
int tmp[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
tmp[j][5 - i - 1] = res[i][j];
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
res[i][j] = tmp[i][j];
}
}
}
void flip_pent(int res[5][5]) {
int tmp[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
tmp[5 - i - 1][j] = res[i][j];
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
res[i][j] = tmp[i][j];
}
}
}
bool make_both(int both[10][10], int A, int Arot, int Aflip, int B, int Brot, int Bflip, int dx, int dy) {
int rA[5][5], rB[5][5];
make_pent(rA, A); make_pent(rB, B);
if (Aflip) flip_pent(rA);
if (Bflip) flip_pent(rB);
for (int r = 0; r < Arot; r++) rotate_pent(rA);
for (int r = 0; r < Brot; r++) rotate_pent(rB);
for (int i=0;i<10;i++) for (int j=0;j<10;j++) both[i][j] = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
both[i][j] = rA[i][j] ? 1 : 0;
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (!rB[i][j]) continue;
if (both[i+dx][j+dy]) return false;
both[i][j] = 2;
}
}
if (!connected(both)) return false;
return true;
}
set<pair<int, pair<int, int> > > pairs;
void generate() {
for (int A=0; A<NP;A++) {
for (int B=A;B<NP;B++) {
for (int Arot = 0; Arot < 4; Arot++) {
for (int Brot = 0; Brot < 4; Brot++) {
for (int Aflip=0;Aflip<2;Aflip++) {
for (int Bflip=0;Bflip<2;Bflip++) {
for (int dx=0;dx<=5;dx++) {
for (int dy=0;dy<=5;dy++) {
int both[10][10];
if (!make_both(both, A, Arot, Aflip, B, Brot, Bflip, dx, dy)) continue;
int h = hash(both);
pairs.insert(make_pair(h, make_pair(A,B)));
}
}}}
}
}
}
}
}
int locate(char c) {
char* names="FILNPTUVWXYZ";
for (int i = 0; names[i]; i++) {
if (names[i] == c) return i;
}
debug("ERROR!");
exit(1);
}
int main() {
int res[5][5];
make_pent(res, 5);
dump(res);
rotate_pent(res);
dump(res);
rotate_pent(res);
dump(res);
rotate_pent(res);
dump(res);
rotate_pent(res);
dump(res);
srand(0);
for (int i=0;i<10;i++) {
for (int j=0;j<10;j++) {
for (int k=0;k<2;k++) {
rnd[i][j][k] = rand();
}
}
}
generate();
// printf("%d\n", pairs.size());
set<pair<pair<int, int>, pair<int,int> > > all_pairs;
for (set<pair<int, pair<int,int> > >::iterator i = pairs.begin(); i != pairs.end(); i++) {
int h = i->first;
for (set<pair<int, pair<int,int> > >::iterator j = pairs.begin(); j != pairs.end(); j++) {
if (j->first == h) {
// debug("[(%d,%d) <=> (%d,%d)]\n", i->second.first, i->second.second, j->second.first, j->second.second);
int a = i->second.first, b = i->second.second, x = j->second.first, y = j->second.second;
all_pairs.insert(make_pair(make_pair(a, b), make_pair(x, y)));
all_pairs.insert(make_pair(make_pair(a, b), make_pair(y, x)));
all_pairs.insert(make_pair(make_pair(b, a), make_pair(x, y)));
all_pairs.insert(make_pair(make_pair(b, a), make_pair(y, x)));
}
}
}
// printf("\n");
while (true) {
char A[10], B[10];
if (scanf("%s%s", A, B) != 2) break;
int Ai = locate(A[0]), Aj = locate(A[1]), Bi = locate(B[0]), Bj = locate(B[1]);
debug("[%d %d] vs [%d %d]\n", Ai, Aj, Bi, Bj);
if (all_pairs.find(make_pair(make_pair(Ai,Aj),make_pair(Bi,Bj))) != all_pairs.end()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}