9 | 12月 | 2017 | 超客的水墨烟雨

uva508

maksyuki 发表于 oj 分类，标签: 基础算法-枚举

09 12月 2017

Samuel F. B. Morse is best known for the coding scheme that carries his name. Morse code is still used in international radio communication. The coding of text using Morse code is straightforward. Each character (case is insignificant) is translated to a predefined sequence of dits and dahs (the elements of Morse code). Dits are represented as periods (‘.’) and dahs are represented as hyphens or minus signs (‘-’). Each element is transmitted by sending a signal for some period of time. A dit is rather short, and a dah is, in perfectly formed code, three times as long as a dit. A short silent space appears between elements, with a longer space between characters. A still longer space separates words. This dependence on the spacing and timing of elements means that Morse code operators sometimes do not send perfect code. This results in difficulties for the receiving operator, but frequently the message can be decoded depending on context.

In this problem we consider reception of words in Morse code without spacing between letters. Without the spacing, it is possible for multiple words to be coded the same. For example, if the message “dit dit dit” were received, it could be interpreted as “EEE”, “EI”, “IE” or “S” based on the coding scheme shown in the sample input. To decide between these multiple interpretations, we assume a particular context by expecting each received word to appear in a dictionary.

For this problem your program will read a table giving the encoding of letters and digits into Morse code, a list of expected words (context), and a sequence of words encoded in Morse code (morse). These morse words may be flawed. For each morse word, your program is to determine the matching word from context, if any. If multiple words from context match morse, or if no word matches perfectly, your program will display the best matching word and a mismatch indicator.

If a single word from context matches morse perfectly, it will be displayed on a single line, by itself. If multiple context words match morse perfectly, then select the matching word with the fewest characters. If this still results in an ambiguous match, any of these matches may be displayed. If multiple context words exist for a given morse, the first matching word will be displayed followed by an exclamation point (‘!’).

We assume only a simple case of errors in transmission in which elements may be either truncated from the end of a morse word or added to the end of a morse word. When no perfect matches for morse are found, display the word from context that matches the longest prefix of morse, or has the fewest extra elements beyond those in morse. If multiple words in context match using these rules, any of these matches may be displayed. Words that do not match perfectly are displayed with a question mark (‘?’) suffixed.

The input data will only contain cases that fall within the preceding rules.

Input

The Morse code table will appear first and consists of lines each containing an uppercase letter or a digit C, zero or more blanks, and a sequence of no more than six periods and hyphens giving the Morse code for C. Blanks may precede or follow the items on the line. A line containing a single asterisk (‘*’), possibly preceded or followed by blanks, terminates the Morse code table. You may assume that there will be Morse code given for every character that appears in the context section.

The context section appears next, with one word per line, possibly preceded and followed by blanks. Each word in context will contain no more than ten characters. No characters other than upper case letters and digits will appear. Thered will be at most 100 context words. A line containing only a single asterisk (‘*’), possibly preceded or followed by blanks, terminates the context section.

The remainder of the input contains morse words separated by blanks or end-of-line characters. A line containing only a single asterisk (“*”), possibly preceded or followed by blanks, terminates the input. No morse word will have more than eighty (80) elements.

Output

For each input morse word, display the appropriate matching word from context followed by an exclamation mark (‘!’) or question mark (‘?’) if appropriate. Each word is to appear on a separate line starting in column one.

Sample Input

A .-
B -...
C -.-.
D -..
E .
F ..-.
G --.
H ....
I ..
J .---
K -.-
L .-..
M --
N -.
O ---
P .--.
Q --.-
R .-.
S ...
T -
U ..-
V ...-
W .--
X -..-
Y -.--
Z --..
0 ------
1 .-----
2 ..---
3 ...--
4 ....-
5 .....
6 -....
7 --...
8 ---..
9 ----.
*
AN
EARTHQUAKE
EAT
GOD
HATH
IM
READY
TO
WHAT
WROTH
*
.--.....-- .....--....
--.----.. .--.-.----..
.--.....-- .--.
..-.-.-....--.-..-.--.-.
..-- .-...--..-.--
---- ..--
*
Sample Output

WHAT
HATH
GOD
WROTH?
WHAT
AN
EARTHQUAKE
EAT!
READY
TO
EAT!

题目类型：暴力枚举

算法分析：使用map存下所有的字符编码表和每个单词编码后的结果，由于map中的string定义了小于符号，所以迭代到满足条件的第一个结果就是字典序最小的，注意没有精确匹配时需要寻找单词中编码与其距离最小的，距离相同时，输出字典序最小的，而这个只要顺序迭代就能满足

/**************************************************
filename       :r.cpp
author         :maksyuki
created time   :2017/12/9 15:28:25
last modified  :2017/12/9 15:47:49
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

map<char, string> tab;
map<string, string> dict;

string solve(string s) {
    int cnt = 0;
    string ans;
    bool is_first = true;
    for(map<string, string>:: iterator it = dict.begin(); it != dict.end(); it++) 
        if(s == it->second) {
            cnt++;
            if(is_first) {
                is_first = false;
                ans = it->first;
            }
        }

    if(cnt > 1) ans += "!";

    if(!cnt) {
        int minval = INF;
        string va, vb;
        for(map<string, string>:: iterator it = dict.begin(); it != dict.end(); it++) {
            va = s, vb = it->second;
            if(va.size() > vb.size()) swap(va, vb);
            if(va == vb.substr(0, va.size())) {
                int tmp = vb.size() - va.size();
                if(minval > tmp) {
                    minval = tmp;
                    ans = it->first;
                }
            }
        }
        ans += '?';
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    string sa, sb;
    while(cin >> sa) {
        cin >> sb;
        tab[sa[0]] = sb;

        while(cin >> sa) {
            if(sa == "*") break;
            cin >> sb;
            tab[sa[0]] = sb;
        }
        
        while(cin >> sa) {
            if(sa == "*") break;
            
            for(int i = 0; sa[i]; i++) dict[sa] += tab[sa[i]];
        }
        
       while(cin >> sa) {
           if(sa == "*") break;
            
           cout << solve(sa) << endl;
       }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

/**************************************************

filename :r.cpp

author :maksyuki

created time :2017/12/9 15:28:25

last modified :2017/12/9 15:47:49

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

map<char, string> tab;

map<string, string> dict;

string solve(string s) {

int cnt = 0;

string ans;

bool is_first = true;

for(map<string, string>:: iterator it = dict.begin(); it != dict.end(); it++)

if(s == it->second) {

cnt++;

if(is_first) {

is_first = false;

ans = it->first;

}

if(cnt > 1) ans += "!";

if(!cnt) {

int minval = INF;

string va, vb;

for(map<string, string>:: iterator it = dict.begin(); it != dict.end(); it++) {

va = s, vb = it->second;

if(va.size() > vb.size()) swap(va, vb);

if(va == vb.substr(0, va.size())) {

int tmp = vb.size() - va.size();

if(minval > tmp) {

minval = tmp;

ans = it->first;

}

ans += '?';

}

return ans;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

string sa, sb;

while(cin >> sa) {

cin >> sb;

tab[sa[0]] = sb;

while(cin >> sa) {

if(sa == "*") break;

cin >> sb;

tab[sa[0]] = sb;

}

while(cin >> sa) {

if(sa == "*") break;

for(int i = 0; sa[i]; i++) dict[sa] += tab[sa[i]];

}

while(cin >> sa) {

if(sa == "*") break;

cout << solve(sa) << endl;

}

return 0;

}

uva1590

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

09 12月 2017

Alex is administrator of IP networks. His clients have a bunch of individual IP addresses and he decided to group all those IP addresses into the smallest possible IP network.

Each IP address is a 4-byte number that is written byte-by-byte in a decimal dot-separated notation “byte0.byte1.byte2.byte3” (quotes are added for clarity). Each byte is written as a decimal number from 0 to 255 (inclusive) without extra leading zeroes.

IP network is described by two 4-byte numbers — network address and network mask. Both network address and network mask are written in the same notation as IP addresses.

In order to understand the meaning of network address and network mask you have to consider their binary representation. Binary representation of IP address, network address, and network mask consists of 32 bits: 8 bits for byte0 (most significant to least significant), followed by 8 bits for byte1, followed by 8 bits for byte2, and followed by 8 bits for byte3.

IP network contains a range of 2n IP addresses where 0 ≤ n ≤ 32. Network mask always has 32 − n first bits set to one, and n last bits set to zero in its binary representation. Network address has arbitrary 32 − n first bits, and n last bits set to zero in its binary representation. IP network contains all IP addresses whose 32 − n first bits are equal to 32 − n first bits of network address with arbitrary n last bits. We say that one IP network is smaller than the other IP network if it contains fewer IP addresses.

For example, IP network with network address 194.85.160.176 and network mask 255.255.255.248 contains 8 IP addresses from 194.85.160.176 to 194.85.160.183 (inclusive).

Input

The input file will contain several test cases, each of them as described below.

The first line of the input file contains a single integer number m (1 ≤ m ≤ 1000). The following m lines contain IP addresses, one address on a line. Each IP address may appear more than once in the input file.

Output

For each test case, write to the output file two lines that describe the smallest possible IP network that contains all IP addresses from the input file. Write network address on the first line and network mask on the second line.

Sample Input

194.85.160.177

194.85.160.183

194.85.160.178

Sample Output

194.85.160.176

255.255.255.248

题目类型：简单贪心

算法分析：从IP地址中的最高位开始枚举最长的公共子串，此时32-该串长度为题目中的n，之后按照要求输出即可

/**************************************************
filename       :o.cpp
author         :maksyuki
created time   :2017/12/9 9:03:35
last modified  :2017/12/9 10:01:00
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char si[66], s[1000+6][36];
int tmp[6], m;

void convert(int p) {
    int len = 1;
    int tmpv = 0;
    for(int i = 0; si[i]; i++) {
        if(si[i] == '.') {
            tmp[len++] = tmpv;
            tmpv = 0;
        }
        else tmpv = tmpv * 10 + (si[i] - '0');
    }
    tmp[len++] = tmpv;

    char ans[66];
    len = 0;
    bool is_first = true;
    for(int i = 1; i <= 4; i++) {
        int vv = tmp[i];
        while(vv) {
            ans[len++] = char(vv % 2 + '0');
            vv /= 2;
        }
        while(len <= 7) ans[len++] = '0';
        ans[len] = 0;

        //if(i > 1) strcat(s[p] + 1, ".");
        for(int i = 0; i < len / 2; i++) swap(ans[i], ans[len-1-i]);
        if(is_first) {
            is_first = false;
            strcpy(s[p] + 1, ans);
        }
        else strcat(s[p] + 1, ans);
        len = 0;
    }
}

char res[6][66];

int solve() {
    for(int i = 1; i <= 32; i++) {
        bool is_same = true;
        for(int j = 2; j <= m; j++)
            if(s[j][i] != s[1][i]) {
                is_same = false;
                break;
            }
        if(!is_same) return i - 1;
        res[1][i] = s[1][i];
    }
    return 32;
}

void rconvert(int p) {
    for(int i = 8; i <= 32; i += 8) {
        int tmp = 0, bb = 1; 
        for(int j = i; j >= i - 7; j--) {
            tmp += bb * (res[p][j] - '0');        
            bb <<= 1;
        }
        if(i > 8) printf(".");
        printf("%d", tmp);
        tmp = 0;
    }
    puts("");
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif

    while(scanf("%d", &m) != EOF) {
        for(int i = 1; i <= m; i++) {
            scanf(" %s", si);
            convert(i);
        }
            int vv = solve();
            for(int i = vv + 1; i <= 32; i++) res[1][i] = '0';
            res[1][33] = 0;
            
            for(int i = 1; i <= vv; i++) res[2][i] = '1';
            for(int i = vv + 1; i <= 32; i++) res[2][i] = '0';
            
            rconvert(1);
            rconvert(2);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

/**************************************************

filename :o.cpp

author :maksyuki

created time :2017/12/9 9:03:35

last modified :2017/12/9 10:01:00

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char si[66], s[1000+6][36];

int tmp[6], m;

void convert(int p) {

int len = 1;

int tmpv = 0;

for(int i = 0; si[i]; i++) {

if(si[i] == '.') {

tmp[len++] = tmpv;

tmpv = 0;

}

else tmpv = tmpv * 10 + (si[i] - '0');

}

tmp[len++] = tmpv;

char ans[66];

len = 0;

bool is_first = true;

for(int i = 1; i <= 4; i++) {

int vv = tmp[i];

while(vv) {

ans[len++] = char(vv % 2 + '0');

vv /= 2;

}

while(len <= 7) ans[len++] = '0';

ans[len] = 0;

//if(i > 1) strcat(s[p] + 1, ".");

for(int i = 0; i < len / 2; i++) swap(ans[i], ans[len-1-i]);

if(is_first) {

is_first = false;

strcpy(s[p] + 1, ans);

}

else strcat(s[p] + 1, ans);

len = 0;

}

char res[6][66];

int solve() {

for(int i = 1; i <= 32; i++) {

bool is_same = true;

for(int j = 2; j <= m; j++)

if(s[j][i] != s[1][i]) {

is_same = false;

break;

}

if(!is_same) return i - 1;

res[1][i] = s[1][i];

}

return 32;

}

void rconvert(int p) {

for(int i = 8; i <= 32; i += 8) {

int tmp = 0, bb = 1;

for(int j = i; j >= i - 7; j--) {

tmp += bb * (res[p][j] - '0');

bb <<= 1;

}

if(i > 8) printf(".");

printf("%d", tmp);

tmp = 0;

}

puts("");

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(scanf("%d", &m) != EOF) {

for(int i = 1; i <= m; i++) {

scanf(" %s", si);

convert(i);

}

int vv = solve();

for(int i = vv + 1; i <= 32; i++) res[1][i] = '0';

res[1][33] = 0;

for(int i = 1; i <= vv; i++) res[2][i] = '1';

for(int i = vv + 1; i <= 32; i++) res[2][i] = '0';

rconvert(1);

rconvert(2);

}

return 0;

}

uva253

maksyuki 发表于 oj 分类，标签: 基础算法-枚举

09 12月 2017

We have a machine for painting cubes. It is supplied with three different colors: blue, red and green. Each face of the cube gets one of these colors. The cube’s faces are numbered as in Figure 1.

Since a cube has 6 faces, our machine can paint a face-numbered cube in 3 6 = 729 different ways. When ignoring the face-numbers, the number of different paintings is much less, because a cube can be rotated. See example below.

We denote a painted cube by a string of 6 characters, where each character is a ‘b’, ‘r’, or ‘g’. The i-th character (1 ≤ i ≤ 6) from the left gives the color of face i. For example, Figure 2 is a picture of “rbgggr” and Figure 3 corresponds to “rggbgr”. Notice that both cubes are painted in the same way: by rotating it around the vertical axis by 90°, the one changes into the other.

Input

The input of your program is a textfile that ends with the standard end-of-file marker. Each line is a string of 12 characters. The first 6 characters of this string are the representation of a painted cube, the remaining 6 characters give you the representation of another cube. Your program determines whether these two cubes are painted in the same way, that is, whether by any combination of rotations one can be turned into the other. (Reflections are not allowed.)

Output

The output is a file of boolean. For each line of input, output contains ‘TRUE’ if the second half can be obtained from the first half by rotation as describes above, ‘FALSE’ otherwise.

Sample Input

rbgggrrggbgr
rrrbbbrrbbbr
rbgrbgrrrrrg

Sample Output

TRUE

FALSE

题目类型：暴力枚举

算法分析：首先枚举2个对面(顶面和底面)，然后对于每个确定的两个对面，枚举(旋转)4个面，判断的条件是所有的面都相等，一个小技巧是程序中使用的index数组，可以简化生成枚举对象的过程，下面第一个代码是更好的实现

/**************************************************
filename       :n.cpp
author         :maksyuki
created time   :2017/12/8 23:16:14
last modified  :2017/12/9 8:40:30
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

const int dx[] = {1, 2, 3};
const int dy[] = {6, 5, 4};
const int dv[3][4] = {{2, 4, 5, 3}, {1, 3, 6, 4}, {1, 2, 6, 5}};

char si[66], s[6][66];
char st[6][66], sbbt[66];

void cutchar(int pv, int p) {
    int len = 1;
    for(int i = 0; i < 4; i++)
        st[p][len++] = s[p][dv[pv][i]];
}

bool rotate() {
    st[1][5] = st[2][5] = 0;
    strcpy(sbbt, st[2] + 1);
    strcat(sbbt, st[2] + 1);
    if(strstr(sbbt, st[1] + 1) != NULL) return true;
    return false;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf("%s",  si + 1) != EOF) {
        for(int i = 1; i <= 6; i++) s[1][i] = si[i];
        for(int i = 7, j = 1; i <= 12; i++, j++) s[2][j] = si[i];
        
        bool is_right = false;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++) {
                cutchar(i, 1), cutchar(j, 2);
                if(rotate() && ((s[1][dx[i]] == s[2][dx[j]] && s[1][dy[i]] == s[2][dy[j]])
                             || (s[1][dx[i]] == s[2][dy[j]] && s[1][dy[i]] == s[2][dx[j]]))) {
                    is_right = true;
                    break;
                }
            }

        if(is_right) puts("TRUE");
        else puts("FALSE");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

/**************************************************

filename :n.cpp

author :maksyuki

created time :2017/12/8 23:16:14

last modified :2017/12/9 8:40:30

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

const int dx[] = {1, 2, 3};

const int dy[] = {6, 5, 4};

const int dv[3][4] = {{2, 4, 5, 3}, {1, 3, 6, 4}, {1, 2, 6, 5}};

char si[66], s[6][66];

char st[6][66], sbbt[66];

void cutchar(int pv, int p) {

int len = 1;

for(int i = 0; i < 4; i++)

st[p][len++] = s[p][dv[pv][i]];

}

bool rotate() {

st[1][5] = st[2][5] = 0;

strcpy(sbbt, st[2] + 1);

strcat(sbbt, st[2] + 1);

if(strstr(sbbt, st[1] + 1) != NULL) return true;

return false;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(scanf("%s", si + 1) != EOF) {

for(int i = 1; i <= 6; i++) s[1][i] = si[i];

for(int i = 7, j = 1; i <= 12; i++, j++) s[2][j] = si[i];

bool is_right = false;

for(int i = 0; i < 3; i++)

for(int j = 0; j < 3; j++) {

cutchar(i, 1), cutchar(j, 2);

if(rotate() && ((s[1][dx[i]] == s[2][dx[j]] && s[1][dy[i]] == s[2][dy[j]])

|| (s[1][dx[i]] == s[2][dy[j]] && s[1][dy[i]] == s[2][dx[j]]))) {

is_right = true;

break;

}

if(is_right) puts("TRUE");

else puts("FALSE");

}

return 0;

}

#include <iostream>
#include <fstream>
using namespace std;

const int index[8][8] = {{0, 1, 2, 3, 4, 5}, {1, 5, 2, 3, 0, 4}, {2, 1, 5, 0, 4, 3}
, {3, 5, 1, 4, 0, 2}, {4, 5, 3, 2, 0, 1}, {5, 1, 3, 2, 4, 0}};


char val_a[8], val_b[8], temp[8];

bool TestRotation ()
{
	int i, j;
	for (i = 0; i < 6; i++)
	{
		for (j = 0; j < 6; j++)
			temp[j] = val_b[index[i][j]];

		for (j= 0; j < 4; j++)
		{
			char ch = temp[1];
			temp[1] = temp[2];
			temp[2] = temp[4];
			temp[4] = temp[3];
			temp[3] = ch;

			int k;
			for (k = 0; k < 6; k++)
				if (temp[k] != val_a[k])
					break;

			if (k == 6)
				return true;
		}
	}

return false;
}


int main()
{
//	ifstream cin ("aaa.txt");

	char input[18];

	while (cin >> input)
	{
		int i;
		for (i = 0; i < 6; i++)
			val_a[i] = input[i];

		for (i = 0; i < 6; i++)
			val_b[i] = input[i+6];

		if (TestRotation ())
			cout << "TRUE" << endl;

		else
			cout << "FALSE" << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

const int index[8][8] = {{0, 1, 2, 3, 4, 5}, {1, 5, 2, 3, 0, 4}, {2, 1, 5, 0, 4, 3}

, {3, 5, 1, 4, 0, 2}, {4, 5, 3, 2, 0, 1}, {5, 1, 3, 2, 4, 0}};

char val_a[8], val_b[8], temp[8];

bool TestRotation ()

{

int i, j;

for (i = 0; i < 6; i++)

{

for (j = 0; j < 6; j++)

temp[j] = val_b[index[i][j]];

for (j= 0; j < 4; j++)

{

char ch = temp[1];

temp[1] = temp[2];

temp[2] = temp[4];

temp[4] = temp[3];

temp[3] = ch;

int k;

for (k = 0; k < 6; k++)

if (temp[k] != val_a[k])

break;

if (k == 6)

return true;

}

return false;

}

int main()

{

// ifstream cin ("aaa.txt");

char input[18];

while (cin >> input)

{

int i;

for (i = 0; i < 6; i++)

val_a[i] = input[i];

for (i = 0; i < 6; i++)

val_b[i] = input[i+6];

if (TestRotation ())

cout << "TRUE" << endl;

else

cout << "FALSE" << endl;

}

return 0;

}

超客的水墨烟雨

uva508

uva1590

uva253

分类目录

标签云

书签

近期评论

2017年12月
一	二	三	四	五	六	日
« 3月				1月 »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31