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

uva101

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

29 12月 2017

Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks.

In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will “program” a robotic arm to respond to a limited set of commands.

The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a flat table. Initially there are n blocks on the table (numbered from 0 to n − 1) with block bi adjacent to block bi+1 for all 0 ≤ i < n − 1 as shown in the diagram below:

The valid commands for the robot arm that manipulates blocks are:

• move a onto b

where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.

• move a over b

where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.

• pile a onto b

where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.

• pile a over b

where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.

• quit

terminates manipulations in the block world.

Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.

Input

The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.

The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.

You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

Output

The output should consist of the final state of the blocks world. Each original block position numbered i (0 ≤ i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don’t put any trailing spaces on a line.

There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).

Sample Input

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
Sample Output

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

题目类型：简单模拟

算法分析：用不定长数组进行计算，本题直接进行模拟即可。合理设计函数可以减少重复编码

/**************************************************
filename       :g.cpp
author         :maksyuki
created time   :2017/12/29 22:48:03
last modified  :2017/12/29 23:25: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 = 66;

vector<int> p[maxn];
int n;

int findp(int v) {
    for(int i = 0; i < n; i++) {
        int len = p[i].size();
        for(int j = 0; j < len; j++) 
            if(v == p[i][j]) return i;
    }
    return -1;
}

void clearp(int va, int vb) {
    int len = p[va].size();
    int pos = -1;
    for(int i = 0; i < len; i++)
        if(p[va][i] == vb) {
            pos = i; break;
        }

    for(int i = pos + 1; i < len; i++) p[p[va][i]].push_back(p[va][i]);
    p[va].resize(pos + 1);
}

void putp(int va, int vva, int vb) {
    int pa = -1, len = p[va].size();
    for(int i = 0; i < len; i++)
        if(p[va][i] == vva) {
            pa = i; break;
        }
    
    for(int i = pa; i < len; i++) p[vb].push_back(p[va][i]);
    p[va].resize(pa);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf("%d", &n) != EOF) {
        char op1[16], op2[16];
        int va, vb;
        for(int i = 0; i < maxn; i++) p[i].clear();
        for(int i = 0; i < n; i++) p[i].push_back(i);
        
        while(scanf(" %s", op1)) {
            if(!strcmp(op1, "quit")) break;

            scanf(" %d %s %d", &va, op2, &vb);
            int pa = findp(va);
            int pb = findp(vb);
            if(pa == pb) continue;

            if(!strcmp(op1, "move")) clearp(pa, va);
            if(!strcmp(op2, "onto")) clearp(pb, vb);

            putp(pa, va, pb);
        }
        for(int i = 0; i < n; i++) {
            printf("%d:", i);
            int len = p[i].size();
            for(int j = 0; j < len; j++) printf(" %d", p[i][j]);
            puts("");
        }
    }
    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

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

filename :g.cpp

author :maksyuki

created time :2017/12/29 22:48:03

last modified :2017/12/29 23:25: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 = 66;

vector<int> p[maxn];

int n;

int findp(int v) {

for(int i = 0; i < n; i++) {

int len = p[i].size();

for(int j = 0; j < len; j++)

if(v == p[i][j]) return i;

}

return -1;

}

void clearp(int va, int vb) {

int len = p[va].size();

int pos = -1;

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

if(p[va][i] == vb) {

pos = i; break;

}

for(int i = pos + 1; i < len; i++) p[p[va][i]].push_back(p[va][i]);

p[va].resize(pos + 1);

}

void putp(int va, int vva, int vb) {

int pa = -1, len = p[va].size();

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

if(p[va][i] == vva) {

pa = i; break;

}

for(int i = pa; i < len; i++) p[vb].push_back(p[va][i]);

p[va].resize(pa);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

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

char op1[16], op2[16];

int va, vb;

for(int i = 0; i < maxn; i++) p[i].clear();

for(int i = 0; i < n; i++) p[i].push_back(i);

while(scanf(" %s", op1)) {

if(!strcmp(op1, "quit")) break;

scanf(" %d %s %d", &va, op2, &vb);

int pa = findp(va);

int pb = findp(vb);

if(pa == pb) continue;

if(!strcmp(op1, "move")) clearp(pa, va);

if(!strcmp(op2, "onto")) clearp(pb, vb);

putp(pa, va, pb);

}

for(int i = 0; i < n; i++) {

printf("%d:", i);

int len = p[i].size();

for(int j = 0; j < len; j++) printf(" %d", p[i][j]);

puts("");

}

return 0;

}

uva10474

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

29 12月 2017

Raju and Meena love to play with Marbles. They have got a lot of marbles with numbers written on them. At the beginning, Raju would place the marbles one after another in ascending order of the numbers written on them. Then Meena would ask Raju to find the first marble with a certain number. She would count 1...2...3. Raju gets one point for correct answer, and Meena gets the point if Raju fails. After some fixed number of trials the game ends and the player with maximum points wins. Today it’s your chance to play as Raju. Being the smart kid, you’d be taking the favor of a computer. But don’t underestimate Meena, she had written a program to keep track how much time you’re taking to give all the answers. So now you have to write a program, which will help you in your role as Raju.

Input

There can be multiple test cases. Total no of test cases is less than 65. Each test case consists begins with 2 integers: N the number of marbles and Q the number of queries Mina would make. The next N lines would contain the numbers written on the N marbles. These marble numbers will not come in any particular order. Following Q lines will have Q queries. Be assured, none of the input numbers are greater than 10000 and none of them are negative.

Input is terminated by a test case where N = 0 and Q = 0.

Output

For each test case output the serial number of the case.

For each of the queries, print one line of output. The format of this line will depend upon whether or not the query number is written upon any of the marbles. The two different formats are described below:

• ‘x found at y’, if the first marble with number x was found at position y. Positions are numbered 1, 2, . . . , N.

• ‘x not found’, if the marble with number x is not present. Look at the output for sample input for details.

Sample Input

4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0

Sample Output

CASE# 1:

5 found at 4

CASE# 2:

2 not found

3 found at 3

题目类型：简单排序

算法分析：将数据按照递增序排好后使用二分查找是否存在给定值即可

/**************************************************
filename       :f.cpp
author         :maksyuki
created time   :2017/12/29 21:48:31
last modified  :2017/12/29 21:57:20
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;

int aa[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int N, Q, id = 1;
    while(scanf("%d %d", &N, &Q) != EOF) {
        if(!N && !Q) break;

        for(int i = 1; i <= N; i++) scanf(" %d", &aa[i]);
        sort(aa + 1, aa + 1 + N);
//1 2 3 5    
        int tmp;
        printf("CASE# %d:\n", id++);
        for(int i = 1; i <= Q; i++) {
            scanf(" %d", &tmp);
            int p = lower_bound(aa + 1, aa + 1 + N, tmp) - (aa + 1);
            if(aa[p+1] == tmp) printf("%d found at %d\n", tmp, p + 1);
            else printf("%d not found\n", tmp);
        }
    }
    return 0;
}

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

filename :f.cpp

author :maksyuki

created time :2017/12/29 21:48:31

last modified :2017/12/29 21:57:20

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;

int aa[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int N, Q, id = 1;

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

if(!N && !Q) break;

for(int i = 1; i <= N; i++) scanf(" %d", &aa[i]);

sort(aa + 1, aa + 1 + N);

//1 2 3 5

int tmp;

printf("CASE# %d:\n", id++);

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

scanf(" %d", &tmp);

int p = lower_bound(aa + 1, aa + 1 + N, tmp) - (aa + 1);

if(aa[p+1] == tmp) printf("%d found at %d\n", tmp, p + 1);

else printf("%d not found\n", tmp);

}

return 0;

}

uva509

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

27 12月 2017

RAID (Redundant Array of Inexpensive Disks) is a technique which uses multiple disks to store data. By storing the data on more than one disk, RAID is more fault tolerant than storing data on a single disk. If there is a problem with one of the disks, the system can still recover the original data provided that the remaining disks do not have corresponding problems.

One approach to RAID breaks data into blocks and stores these blocks on all but one of the disks. The remaining disk is used to store the parity information for the data blocks. This scheme uses vertical parity in which bits in a given position in data blocks are exclusive ORed to form the corresponding parity bit. The parity block moves between the disks, starting at the first disk, and moving to the next one in order. For instance, if there were five disks and 28 data blocks were stored on them, they would be arranged as follows:

With this arrangement of disks, a block size of two bits and even parity, the hexadecimal sample data 6C7A79EDFC (01101100 01111010 01111001 11101101 11111100 in binary) would be stored as:

If a block becomes unavailable, its information can still be retrieved using the information on the other disks. For example, if the first bit of the first block of disk 3 becomes unavailable, it can be reconstructed using the corresponding parity and data bits from the other four disks. We know that our sample system uses even parity:

0 ⊕ 0⊕? ⊕ 1 ⊕ 0 = 0

So the missing bit must be 1.

An arrangement of disks is invalid if a parity error is detected, or if any data block cannot be reconstructed because two or more disks are unavailable for that block.

Write a program to report errors and recover information from RAID disks.

Input

The input consists of several disk sets.

Each disk set has 3 parts. The first part of the disk set contains three integers on one line: the first integer d, 2 ≤ d ≤ 6, is the number of disks, the second integer s, 1 ≤ s ≤ 64, is the size of each block in bits, and the third integer b, 1 ≤ b ≤ 100, is the total number of data and parity blocks on each disk. The second part of the disk set is a single letter on a line, either ‘E’ signifying even parity or ‘O’ signifying odd parity. The third part of the disk set contains d lines, one for each disk, each holding s × b characters representing the bits on the disk, with the most significant bits first. Each bit will be specified as ‘0’ or ‘1’ if it holds valid data, or ‘x’ if that bit is unavailable. The end of input will be a disk set with d = 0. There will be no other data for this set which should not be processed.

Output

For each disk set in the input, display the number of the set and whether the set is valid or invalid. If the set is valid, display the recovered data bits in hexadecimal. If necessary, add extra ‘0’ bits at the end of the recovered data so the number of bits is always a multiple of 4. All output shall be appropriately labeled.

Sample Input

5 2 5
E
0001011111
0110111011
1011011111
1110101100
0010010111
3 2 5
E
0001111111
0111111011
xx11011111
3 5 1
O
11111
11xxx
x1111
0
Sample Output

Disk set 1 is valid, contents are: 6C7A79EDFC

Disk set 2 is invalid.

Disk set 3 is valid, contents are: FFC

题目类型：简单字符处理

算法分析：判断数据没损坏时校验对是否合法和数据损坏时是否最多只有一个数据损坏

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/12/27 20:59:10
last modified  :2017/12/27 22:15:38
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 aa[166][166][166];
char ans[166*166*166];
int d, s, b, id = 1;
char par;

//1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
//1 2 3 4 5 1 2 3 4  5  1  2  3  4  5

void print_ans() {
    memset(ans, 0, sizeof(ans));
    bool is_first = true;
    for(int i = 1; i <= b; i++) {
        for(int j = 1; j <= d; j++) {
            if(i % d == 0 && j == d) continue;
            if(i % d != 0 && (j == i % d)) continue;
            if(is_first) {
                is_first = false;
                strcpy(ans, aa[i][j]);
            }
            else strcat(ans, aa[i][j]);
        }
    }
    
    int len = strlen(ans);
    int alen = len;
    if(len % 4) alen = (len / 4) * 4 + 4;
    for(int i = len; i <= alen; i++) ans[i] = '0';
    ans[alen] = 0;

    for(int i = 0; i < alen; i += 4) {
        int val = 0;
        for(int j = i, cnt = 1; cnt <= 4; j++, cnt++)
            val = val * 2 + (ans[j] - '0');
        
        if(val < 10) printf("%c", val + '0');
        else printf("%c", val - 10 + 'A');
    }
    puts("");
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf("%d", &d) != EOF) {
        if(!d) break;
        
        scanf(" %d %d", &s, &b);
        scanf(" %c", &par);
    
        char tmp[166*166];
        for(int i = 1; i <= d; i++) {
            scanf(" %s", tmp);
            for(int j = 1, len = 0; j <= b; j++, len += s) {
                strncpy(aa[j][i], tmp + len, s);
                aa[j][i][s] = 0; 
            }
        }

        int org_par;
        if(par == 'E') org_par = 0;
        else org_par = 1;

        bool is_valid = true;
        for(int i = 1; i <= b; i++) {
            for(int j = 0; j < s; j++) {
                int cnt = 0, tmpv = -1, cnt_pos = -1;
                bool is_first = true;
                for(int k = 1; k <= d; k++) {
                    if(aa[i][k][j] != 'x') {
                        if(is_first) {
                            is_first = false;
                            tmpv = aa[i][k][j] - '0';
                        }
                        else tmpv ^= (aa[i][k][j] - '0');
                    }
                    else {
                        cnt++;
                        cnt_pos = k;
                    }
                }
                if(cnt >= 2 || (cnt == 0 && tmpv != org_par)) {
                    is_valid = false;
                    break;
                }
              
                if(cnt == 1) aa[i][cnt_pos][j] = char ('0' + (tmpv ^ org_par));
            }
            if(!is_valid) break;
        }
        
        printf("Disk set %d is ", id++);
        if(!is_valid) printf("invalid.\n");

        else {
            printf("valid, contents are: ");
            print_ans();
        }
    }
    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

153

154

155

156

157

158

159

160

161

162

163

164

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

filename :e.cpp

author :maksyuki

created time :2017/12/27 20:59:10

last modified :2017/12/27 22:15:38

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 aa[166][166][166];

char ans[166*166*166];

int d, s, b, id = 1;

char par;

//1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

//1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

void print_ans() {

memset(ans, 0, sizeof(ans));

bool is_first = true;

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

for(int j = 1; j <= d; j++) {

if(i % d == 0 && j == d) continue;

if(i % d != 0 && (j == i % d)) continue;

if(is_first) {

is_first = false;

strcpy(ans, aa[i][j]);

}

else strcat(ans, aa[i][j]);

}

int len = strlen(ans);

int alen = len;

if(len % 4) alen = (len / 4) * 4 + 4;

for(int i = len; i <= alen; i++) ans[i] = '0';

ans[alen] = 0;

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

int val = 0;

for(int j = i, cnt = 1; cnt <= 4; j++, cnt++)

val = val * 2 + (ans[j] - '0');

if(val < 10) printf("%c", val + '0');

else printf("%c", val - 10 + 'A');

}

puts("");

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

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

if(!d) break;

scanf(" %d %d", &s, &b);

scanf(" %c", &par);

char tmp[166*166];

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

scanf(" %s", tmp);

for(int j = 1, len = 0; j <= b; j++, len += s) {

strncpy(aa[j][i], tmp + len, s);

aa[j][i][s] = 0;

}

int org_par;

if(par == 'E') org_par = 0;

else org_par = 1;

bool is_valid = true;

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

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

int cnt = 0, tmpv = -1, cnt_pos = -1;

bool is_first = true;

for(int k = 1; k <= d; k++) {

if(aa[i][k][j] != 'x') {

if(is_first) {

is_first = false;

tmpv = aa[i][k][j] - '0';

}

else tmpv ^= (aa[i][k][j] - '0');

}

else {

cnt++;

cnt_pos = k;

}

if(cnt >= 2 || (cnt == 0 && tmpv != org_par)) {

is_valid = false;

break;

}

if(cnt == 1) aa[i][cnt_pos][j] = char ('0' + (tmpv ^ org_par));

}

if(!is_valid) break;

}

printf("Disk set %d is ", id++);

if(!is_valid) printf("invalid.\n");

else {

printf("valid, contents are: ");

print_ans();

}

return 0;

}

uva1591

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

23 12月 2017

Dr. Tuple is working on the new data-mining application for Advanced Commercial Merchandise Inc. One of the subroutines for this application works with two arrays P and Q containing N records of data each (records are numbered from 0 to N − 1). Array P contains hash-like structure with keys. Array P is used to locate record for processing and the data for the corresponding record is later retrieved from the array Q.

All records in array P have a size of SP bytes and records in array Q have size of SQ bytes. Dr. Tuple needs to implement this subroutine with the highest possible performance because it is a hot-spot of the whole data-mining application. However, SP and SQ are only known at run-time of application which complicates or makes impossible to make certain well-known compile-time optimizations.

The straightforward way to find byte-offset of i-th record in array P is to use the following formula:

Pofs(i) = SP · i, (1)

and the following formula for array Q:

Qofs(i) = SQ · i. (2)

However, multiplication computes much slower than addition or subtraction in modern processors. Dr. Tuple avoids usage of multiplication while scanning array P by keeping computed byte-offset Pofs(i) of i-th record instead of its index i in all other data-structures of data-mining application. He uses the following simple formulae when he needs to compute byte-offset of the record that precedes or follows i-th record in array P:

Pofs(i + 1) = Pofs(i) + SP

Pofs(i − 1) = Pofs(i) − SP

Whenever a record from array P is located by either scanning of the array or by taking Pofs(i) from other data structures, Dr. Tuple needs to retrieve information from the corresponding record in array Q. To access record in array Q its byte-offset Qofs(i) needs to be computed. One can immediately derive formula to compute Qofs(i) with known Pofs(i) from formulae (1) and (2):

Qofs(i) = Pofs(i)/SP · SQ (3)

Unfortunately, this formula not only contains multiplication, but also contains division. Even though only integer division is required here, it is still an order of magnitude slower than multiplication on modern processors. If coded this way, its computation is going to consume the most of CPU time in data-mining application for ACM Inc.

After some research Dr. Tuple has discovered that he can replace formula (3) with the following fast formula:

Qofs’(i) = (Pofs(i) + Pofs(i) << A) >> B (4)

where A and B are non-negative integer numbers, “<< A” is left shift by A bits (equivalent to integer multiplication by 2A), “ >> B” is right shift by B bits (equivalent to integer division by 2B).

This formula is an order of magnitude faster than (3) to compute, but it generally cannot always produce the same result as (3) regardless of the choice for values of A and B. It still can be used if one is willing to sacrifice some extra memory.

Conventional layout of array Q in memory (using formula (2)) requires N · SQ bytes to store the entire array. Dr. Tuple has found that one can always choose such K that if he allocates K bytes of memory for the array Q (where K ≤ N · SQ) and carefully selects values for A and B, the fast formula (4) will give non-overlapping storage locations for each of the N records of array Q.

Your task is to write a program that finds minimal possible amount of memory K that needs to be allocated for array Q when formula (4) is used. Corresponding values for A and B are also to be found. If multiple pairs of values for A and B give the same minimal amount of memory K, then the pair where A is minimal have to be found, and if there is still several possibilities, the one where B is minimal. You shall assume that integer registers that will be used to compute formula (4) are wide enough so that overflow will never occur.

Input

Input consists of several datasets. Each dataset consists of three integer numbers N, SP , and SQ separated by spaces (1 ≤ N ≤ 2 20 , 1 ≤ SP ≤ 2 10 , 1 ≤ SQ ≤ 2 10).

Output

For each dataset, write to the output file a single line with three integer numbers K, A, and B separated by spaces.

Sample Input

20 3 5
1024 7 1

Sample Output

119 0 0

1119 2 5

题目类型；简单枚举

算法分析：按照题目要求对A和B暴力枚举即可

/**************************************************
filename       :d.cpp
author         :maksyuki
created time   :2017/12/23 18:54:16
last modified  :2017/12/23 19:01:56
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;

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    LL n, sp, sq;
    while(scanf("%lld %lld %lld", &n, &sp, &sq) != EOF) {
        LL ans = (1LL << 62);
        LL va = -1, vb = -1;
        for(int i = 0; i < 32; i++)
            for(int j = 0; j < 32; j++) {
                LL tmp = (((n - 1) * sp + (((n - 1) * sp) << i)) >> j) + sq;
                if(tmp >= n * sq && tmp < ans) {
                    ans = tmp;
                    va = i, vb = j;
                }
            }
        printf("%lld %lld %lld\n", ans, va, vb);
    }
    return 0;
}

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

filename :d.cpp

author :maksyuki

created time :2017/12/23 18:54:16

last modified :2017/12/23 19:01:56

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;

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

LL n, sp, sq;

while(scanf("%lld %lld %lld", &n, &sp, &sq) != EOF) {

LL ans = (1LL << 62);

LL va = -1, vb = -1;

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

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

LL tmp = (((n - 1) * sp + (((n - 1) * sp) << i)) >> j) + sq;

if(tmp >= n * sq && tmp < ans) {

ans = tmp;

va = i, vb = j;

}

printf("%lld %lld %lld\n", ans, va, vb);

}

return 0;

}

uva12108

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

23 12月 2017

When a student is too tired, he can’t help sleeping in class, even if his favorite teacher is right here in front of him. Imagine you have a class of extraordinarily tired students, how long do you have to wait, before all the students are listening to you and won’t sleep any more? In order to complete this task, you need to understand how students behave.

When a student is awaken, he struggles for a minutes listening to the teacher (after all, it’s too bad to sleep all the time). After that, he counts the number of awaken and sleeping students (including himself). If there are strictly more sleeping students than awaken students, he sleeps for b minutes. Otherwise, he struggles for another a minutes, because he knew that when there is only very few sleeping students, there is a big chance for them to be punished! Note that a student counts the number of sleeping students only when he wants to sleep again.

Now that you understand each student could be described by two integers a and b, the length of awaken and sleeping period. If there are always more sleeping students, these two periods continue again and again. We combine an awaken period with a sleeping period after it, and call the combined period an awaken-sleeping period. For example, a student with a = 1 and b = 4 has an awaken-sleeping period of awaken-sleeping-sleeping-sleeping-sleeping. In this problem, we need another parameter c (1 ≤ c ≤ a + b) to describe a student’s initial condition: the initial position in his awaken-sleeping period. The 1st and 2nd position of the period discussed above are awaken and sleeping, respectively.

Now we use a triple (a, b, c) to describe a student. Suppose there are three students (2, 4, 1), (1, 5, 2) and (1, 4, 3), all the students will be awaken at time 18. The details are shown in the table below.

Write a program to calculate the first time when all the students are not sleeping.

Input

The input consists of several test cases. The first line of each case contains a single integer n (1 ≤ n ≤ 10), the number of students. This is followed by n lines, each describing a student. Each of these lines contains three integers a, b, c (1 ≤ a, b ≤ 5), described above. The last test case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the first time all the students are awaken. If it’ll never happen, output ‘-1’.

Sample Input

3
2 4 1
1 5 2
1 4 3
3
1 2 1
1 2 2
1 2 3
0

Sample Output

Case 1: 18

Case 2: -1

题目类型：简单模拟

算法分析：最大枚举的范围为所有成员周期之积，超出即输出-1，然后对于每个时间位置模拟每个人的操作即可

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2017/12/22 20:10:53
last modified  :2017/12/23 18:27:28
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;

struct node {
    int a, b, c, p;
    int cur;
};

node aa[66];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int n, id = 1;
    while(scanf("%d", &n) != EOF) {
        if(!n) break;
        
        int len = 1;
        for(int i = 1; i <= n; i++) {
            scanf("%d %d %d", &aa[i].a, &aa[i].b, &aa[i].c);
            aa[i].p = aa[i].a + aa[i].b;
            aa[i].cur = aa[i].c;
            len *= aa[i].p;
        }
            
        int ans = -1;
        int awk = 0, slp = 0;
        for(int i = 1; i <= n; i++) {
            if(aa[i].cur <= aa[i].a) awk++;
            else slp++;
        }
        
        int awk_pre = awk, slp_pre = slp;
        for(int i = 2; i <= len; i++) {
            
//            for(int j = 1; j <= n; j++) DB(aa[j].cur);
            for(int j = 1; j <= n; j++) {
                if(aa[j].cur == aa[j].a) {
                    if(awk_pre >= slp_pre) aa[j].cur = 1;
                    else {
                        aa[j].cur++;
                        awk--, slp++;
                    }
                }
                else {
                    if(aa[j].cur == aa[j].p) {
                        aa[j].cur = 1, awk++, slp--;
                    }
                    else aa[j].cur++;
                }
            }
            awk_pre = awk, slp_pre = slp;
//            cout << i << endl;
//            DB(awk), DB(slp);
//            cout << endl;
            if(awk == n) {
                ans = i;
                break;
            }
        }
        
        printf("Case %d: %d\n", id++, ans);

    }
    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

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

filename :c.cpp

author :maksyuki

created time :2017/12/22 20:10:53

last modified :2017/12/23 18:27:28

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;

struct node {

int a, b, c, p;

int cur;

};

node aa[66];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int n, id = 1;

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

if(!n) break;

int len = 1;

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

scanf("%d %d %d", &aa[i].a, &aa[i].b, &aa[i].c);

aa[i].p = aa[i].a + aa[i].b;

aa[i].cur = aa[i].c;

len *= aa[i].p;

}

int ans = -1;

int awk = 0, slp = 0;

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

if(aa[i].cur <= aa[i].a) awk++;

else slp++;

}

int awk_pre = awk, slp_pre = slp;

for(int i = 2; i <= len; i++) {

// for(int j = 1; j <= n; j++) DB(aa[j].cur);

for(int j = 1; j <= n; j++) {

if(aa[j].cur == aa[j].a) {

if(awk_pre >= slp_pre) aa[j].cur = 1;

else {

aa[j].cur++;

awk--, slp++;

}

else {

if(aa[j].cur == aa[j].p) {

aa[j].cur = 1, awk++, slp--;

}

else aa[j].cur++;

}

awk_pre = awk, slp_pre = slp;

// cout << i << endl;

// DB(awk), DB(slp);

// cout << endl;

if(awk == n) {

ans = i;

break;

}

printf("Case %d: %d\n", id++, ans);

}

return 0;

}

uva815

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

18 12月 2017

To enable homebuyers to estimate the cost of flood insurance, a real-estate firm provides clients with the elevation of each 10-meter by 10-meter square of land in regions where homes may be purchased. Water from rain, melting snow, and burst water mains will collect first in those squares with the lowest elevations, since water from squares of higher elevation will run downhill. For simplicity, we also assume that storm sewers enable water from high-elevation squares in valleys (completely enclosed by still higher elevation squares) to drain to lower elevation squares, and that water will not be absorbed by the land.

From weather data archives, we know the typical volume of water that collects in a region. As prospective homebuyers, we wish to know the elevation of the water after it has collected in lowlying squares, and also the percentage of the region’s area that is completely submerged (that is, the percentage of 10-meter squares whose elevation is strictly less than the water level). You are to write the program that provides these results.

Input

The input consists of a sequence of region descriptions. Each begins with a pair of integers, m and n, each less than 30, giving the dimensions of the rectangular region in 10-meter units. Immediately following are m lines of n integers giving the elevations of the squares in row-major order. Elevations are given in meters, with positive and negative numbers representing elevations above and below sea level, respectively. The final value in each region description is an integer that indicates the number of cubic meters of water that will collect in the region. A pair of zeroes follows the description of the last region.

Output

For each region, display the region number (1, 2, . . . ), the water level (in meters above or below sea level) and the percentage of the region’s area under water, each on a separate line. The water level and percentage of the region’s area under water are to be displayed accurate to two fractional digits. Follow the output for each region with a blank line.

Sample Input

3 3
25 37 45
51 12 34
94 83 27
10000
0 0

Sample Output

Region 1

Water level is 46.67 meters.

66.67 percent of the region is under water.

题目类型：简单模拟

算法分析：对于求解来说每个格子的位置不重要，可以将格子按照高度递增排列成一排，然后依次从最小的格子开始填起，剩余不到的体积最后处理一下即可

/**************************************************
filename       :b.cpp
author         :maksyuki
created time   :2017/12/18 11:02:04
last modified  :2017/12/18 11:16:25
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;

int aa[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int n, m, id = 1;
    while(scanf("%d %d", &m, &n) != EOF) {
        if(!m && !n) break;
        
        int len = m * n;
        for(int i = 1; i <= len; i++) scanf(" %d", &aa[i]);
        sort(aa + 1, aa + 1 + len);

        int v;
        scanf("%d", &v);
        
        int tmp = 0, i;
        for(i = 1; i <= len - 1; i++) {
            int tt = i * 10 * 10 * (aa[i+1] - aa[i]);
            if(tmp + tt > v) break;
            tmp += tt;
        }
        
        printf("Region %d\n", id++);
        double ans = aa[i] + (v - tmp) / (10.0 * 10.0 * i);
        printf("Water level is %.2lf meters.\n", ans);
        printf("%.2lf percent of the region is under water.\n\n", i * 1.0 / len * 100);
    }
    return 0;
}

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

filename :b.cpp

author :maksyuki

created time :2017/12/18 11:02:04

last modified :2017/12/18 11:16:25

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;

int aa[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int n, m, id = 1;

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

if(!m && !n) break;

int len = m * n;

for(int i = 1; i <= len; i++) scanf(" %d", &aa[i]);

sort(aa + 1, aa + 1 + len);

int v;

scanf("%d", &v);

int tmp = 0, i;

for(i = 1; i <= len - 1; i++) {

int tt = i * 10 * 10 * (aa[i+1] - aa[i]);

if(tmp + tt > v) break;

tmp += tt;

}

printf("Region %d\n", id++);

double ans = aa[i] + (v - tmp) / (10.0 * 10.0 * i);

printf("Water level is %.2lf meters.\n", ans);

printf("%.2lf percent of the region is under water.\n\n", i * 1.0 / len * 100);

}

return 0;

}

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;

}

uva220

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

08 12月 2017

Othello is a game played by two people on an 8 x 8 board, using disks that are white on one side and black on the other. One player places disks with the white side up and the other player places disks with the black side up. The players alternate placing one disk on an unoccupied space on the board. In placing a disk, the player must bracket at least one of the other color disks. Disks are bracketed if they are in a straight line horizontally, vertically, or diagonally, with a disk of the current player’s color at each end of the line. When a move is made, all the disks that were bracketed are changed to the color of the player making the move. (It is possible that disks will be bracketed across more than one line in a single move.)

Write a program to read a series of Othello games.

Input

The first line of the input is the number of games to be processed. Each game consists of a board configuration followed by a list of commands. The board configuration consists of 9 lines. The first 8 specify the current state of the board. Each of these 8 lines contains 8 characters, and each of these characters will be one of the following:

‘-’ indicating an unoccupied square

‘B’ indicating a square occupied by a black disk

‘W’ indicating a square occupied by a white disk

The ninth line is either a ‘B’ or a ‘W’ to indicate which is the current player. You may assume that the data is legally formatted.

Then a set of commands follows. The commands are to list all possible moves for the current player, make a move, or quit the current game. There is one command per line with no blanks in the input.

Output

The commands and the corresponding outputs are formatted as follows:

List all possible moves for the current player. The command is an ‘L’ in the first column of the line. The program should go through the board and print all legal moves for the current player in the format (x, y) where x represents the row of the legal move and y represents its column. These moves should be printed in row major order which means:

1) all legal moves in row number i will be printed before any legal move in row number j if j is greater than i and

2) if there is more than one legal move in row number i, the moves will be printed in ascending order based on column number.

All legal moves should be put on one line. If there is no legal move because it is impossible for the current player to bracket any pieces, the program should print the message ‘No legal move.’

Make a move.

The command is an ‘M’ in the first column of the line, followed by 2 digits in the second and third column of the line. The digits are the row and the column of the space to place the piece of the current player’s color, unless the current player has no legal move. If the current player has no legal move, the current player is first changed to the other player and the move will be the move of the new current player. You may assume that the move is then legal. You should record the changes to the board, including adding the new piece and changing the color of all bracketed pieces. At the end of the move, print the number of pieces of each color on the board in the format ‘Black - xx White - yy’ where xx is the number of black pieces on the board and yy is the number of white pieces on the board. After a move, the current player will be changed to the player that did not move.

Quit the current game.

The command will be a ‘Q’ in the first column of the line. At this point, print the final board configuration using the same format as was used in the input. This terminates input for the current game.

You may assume that the commands will be syntactically correct. Put one blank line between output from separate games and no blank lines anywhere else in the output.

Sample Input

2
--------
--------
--------
---WB---
---BW---
--------
--------
--------
W
L
M35
L
Q
WWWWB---
WWWB----
WWB-----
WB------
--------
--------
--------
--------
B
L
M25
L
Q

Sample Output

(3,5) (4,6) (5,3) (6,4)
Black - 1 White - 4
(3,4) (3,6) (5,6)
--------
--------
----W---
---WW---
---BW---
--------
--------
--------
No legal move.
Black - 3 White - 12
(3,5)
WWWWB---
WWWWW---
WWB-----
WB------
--------
--------
--------
--------

题目类型：简单模拟

算法分析：按照题目的要求直接分类模拟输出即可，注意最后一个测试用例的最后没有多余的空行，输出棋子个数时的格式和一个位置可能存在夹住异色棋子的多个状态，下面第一个代码是更好的实现

/**************************************************
filename       :m.cpp
author         :maksyuki
created time   :2017/12/8 20:54:53
last modified  :2017/12/8 22:29:29
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, 1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

char ga[16][16];
int gb[16][16];
bool vis[16][16];

struct node {
    int x, y;
    node () {};
    node (int xx, int yy): x(xx), y(yy) {};
};

int len;
node aa[maxn];

bool is_inline(int x, int y) {
    if(x >= 1 && x <= 8 && y >= 1 && y <= 8) return true;
    return false;
}

void findv(int user) {
    for(int i = 1; i <= 8; i++) 
        for(int j = 1; j <= 8; j++) {
            if(gb[i][j]) continue;
            for(int k = 0; k < 8; k++) {
                int tmpx = i + dx[k], tmpy = j + dy[k];
                bool is_change = false;
                while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {
                    tmpx += dx[k], tmpy += dy[k];
                    is_change = true;
                }
                if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy] && is_change && !vis[i][j]) {
                    aa[len++] = node(i, j);
                    vis[i][j] = true; 
                }
            }
        }
}

void move(int user, int xx, int yy) {
    gb[xx][yy] = user;
    for(int i = 0; i < 8; i++) {
        int tmpx = xx + dx[i], tmpy = yy + dy[i];
        while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {
            tmpx += dx[i], tmpy += dy[i];
        }
        if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy]) {
            int ax = xx, ay = yy;
            while(1) {
                if(ax == tmpx && ay == tmpy) break;
                gb[ax][ay] = user;
                ax += dx[i], ay += dy[i];
            }
        }
    }

    int cntb = 0, cntw = 0;
    for(int i = 1; i <= 8; i++)
        for(int j = 1; j <= 8; j++) {
            if(gb[i][j] == -1) cntb++;
            if(gb[i][j] == 1) cntw++;
        }

    printf("Black -%3d White -%3d\n", cntb, cntw);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t, id = 1;
    scanf("%d", &t);
    while(t--) {
        for(int i = 1; i <= 8; i++) scanf(" %s", (ga[i] + 1));
       
        memset(gb, 0, sizeof(gb));
        for(int i = 1; i <= 8; i++)
            for(int j = 1; j <= 8; j++) {
                if(ga[i][j] == 'B') gb[i][j] = -1;
                if(ga[i][j] == 'W') gb[i][j] = 1;
            }

        char tmp;
        int user;
        scanf(" %c", &tmp);
        if(tmp == 'B') user = -1;
        else user = 1;
        
        if(id++ > 1) puts("");

        char cmd[16];
        while(scanf(" %s", cmd)) {
            if(!strcmp(cmd, "Q")) {
                for(int i = 1; i <= 8; i++) {
                    for(int j = 1; j <= 8; j++) {
                        if(gb[i][j] == -1) printf("B");
                        if(gb[i][j] == 0) printf("-");
                        if(gb[i][j] == 1) printf("W");
                    }
                    puts("");
                }
                break;
            }

            if(!strcmp(cmd, "L")) {
                len = 0;
                memset(vis, false, sizeof(vis));
                findv(user);
                if(!len) puts("No legal move.");
                else {
                    for(int i = 0; i < len; i++) {
                        if(i) printf(" ");
                        printf("(%d,%d)", aa[i].x, aa[i].y);
                    }
                    puts("");
                }
            }
            
            else {
                int xx = cmd[1] - '0', yy = cmd[2] - '0';
                len = 0;
                memset(vis, false, sizeof(vis));
                findv(user);             
                if(!len) user = -user;
                move(user, xx, yy); 
                user = -user;
            }
        }
    }
    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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

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

filename :m.cpp

author :maksyuki

created time :2017/12/8 20:54:53

last modified :2017/12/8 22:29:29

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, 1, 0, 0, -1, -1, 1, 1};

const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

char ga[16][16];

int gb[16][16];

bool vis[16][16];

struct node {

int x, y;

node () {};

node (int xx, int yy): x(xx), y(yy) {};

};

int len;

node aa[maxn];

bool is_inline(int x, int y) {

if(x >= 1 && x <= 8 && y >= 1 && y <= 8) return true;

return false;

}

void findv(int user) {

for(int i = 1; i <= 8; i++)

for(int j = 1; j <= 8; j++) {

if(gb[i][j]) continue;

for(int k = 0; k < 8; k++) {

int tmpx = i + dx[k], tmpy = j + dy[k];

bool is_change = false;

while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {

tmpx += dx[k], tmpy += dy[k];

is_change = true;

}

if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy] && is_change && !vis[i][j]) {

aa[len++] = node(i, j);

vis[i][j] = true;

}

void move(int user, int xx, int yy) {

gb[xx][yy] = user;

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

int tmpx = xx + dx[i], tmpy = yy + dy[i];

while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {

tmpx += dx[i], tmpy += dy[i];

}

if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy]) {

int ax = xx, ay = yy;

while(1) {

if(ax == tmpx && ay == tmpy) break;

gb[ax][ay] = user;

ax += dx[i], ay += dy[i];

}

int cntb = 0, cntw = 0;

for(int i = 1; i <= 8; i++)

for(int j = 1; j <= 8; j++) {

if(gb[i][j] == -1) cntb++;

if(gb[i][j] == 1) cntw++;

}

printf("Black -%3d White -%3d\n", cntb, cntw);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t, id = 1;

scanf("%d", &t);

while(t--) {

for(int i = 1; i <= 8; i++) scanf(" %s", (ga[i] + 1));

memset(gb, 0, sizeof(gb));

for(int i = 1; i <= 8; i++)

for(int j = 1; j <= 8; j++) {

if(ga[i][j] == 'B') gb[i][j] = -1;

if(ga[i][j] == 'W') gb[i][j] = 1;

}

char tmp;

int user;

scanf(" %c", &tmp);

if(tmp == 'B') user = -1;

else user = 1;

if(id++ > 1) puts("");

char cmd[16];

while(scanf(" %s", cmd)) {

if(!strcmp(cmd, "Q")) {

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

for(int j = 1; j <= 8; j++) {

if(gb[i][j] == -1) printf("B");

if(gb[i][j] == 0) printf("-");

if(gb[i][j] == 1) printf("W");

}

puts("");

}

break;

}

if(!strcmp(cmd, "L")) {

len = 0;

memset(vis, false, sizeof(vis));

findv(user);

if(!len) puts("No legal move.");

else {

for(int i = 0; i < len; i++) {

if(i) printf(" ");

printf("(%d,%d)", aa[i].x, aa[i].y);

}

puts("");

}

else {

int xx = cmd[1] - '0', yy = cmd[2] - '0';

len = 0;

memset(vis, false, sizeof(vis));

findv(user);

if(!len) user = -user;

move(user, xx, yy);

user = -user;

}

return 0;

}

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

const int dx[] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 1};

const int maxn = 12;

char game[maxn][maxn];
int sum_b, sum_w;
char cur_player;

void CalcNumber ()
{
	sum_b = 0, sum_w = 0;

	int i, j;
	for (i = 0; i < 8; i++)
		for (j = 0; j < 8; j++)
		{
			if (game[i][j] == 'W')
				sum_w++;

			else if (game[i][j] == 'B')
				sum_b++;
		}
}


void OutPut ()
{
	int i;
	for (i = 0; i < 8; i++)
		cout << game[i] << endl;
}

inline char Opposite (char val)
{
	if (val == 'B')
		return 'W';

return 'B';
}

void Change (char &val)
{
	if (val == 'B')
		val = 'W';

	else
		val = 'B';
}


inline bool OkMove (int x, int y)
{
	if (x >= 0 && x <= 7 && y >= 0 && y <= 7 && game[x][y] == Opposite (cur_player))
		return true;

return false;
}

void PaintPoint (int x, int y, int loc)
{
	game[x][y] = cur_player;
	while (OkMove (x + dx[loc], y + dy[loc]))
	{
		x += dx[loc];
		y += dy[loc];
		game[x][y] = cur_player;
	}
}


bool Search (int x, int y, int loc)
{

	while (OkMove (x + dx[loc], y + dy[loc]))
	{
		x += dx[loc];
		y += dy[loc];
	}

	int temp_x = x + dx[loc];
	int temp_y = y + dy[loc];

	if (temp_x >= 0 && temp_x <= 7 && temp_y >= 0 && temp_y <= 7
	&& game[temp_x][temp_y] == cur_player)
		return true;

return false;
}

void ShowLegalPosition ()
{
	bool is_first = true;

	int i;
	for (i = 0; i < 8; i++)
	{
		int j;
		for (j = 0; j < 8; j++)
		{
			int k;
			for (k = 0; k < 8; k++)
				if (game[i][j] == '-' && OkMove (i + dx[k], j + dy[k]))
				{	//game[i][j] == '-' is important!!!
						if (Search (i, j, k))
						{
							if (is_first)
							{
								is_first = false;
								cout << "(" << i + 1 << "," << j + 1 << ")";
							}

							else
								cout << " (" << i + 1 << "," << j + 1 << ")";

						break;	//important!!!!!!

						}

				}
		}
	}

	if (is_first)
		cout << "No legal move." << endl;

	else
		cout << endl;
}

bool PlayGame (int x, int y)
{
	bool is_legal = false;

	int i;
	for (i = 0; i < 8; i++)
		if (OkMove (x + dx[i], y + dy[i]))
		{
			if (Search (x, y, i))
			{
				is_legal = true;
				PaintPoint (x, y, i);
			}
		}

return is_legal;
}


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

	int cases;
	cin >> cases;
	char cmd[12];

	while (cases--)
	{
		int i;
		sum_b = 0, sum_w = 0;

		for (i = 0; i < 8; i++)
		{
			int j;
			for (j = 0; j < 8; j++)
			{
				cin >> game[i][j];

				if (game[i][j] == 'W')
					sum_w++;

				else if (game[i][j] == 'B')
				sum_b++;
			}
		}

		cin >> cur_player;
		while (cin >> cmd)
		{
			if (cmd[0] == 'Q')
			{
				OutPut ();
				break;
			}

			else if (cmd[0] == 'L')
			{
				ShowLegalPosition ();
			}

			else if (cmd[0] == 'M')
			{
				int weizhi_x = (cmd[1] - '0') - 1;
				int weizhi_y = (cmd[2] - '0') - 1;
				if (game[weizhi_x][weizhi_y] == '-' && PlayGame (weizhi_x, weizhi_y))
				{
					Change (cur_player);
				}

				else
				{
					Change (cur_player);
					PlayGame (weizhi_x, weizhi_y);
					Change (cur_player);
				}

				CalcNumber ();
				cout << "Black -" << setw (3) << sum_b << " ";
				cout << "White -" << setw (3) << sum_w << endl;
			}
		}

		if (cases)
			cout << 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

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

#include <iostream>

#include <fstream>

#include <iomanip>

using namespace std;

const int dx[] = {-1, -1, -1, 1, 1, 1, 0, 0};

const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 1};

const int maxn = 12;

char game[maxn][maxn];

int sum_b, sum_w;

char cur_player;

void CalcNumber ()

{

sum_b = 0, sum_w = 0;

int i, j;

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

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

{

if (game[i][j] == 'W')

sum_w++;

else if (game[i][j] == 'B')

sum_b++;

}

void OutPut ()

{

int i;

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

cout << game[i] << endl;

}

inline char Opposite (char val)

{

if (val == 'B')

return 'W';

return 'B';

}

void Change (char &val)

{

if (val == 'B')

val = 'W';

else

val = 'B';

}

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= 7 && y >= 0 && y <= 7 && game[x][y] == Opposite (cur_player))

return true;

return false;

}

void PaintPoint (int x, int y, int loc)

{

game[x][y] = cur_player;

while (OkMove (x + dx[loc], y + dy[loc]))

{

x += dx[loc];

y += dy[loc];

game[x][y] = cur_player;

}

bool Search (int x, int y, int loc)

{

while (OkMove (x + dx[loc], y + dy[loc]))

{

x += dx[loc];

y += dy[loc];

}

int temp_x = x + dx[loc];

int temp_y = y + dy[loc];

if (temp_x >= 0 && temp_x <= 7 && temp_y >= 0 && temp_y <= 7

&& game[temp_x][temp_y] == cur_player)

return true;

return false;

}

void ShowLegalPosition ()

{

bool is_first = true;

int i;

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

{

int j;

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

{

int k;

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

if (game[i][j] == '-' && OkMove (i + dx[k], j + dy[k]))

{ //game[i][j] == '-' is important!!!

if (Search (i, j, k))

{

if (is_first)

{

is_first = false;

cout << "(" << i + 1 << "," << j + 1 << ")";

}

else

cout << " (" << i + 1 << "," << j + 1 << ")";

break; //important!!!!!!

}

if (is_first)

cout << "No legal move." << endl;

else

cout << endl;

}

bool PlayGame (int x, int y)

{

bool is_legal = false;

int i;

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

if (OkMove (x + dx[i], y + dy[i]))

{

if (Search (x, y, i))

{

is_legal = true;

PaintPoint (x, y, i);

}

return is_legal;

}

int main()

{

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

int cases;

cin >> cases;

char cmd[12];

while (cases--)

{

int i;

sum_b = 0, sum_w = 0;

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

{

int j;

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

{

cin >> game[i][j];

if (game[i][j] == 'W')

sum_w++;

else if (game[i][j] == 'B')

sum_b++;

}

cin >> cur_player;

while (cin >> cmd)

{

if (cmd[0] == 'Q')

{

OutPut ();

break;

}

else if (cmd[0] == 'L')

{

ShowLegalPosition ();

}

else if (cmd[0] == 'M')

{

int weizhi_x = (cmd[1] - '0') - 1;

int weizhi_y = (cmd[2] - '0') - 1;

if (game[weizhi_x][weizhi_y] == '-' && PlayGame (weizhi_x, weizhi_y))

{

Change (cur_player);

}

else

{

Change (cur_player);

PlayGame (weizhi_x, weizhi_y);

Change (cur_player);

}

CalcNumber ();

cout << "Black -" << setw (3) << sum_b << " ";

cout << "White -" << setw (3) << sum_w << endl;

}

if (cases)

cout << endl;

}

return 0;

}

uva201

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

08 12月 2017

A children’s board game consists of a square array of dots that contains lines connecting some of the pairs of adjacent dots. One part of the game requires that the players count the number of squares of certain sizes that are formed by these lines. For example, in the figure shown below, there are 3 squares — 2 of size 1 and 1 of size 2. (The “size” of a square is the number of lines segments required to form a side.)

Your problem is to write a program that automates the process of counting all the possible squares.

Input

The input file represents a series of game boards. Each board consists of a description of a square array of n 2 dots (where 2 ≤ n ≤ 9) and some interconnecting horizontal and vertical lines. A record for a single board with n 2 dots and m interconnecting lines is formatted as follows:

Line 1: n the number of dots in a single row or column of the array

Line 2: m the number of interconnecting lines

Each of the next m lines are of one of two types:

H i j indicates a horizontal line in row i which connects the dot in column j to the one to its right in column j + 1

V i j indicates a vertical line in column i which connects the dot in row j to the one below in row j + 1

Information for each line begins in column 1. The end of input is indicated by end-of-file. The first record of the sample input below represents the board of the square above.

Output

For each record, label the corresponding output with ‘Problem #1’, ‘Problem #2’, and so forth. Output for a record consists of the number of squares of each size on the board, from the smallest to the largest. lf no squares of any size exist, your program should print an appropriate message indicating so. Separate output for successive input records by a line of asterisks between two blank lines, like in the sample below.

Sample Input

4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
Sample Output

Problem #1

2 square (s) of size 1

1 square (s) of size 2

**********************************

Problem #2

No completed squares can be found.

题目类型：简单模拟

算法分析：构造一个链接点与点之间关系的图，然后从小到大枚举每一个可能的子正方形的边长，按照从上至下，从左至右的顺序以每一个元素的位置为起始位置来”构造”相应边长的子正方形。注意最后一个测试用例的最后没有多余的空行。输出多余的空行在UVA上会WA，下面第一个代码是更好的实现

/**************************************************
filename       :l.cpp
author         :maksyuki
created time   :2017/12/8 20:01:15
last modified  :2017/12/8 20:28:59
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;

bool g[12][12][12][12];

int main()
{
#ifdef LOCAL
    CFF;
    CFO;
#endif
    
    int n, m, id = 1;
    while(scanf("%d", &n) != EOF) {
        scanf(" %d", &m);
        
        memset(g, false, sizeof(g));
        char ch;
        int ix, iy;
        for(int i = 1; i <= m; i++) {
            scanf(" %c %d %d", &ch, &ix, &iy);
            if(ch == 'H') g[ix][iy][ix][iy+1] = true;
            else g[iy][ix][iy+1][ix] = true;
        }
        
        int ans[16];
        memset(ans, 0, sizeof(ans));
        for(int len = 1; len <= n - 1; len++)
            for(int i = 1; i <= n - len; i++)
                for(int j = 1; j <= n - len; j++) {
                    bool is_valid = true;
                    for(int q = j; q <= j + len - 1; q++)
                        if(!g[i][q][i][q+1] || !g[i+len][q][i+len][q+1]) {
                            is_valid = false;
                            break;
                        }
                    
                    for(int q = i; q <= i + len - 1; q++)
                        if(!g[q][j][q+1][j] || !g[q][j+len][q+1][j+len]) {
                            is_valid = false;
                            break;
                        }
                    if(is_valid) ans[len]++;
                }

        if(id > 1) printf("\n**********************************\n\n");
        
        printf("Problem #%d\n\n", id++);

        bool is_have = false;
        for(int i = 1; i <= n - 1; i++)
            if(ans[i]) {
                is_have = true;
                break;
            }

        if(!is_have) puts("No completed squares can be found.");
        else {
            for(int i = 1; i <= n - 1; i++)
                if(ans[i]) printf("%d square (s) of size %d\n", ans[i], i);
        }

    }
    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

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

filename :l.cpp

author :maksyuki

created time :2017/12/8 20:01:15

last modified :2017/12/8 20:28:59

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;

bool g[12][12][12][12];

int main()

{

#ifdef LOCAL

CFF;

CFO;

#endif

int n, m, id = 1;

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

scanf(" %d", &m);

memset(g, false, sizeof(g));

char ch;

int ix, iy;

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

scanf(" %c %d %d", &ch, &ix, &iy);

if(ch == 'H') g[ix][iy][ix][iy+1] = true;

else g[iy][ix][iy+1][ix] = true;

}

int ans[16];

memset(ans, 0, sizeof(ans));

for(int len = 1; len <= n - 1; len++)

for(int i = 1; i <= n - len; i++)

for(int j = 1; j <= n - len; j++) {

bool is_valid = true;

for(int q = j; q <= j + len - 1; q++)

if(!g[i][q][i][q+1] || !g[i+len][q][i+len][q+1]) {

is_valid = false;

break;

}

for(int q = i; q <= i + len - 1; q++)

if(!g[q][j][q+1][j] || !g[q][j+len][q+1][j+len]) {

is_valid = false;

break;

}

if(is_valid) ans[len]++;

}

if(id > 1) printf("\n**********************************\n\n");

printf("Problem #%d\n\n", id++);

bool is_have = false;

for(int i = 1; i <= n - 1; i++)

if(ans[i]) {

is_have = true;

break;

}

if(!is_have) puts("No completed squares can be found.");

else {

for(int i = 1; i <= n - 1; i++)

if(ans[i]) printf("%d square (s) of size %d\n", ans[i], i);

}

return 0;

}

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

const int maxn = 16;

int cnt[16];
int side, flag = 1;

struct point
{
	bool edge[4];				//edge[0] means "up edge" 1, 2, 3 mean left, down, right edge"
};

point ans[maxn][maxn];

bool OkMove (int x, int y)
{
	if (x >= 0 && x <= side - 1 && y >= 0 && y <= side - 1)
		return true;

return false;
}


bool Search (int x, int y, int len)
{
	int i;
	bool can = true;

	for (i = 1; i <= len; i++)
	{
		if (OkMove (x, y + 1) && ans[x][y].edge[1])
			y++;

		else
			can = false;
	}	

	for (i = 1; i <= len; i++)
	{
		if (OkMove (x + 1, y) && ans[x][y].edge[2])
			x++;

		else
			can = false;
	}

	for (i = 1; i <= len; i++)
	{
		if (OkMove (x, y - 1) && ans[x][y].edge[3])
			y--;

		else
			can = false;
	}

	for (i = 1; i <= len; i++)
	{
		if (OkMove (x - 1, y) && ans[x][y].edge[0])
			x--;

		else
			can = false;
	}
			
return can;
}


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

	bool is_illegal;
	char oper;
	int weizhi_x, weizhi_y;

	while (cin >> side)
	{
		int side_num;

		cin >> side_num;

		memset (cnt, 0, sizeof (cnt));
		is_illegal = true;
		int i;	
		
		for (i = 0; i < maxn; i++)
		{
			int j;
			for (j = 0; j < maxn; j++)
				memset (ans[i][j].edge, false, sizeof (ans[i][j].edge));
		}


		for (i = 0; i < side_num; i++)
		{
			cin >> oper >> weizhi_x >> weizhi_y;

			if (oper == 'H')
			{
				ans[weizhi_x-1][weizhi_y-1].edge[1] = true;
				ans[weizhi_x-1][weizhi_y].edge[3] = true;
			}

			else if (oper == 'V')
			{
				ans[weizhi_y-1][weizhi_x-1].edge[2] = true;
				ans[weizhi_y][weizhi_x-1].edge[0] = true;
			}
		}
		

		for (i = 1; i <= side - 1; i++)
		{
			int j, k;
			for (j = 0; j < side; j++)
				for (k = 0; k < side; k++)
					if (Search (j, k, i))
					{
						cnt[i]++;
						is_illegal = false;
					}
		}

		if (flag - 1)
			cout << endl << "**********************************" << endl << endl;

		cout << "Problem #" << flag++ << endl << endl;

		if (is_illegal)
			cout << "No completed squares can be found." << endl;

		else
		{
			for (i = 1; i <= side - 1; i++)
				if (cnt[i])
					cout << cnt[i] << " square (s) of size " << i << 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

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 16;

int cnt[16];

int side, flag = 1;

struct point

{

bool edge[4]; //edge[0] means "up edge" 1, 2, 3 mean left, down, right edge"

};

point ans[maxn][maxn];

bool OkMove (int x, int y)

{

if (x >= 0 && x <= side - 1 && y >= 0 && y <= side - 1)

return true;

return false;

}

bool Search (int x, int y, int len)

{

int i;

bool can = true;

for (i = 1; i <= len; i++)

{

if (OkMove (x, y + 1) && ans[x][y].edge[1])

y++;

else

can = false;

}

for (i = 1; i <= len; i++)

{

if (OkMove (x + 1, y) && ans[x][y].edge[2])

x++;

else

can = false;

}

for (i = 1; i <= len; i++)

{

if (OkMove (x, y - 1) && ans[x][y].edge[3])

y--;

else

can = false;

}

for (i = 1; i <= len; i++)

{

if (OkMove (x - 1, y) && ans[x][y].edge[0])

x--;

else

can = false;

}

return can;

}

int main()

{

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

bool is_illegal;

char oper;

int weizhi_x, weizhi_y;

while (cin >> side)

{

int side_num;

cin >> side_num;

memset (cnt, 0, sizeof (cnt));

is_illegal = true;

int i;

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

{

int j;

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

memset (ans[i][j].edge, false, sizeof (ans[i][j].edge));

}

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

{

cin >> oper >> weizhi_x >> weizhi_y;

if (oper == 'H')

{

ans[weizhi_x-1][weizhi_y-1].edge[1] = true;

ans[weizhi_x-1][weizhi_y].edge[3] = true;

}

else if (oper == 'V')

{

ans[weizhi_y-1][weizhi_x-1].edge[2] = true;

ans[weizhi_y][weizhi_x-1].edge[0] = true;

}

for (i = 1; i <= side - 1; i++)

{

int j, k;

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

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

if (Search (j, k, i))

{

cnt[i]++;

is_illegal = false;

}

if (flag - 1)

cout << endl << "**********************************" << endl << endl;

cout << "Problem #" << flag++ << endl << endl;

if (is_illegal)

cout << "No completed squares can be found." << endl;

else

{

for (i = 1; i <= side - 1; i++)

if (cnt[i])

cout << cnt[i] << " square (s) of size " << i << endl;

}

return 0;

}

uva1589

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

07 12月 2017

Xiangqi is one of the most popular two-player board games in China. The game represents a battle between two armies with the goal of capturing the enemy’s “general” piece. In this problem, you are given a situation of later stage in the game. Besides, the red side has already “delivered a check”. Your work is to check whether the situation is “checkmate”.

Now we introduce some basic rules of Xiangqi. Xiangqi is played on a 10 × 9 board and the pieces are placed on the intersections (points). The top left point is (1,1) and the bottom right point is (10,9). There are two groups of pieces marked by black or red Chinese characters, belonging to the two players separately. During the game, each player in turn moves one piece from the point it occupies to another point. No two pieces can occupy the same point at the same time. A piece can be moved onto a point occupied by an enemy piece, in which case the enemy piece is“captured” and removed from the board. When the general is in danger of being captured by the enemy player on the enemy player’s next move, the enemy player is said to have “delivered a check”. If the general’s player can make no move to prevent the general’s capture by next enemy move, the situation is called “checkmate”.

We only use 4 kinds of pieces introducing as follows:

General: the generals can move and capture one point either vertically or horizontally and cannot leave the “palace” unless the situation called “flying general” (see the figure above). “Flying general” means that one general can “fly” across the board to capture the enemy general if they stand on the same line without intervening pieces.

Chariot: the chariots can move and capture vertically and horizontally by any distance, but may not jump over intervening pieces

Cannon: the cannons move like the chariots, horizontally and vertically, but capture by jumping exactly one piece (whether it is friendly or enemy) over to its target.

Horse: the horses have 8 kinds of jumps to move and capture shown in the left figure. However, if there is any pieces lying on a point away from the horse horizontally or vertically it cannot move or capture in that direction (see the figure below), which is called “hobbling the horse’s leg”.

Now you are given a situation only containing a black general, a red general and several red chariots, cannons and horses, and the red side has delivered a check. Now it turns to black side’s move. Your job is to determine that whether this situation is “checkmate”.

Input

The input contains no more than 40 test cases. For each test case, the first line contains three integers representing the number of red pieces N (2 ≤ N ≤ 7) and the position of the black general. The following N lines contain details of N red pieces. For each line, there are a char and two integers representing the type and position of the piece (type char ‘G’ for general, ‘R’ for chariot, ‘H’ for horse and ‘C’ for cannon). We guarantee that the situation is legal and the red side has delivered the check.

There is a blank line between two test cases. The input ends by ‘0 0 0’.

Output

For each test case, if the situation is checkmate, output a single word ‘YES’, otherwise output the word ‘NO’.

Hint: In the first situation, the black general is checked by chariot and “flying general”. In the second situation, the black general can move to (1, 4) or (1, 6) to stop check. See the figure on the right.

Sample Input

2 1 4
G 10 5
R 6 4
3 1 5
H 4 5
G 10 5
C 7 5
0 0 0

Sample Output

YES

题目类型：简单模拟

算法分析：对于每个黑色general可以移动到的位置，查找是否有红色棋子可以攻击到。对于车，炮，马和国王来说，从待查找位置开始向四周查找比较好写

/**************************************************
filename       :k.cpp
author         :maksyuki
created time   :2017/12/7 22:57:55
last modified  :2017/12/7 23:15:31
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 v[12][12];
int dx1[4] = {1, -1, 0, 0};
int dy1[4] = {0, 0, 1, -1};
int dx2[8] = {-2, -1, -2, -1, 1, 2, 1, 2};
int dy2[8] = {-1, -2, 1, 2, -2, -1, 2, 1};
int dx3[8] = {-1, -1, -1, -1, 1, 1, 1, 1};
int dy3[8] = {-1, -1, 1, 1, -1, -1, 1, 1};

int n, bx, by;

bool check(int xx, int yy) {
    if(xx <= 0 || xx >= 4 || yy <= 3 || yy >= 7) return 1;

    for(int i = 0; i < 4; i++) {
        int tmpx = xx + dx1[i], tmpy = yy + dy1[i];
        int cnt = 0;
        for(; tmpx >= 1 && tmpx <= 10 && tmpy >= 1 && tmpy <= 9; tmpx += dx1[i], tmpy += dy1[i]) {
            if(v[tmpx][tmpy]) {
                if((v[tmpx][tmpy] == 'R' || v[tmpx][tmpy] == 'G') && !cnt) return 1;
                if(v[tmpx][tmpy] == 'C' && cnt == 1) return 1;
                cnt++;
            }
        }
    }

    for(int i = 0; i < 8; i++) {
        int tmpx = xx + dx2[i], tmpy = yy + dy2[i];
        if(tmpx >= 1 && tmpy <= 10 && tmpy >= 1 && tmpy <= 9) {
            int bbx = xx + dx3[i], bby = yy + dy3[i];
            if(v[tmpx][tmpy] == 'H' && !v[bbx][bby]) return 1;
        }
    }
    return 0;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf("%d %d %d", &n, &bx, &by) != EOF) {
        if(!n && !bx && !by) break;

        char c;
        int xx, yy;
        memset(v, 0, sizeof(v));
        for(int i = 1; i <= n; i++) {
            scanf(" %c %d %d", &c, &xx, &yy);
            v[xx][yy] = c;
        }


        int ans = 0;
        for(int i = 0; i < 4; i++) {
            int tmpx = bx + dx1[i], tmpy = by + dy1[i];
            ans += check(tmpx, tmpy);
        }

        if(ans >= 4) puts("YES");
        else puts("NO");
    }
    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

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

filename :k.cpp

author :maksyuki

created time :2017/12/7 22:57:55

last modified :2017/12/7 23:15:31

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 v[12][12];

int dx1[4] = {1, -1, 0, 0};

int dy1[4] = {0, 0, 1, -1};

int dx2[8] = {-2, -1, -2, -1, 1, 2, 1, 2};

int dy2[8] = {-1, -2, 1, 2, -2, -1, 2, 1};

int dx3[8] = {-1, -1, -1, -1, 1, 1, 1, 1};

int dy3[8] = {-1, -1, 1, 1, -1, -1, 1, 1};

int n, bx, by;

bool check(int xx, int yy) {

if(xx <= 0 || xx >= 4 || yy <= 3 || yy >= 7) return 1;

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

int tmpx = xx + dx1[i], tmpy = yy + dy1[i];

int cnt = 0;

for(; tmpx >= 1 && tmpx <= 10 && tmpy >= 1 && tmpy <= 9; tmpx += dx1[i], tmpy += dy1[i]) {

if(v[tmpx][tmpy]) {

if((v[tmpx][tmpy] == 'R' || v[tmpx][tmpy] == 'G') && !cnt) return 1;

if(v[tmpx][tmpy] == 'C' && cnt == 1) return 1;

cnt++;

}

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

int tmpx = xx + dx2[i], tmpy = yy + dy2[i];

if(tmpx >= 1 && tmpy <= 10 && tmpy >= 1 && tmpy <= 9) {

int bbx = xx + dx3[i], bby = yy + dy3[i];

if(v[tmpx][tmpy] == 'H' && !v[bbx][bby]) return 1;

}

return 0;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(scanf("%d %d %d", &n, &bx, &by) != EOF) {

if(!n && !bx && !by) break;

char c;

int xx, yy;

memset(v, 0, sizeof(v));

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

scanf(" %c %d %d", &c, &xx, &yy);

v[xx][yy] = c;

}

int ans = 0;

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

int tmpx = bx + dx1[i], tmpy = by + dy1[i];

ans += check(tmpx, tmpy);

}

if(ans >= 4) puts("YES");

else puts("NO");

}

return 0;

}

uva512

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

05 12月 2017

Data in spreadsheets are stored in cells, which are organized in rows (r) and columns (c). Some operations on spreadsheets can be applied to single cells (r, c), while others can be applied to entire rows or columns. Typical cell operations include inserting and deleting rows or columns and exchanging cell contents.

Some spreadsheets allow users to mark collections of rows or columns for deletion, so the entire collection can be deleted at once. Some (unusual) spreadsheets allow users to mark collections of rows or columns for insertions too. Issuing an insertion command results in new rows or columns being inserted before each of the marked rows or columns. Suppose, for example, the user marks rows 1 and 5 of the spreadsheet on the left for deletion. The spreadsheet then shrinks to the one on the right.

You must write tracking software that determines the final location of data in spreadsheets that result from row, column, and exchange operations similar to the ones illustrated here.

Input

The input consists of a sequence of spreadsheets, operations on those spreadsheets, and queries about them. Each spreadsheet definition begins with a pair of integers specifying its initial number of rows (r) and columns (c), followed by an integer specifying the number (n) of spreadsheet operations. Row and column labeling begins with 1. The maximum number of rows or columns of each spreadsheet is limited to 50. The following n lines specify the desired operations.

An operation to exchange the contents of cell (r1, c1) with the contents of cell (r2, c2) is given by:

EX r1 c1 r2 c2

The four insert and delete commands—DC (delete columns), DR (delete rows), IC (insert columns), and IR (insert rows) are given by:

< command > A x1 x2 . . . xA

where < command > is one of the four commands; A is a positive integer less than 10, and x1, . . . , xA are the labels of the columns or rows to be deleted or inserted before. For each insert and delete command, the order of the rows or columns in the command has no significance. Within a single delete or insert command, labels will be unique.

The operations are followed by an integer which is the number of queries for the spreadsheet. Each query consists of positive integers r and c, representing the row and column number of a cell in the original spreadsheet. For each query, your program must determine the current location of the data that was originally in cell (r, c). The end of input is indicated by a row consisting of a pair of zeros for the spreadsheet dimensions.

Output

For each spreadsheet, your program must output its sequence number (starting at 1). For each query, your program must output the original cell location followed by the final location of the data or the word ‘GONE’ if the contents of the original cell location were destroyed as a result of the operations. Separate output from different spreadsheets with a blank line.

The data file will not contain a sequence of commands that will cause the spreadsheet to exceed the maximum size.

Sample Input

7 9
5
DR 2 1 5
DC 4 3 6 7 9
IC 1 3
IR 2 2 4
EX 1 2 6 5
4
4 8
5 5
7 8
6 5
0 0

Sample Output

Spreadsheet #1

Cell data in (4,8) moved to (4,6)

Cell data in (5,5) GONE

Cell data in (7,8) moved to (7,6)

Cell data in (6,5) moved to (1,2)

题目类型：简单模拟

算法分析：先保存下所有的操作，然后对于每次查询的位置执行所有操作，当删除操作会删除当前查询单元所在的行或列时，操作非法。注意样例之间需要间隔一个空行

/**************************************************
filename       :g.cpp
author         :maksyuki
created time   :2017/12/5 11:03:02
last modified  :2017/12/5 22:39:32
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 cmd[maxn][6];
int v[maxn][12], row, col, na, nb;
int ans[6];

int calca(int vv, int p) {
    int cnt = 0;
    for(int i = 1; i <= v[vv][0]; i++) {
        if(ans[p] == v[vv][i]) return -1;
        if(ans[p] > v[vv][i]) cnt++;
    }
    return cnt;
}

int calcb(int vv, int p) {
    int cnt = 0;
    for(int i = 1; i <= v[vv][0]; i++)
        if(ans[p] >= v[vv][i]) cnt++;
    return cnt;
}

bool findv(int pa, int pb) {
    ans[1] = pa, ans[2] = pb;
    for(int i = 1; i <= na; i++) {
        //printf("(%d,%d)\n", ansa, ansb);
        if(cmd[i][0] == 'E') {
            if(ans[1] == v[i][1] && ans[2] == v[i][2])
                ans[1] = v[i][3], ans[2] = v[i][4];
            else if(ans[1] == v[i][3] && ans[2] == v[i][4])
                ans[1] = v[i][1], ans[2] = v[i][2];
        }
        else {
            if(cmd[i][0] == 'D') {
                if(cmd[i][1] == 'R') {
                    int tmp = calca(i, 1);
                    if(tmp == -1) return false;
                    ans[1] -= tmp;
                }
                else {
                    int tmp = calca(i, 2);
                    if(tmp == -1) return false;
                    ans[2] -= tmp;
                }
            }
            if(cmd[i][0] == 'I') {
                if(cmd[i][1] == 'R') ans[1] += calcb(i, 1);
                else ans[2] += calcb(i, 2);
            }
        }
    }
    return true;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int id = 1;
    while(scanf(" %d %d", &row, &col) != EOF) {
        if(!row && !col) break;

        scanf(" %d", &na);
        for(int i = 1; i <= na; i++) {
            scanf(" %s", cmd[i]);
                
            if(cmd[i][0] == 'E')
                for(int j = 1; j <= 4; j++) scanf(" %d", &v[i][j]);
            
            else {
                int tmp;
                scanf(" %d", &tmp);
                v[i][0] = tmp;
                for(int j = 1; j <= tmp; j++) scanf(" %d", &v[i][j]);
            }
        }
        
        if(id > 1) puts("");
        printf("Spreadsheet #%d\n", id++);
        scanf(" %d", &nb);
        int rr, cc;
        for(int i = 1; i <= nb; i++) {
            scanf(" %d %d", &rr, &cc);
            printf("Cell data in (%d,%d)", rr, cc);
            if(findv(rr, cc)) printf(" moved to (%d,%d)\n", ans[1], ans[2]);
            else puts(" GONE");

        }
    }
    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 :g.cpp

author :maksyuki

created time :2017/12/5 11:03:02

last modified :2017/12/5 22:39:32

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 cmd[maxn][6];

int v[maxn][12], row, col, na, nb;

int ans[6];

int calca(int vv, int p) {

int cnt = 0;

for(int i = 1; i <= v[vv][0]; i++) {

if(ans[p] == v[vv][i]) return -1;

if(ans[p] > v[vv][i]) cnt++;

}

return cnt;

}

int calcb(int vv, int p) {

int cnt = 0;

for(int i = 1; i <= v[vv][0]; i++)

if(ans[p] >= v[vv][i]) cnt++;

return cnt;

}

bool findv(int pa, int pb) {

ans[1] = pa, ans[2] = pb;

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

//printf("(%d,%d)\n", ansa, ansb);

if(cmd[i][0] == 'E') {

if(ans[1] == v[i][1] && ans[2] == v[i][2])

ans[1] = v[i][3], ans[2] = v[i][4];

else if(ans[1] == v[i][3] && ans[2] == v[i][4])

ans[1] = v[i][1], ans[2] = v[i][2];

}

else {

if(cmd[i][0] == 'D') {

if(cmd[i][1] == 'R') {

int tmp = calca(i, 1);

if(tmp == -1) return false;

ans[1] -= tmp;

}

else {

int tmp = calca(i, 2);

if(tmp == -1) return false;

ans[2] -= tmp;

}

if(cmd[i][0] == 'I') {

if(cmd[i][1] == 'R') ans[1] += calcb(i, 1);

else ans[2] += calcb(i, 2);

}

return true;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int id = 1;

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

if(!row && !col) break;

scanf(" %d", &na);

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

scanf(" %s", cmd[i]);

if(cmd[i][0] == 'E')

for(int j = 1; j <= 4; j++) scanf(" %d", &v[i][j]);

else {

int tmp;

scanf(" %d", &tmp);

v[i][0] = tmp;

for(int j = 1; j <= tmp; j++) scanf(" %d", &v[i][j]);

}

if(id > 1) puts("");

printf("Spreadsheet #%d\n", id++);

scanf(" %d", &nb);

int rr, cc;

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

scanf(" %d %d", &rr, &cc);

printf("Cell data in (%d,%d)", rr, cc);

if(findv(rr, cc)) printf(" moved to (%d,%d)\n", ans[1], ans[2]);

else puts(" GONE");

}

return 0;

}

uva133

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

05 12月 2017

In a serious attempt to downsize (reduce) the dole queue, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is arbitrarily chosen as number 1, and the rest are numbered counter-clockwise up to N (who will be standing on 1's left). Starting from 1 and moving counter-clockwise, one labour official counts off k applicants, while another official starts from N and moves clockwise, counting m applicants. The two who are chosen are then sent off for retraining; if both officials pick the same person she (he) is sent off to become a politician. Each official then starts counting again at the next available person and the process continues until no-one is left. Note that the two victims (sorry, trainees) leave the ring simultaneously, so it is possible for one official to count a person already selected by the other official.

Input

Write a program that will successively read in (in that order) the three numbers (N, k and m; k, m > 0, 0 < N < 20) and determine the order in which the applicants are sent off for retraining. Each set of three numbers will be on a separate line and the end of data will be signalled by three zeroes (0 0 0).

Output

For each triplet, output a single line of numbers specifying the order in which people are chosen. Each number should be in a field of 3 characters. For pairs of numbers list the person chosen by the counter-clockwise official first. Separate successive pairs (or singletons) by commas (but there should not be a trailing comma).

Sample input

10 4 3

0 0 0

Sample output

4 8, 9 5, 3 1, 2 6, 10, 7

where represents a space.

题目类型：简单模拟

算法分析：本题类似于约瑟夫问题，按照题目的要求直接进行模拟即可。本题对于顺时针和逆时针运动可以统一用一个函数go来解决，本函数具有较强的技巧性，下面第二个代码是更好的实现

/**************************************************
filename       :d.cpp
author         :maksyuki
created time   :2017/12/5 8:42:29
last modified  :2017/12/5 9:21:22
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 = 66;

int N, k, m, v[maxn];

int findv(int p, int cnt) {
    while(1) {
        if(cnt == 1) {
            if(p == N) p = 1;
            else p++;
        }
        else {
            if(p == 1) p = N;
            else p--;
        }
        if(v[p] != -1) return p;
    }
    return -6;
}

int go(int p, int vv, int cnt) {
    int ans = p;
    for(int i = 1; i < vv; i++)
        ans = findv(ans, cnt);
    return ans;
}

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

    while(scanf(" %d %d %d", &N, &k, &m) != EOF) {
        if(!N && !k && !m) break;
    
        int tmp = N;
        int pa = 1, pb = N, va, vb;
        for(int i = 0; i < maxn; i++) v[i] = i;
        
        bool is_first = true;

        while(tmp) {
            va = go(pa, k, 1); 
            vb = go(pb, m, -1);
            if(is_first) is_first = false;
            else printf(",");
            if(va == vb) {
                v[va] = -1;
                printf("%3d", va);
                tmp--;
            }
            else {
                v[va] = -1, v[vb] = -1;
                printf("%3d%3d", va, vb);
                tmp -= 2;
            }

            if(!tmp) break;

            pa = go(findv(va, 1), 1, 1);
            pb = go(findv(vb, -1), 1, -1);
        }
        puts("");
    }
    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

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

filename :d.cpp

author :maksyuki

created time :2017/12/5 8:42:29

last modified :2017/12/5 9:21:22

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 = 66;

int N, k, m, v[maxn];

int findv(int p, int cnt) {

while(1) {

if(cnt == 1) {

if(p == N) p = 1;

else p++;

}

else {

if(p == 1) p = N;

else p--;

}

if(v[p] != -1) return p;

}

return -6;

}

int go(int p, int vv, int cnt) {

int ans = p;

for(int i = 1; i < vv; i++)

ans = findv(ans, cnt);

return ans;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

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

if(!N && !k && !m) break;

int tmp = N;

int pa = 1, pb = N, va, vb;

for(int i = 0; i < maxn; i++) v[i] = i;

bool is_first = true;

while(tmp) {

va = go(pa, k, 1);

vb = go(pb, m, -1);

if(is_first) is_first = false;

else printf(",");

if(va == vb) {

v[va] = -1;

printf("%3d", va);

tmp--;

}

else {

v[va] = -1, v[vb] = -1;

printf("%3d%3d", va, vb);

tmp -= 2;

}

if(!tmp) break;

pa = go(findv(va, 1), 1, 1);

pb = go(findv(vb, -1), 1, -1);

}

puts("");

}

return 0;

}

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

const int maxn = 66;

int a[maxn], n;
//bool is_first = true;

int go (int start, int step, int flag)
{
   /* if (is_first)
		step--, is_first = false; */

	while (step--)
	{
		do
		{
			start = (start + flag + n - 1) % n + 1;
		} while (!a[start]);
	}

	return start;
}
int main()
{
    int k, m;
    //ifstream cin ("aaa.txt");

    while (cin >> n >> k >> m && n && k && m)
	{
        int i;
        for (i = 1; i <= n; i++)
            a[i] = i;

        int Aweizhi = 1, Bweizhi = n, leave = n;

        while (leave)
		{
            Aweizhi = go (Aweizhi, m, -1);
            Bweizhi = go (Bweizhi, k, 1);

            printf ("%3d", Bweizhi);
            leave--;

            if (Aweizhi != Bweizhi)
			{
				printf ("%3d", Aweizhi);
				leave--;

			}

			a[Aweizhi] = a[Bweizhi] = 0;

			if (leave)
				printf (",");
		}

		printf ("\n");
	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

const int maxn = 66;

int a[maxn], n;

//bool is_first = true;

int go (int start, int step, int flag)

{

/* if (is_first)

step--, is_first = false; */

while (step--)

{

start = (start + flag + n - 1) % n + 1;

} while (!a[start]);

}

return start;

}

int main()

{

int k, m;

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

while (cin >> n >> k >> m && n && k && m)

{

int i;

for (i = 1; i <= n; i++)

a[i] = i;

int Aweizhi = 1, Bweizhi = n, leave = n;

while (leave)

{

Aweizhi = go (Aweizhi, m, -1);

Bweizhi = go (Bweizhi, k, 1);

printf ("%3d", Bweizhi);

leave--;

if (Aweizhi != Bweizhi)

{

printf ("%3d", Aweizhi);

leave--;

}

a[Aweizhi] = a[Bweizhi] = 0;

if (leave)

printf (",");

}

printf ("\n");

}

return 0;

}

uva489

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

05 12月 2017

In Hangman Judge,'' you are to write a program that judges a series of Hangman games. For each game, the answer to the puzzle is given as well as the guesses. Rules are the same as the classic game of hangman, and are given as follows:

The contestant tries to solve to puzzle by guessing one letter at a time.
Every time a guess is correct, all the characters in the word that match the guess will be turned over.'' For example, if your guess is o'' and the word is book'', then both o''s in the solution will be counted as solved.''
Every time a wrong guess is made, a stroke will be added to the drawing of a hangman, which needs 7 strokes to complete. Each unique wrong guess only counts against the contestant once.
______
| |
| O
| /|\
| |
| / \
__|_
| |______

|_________|

If the drawing of the hangman is completed before the contestant has successfully guessed all the characters of the word, the contestant loses.
If the contestant has guessed all the characters of the word before the drawing is complete, the contestant wins the game.
If the contestant does not guess enough letters to either win or lose, the contestant chickens out.

Your task as the Hangman Judge'' is to determine, for each game, whether the contestant wins, loses, or fails to finish a game.

Input

Your program will be given a series of inputs regarding the status of a game. All input will be in lower case. The first line of each section will contain a number to indicate which round of the game is being played; the next line will be the solution to the puzzle; the last line is a sequence of the guesses made by the contestant. A round number of -1 would indicate the end of all games (and input).

Output

The output of your program is to indicate which round of the game the contestant is currently playing as well as the result of the game. There are three possible results:

You win.

You lose.

You chickened out.

Sample Input

cheese

chese

cheese

abcdefg

cheese

abcdefgij

-1

Sample Output

Round 1

You win.

Round 2

You chickened out.

Round 3

You lose.

题目类型：简单字符处理

算法分析：本题对于存贮玩家猜的字符串每一个字符，调用一次guess函数来判断在完成对于该字符处理之后是否进行退出。注意将玩家猜过的字符改成空格，下面第二个代码是更好的实现

/**************************************************
filename       :b.cpp
author         :maksyuki
created time   :2017/12/3 22:30:29
last modified  :2017/12/5 8:02:29
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 sa[maxn], sb[maxn];

void solve(char c) {
    for(int i = 0; sa[i]; i++)
        if(sa[i] == c) sa[i] = '*';
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int id;
    while(scanf(" %d", &id) != EOF) {
        if(id == -1) break;

        scanf(" %s %s", sa, sb);
        
        int cnt = 0;
        bool is_find;
        for(int i = 0; sb[i]; i++) {
            if(cnt > 6) break;
            is_find = false;
            for(int j = 0; sa[j]; j++) {
                if(sb[i] == sa[j]) {
                    solve(sb[i]);
                    is_find = true;
                }
            }
            if(!is_find) cnt++;
        }
        
        printf("Round %d\n", id);
       
        bool is_win = true;
        for(int i = 0; sa[i]; i++)
            if(sa[i] != '*') {
                is_win = false;
                break;
            }
       
        if(is_win) puts("You win.");
        else {
            if(cnt > 6) puts("You lose.");
            else puts("You chickened out.");
        }

    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

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

filename :b.cpp

author :maksyuki

created time :2017/12/3 22:30:29

last modified :2017/12/5 8:02:29

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 sa[maxn], sb[maxn];

void solve(char c) {

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

if(sa[i] == c) sa[i] = '*';

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int id;

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

if(id == -1) break;

scanf(" %s %s", sa, sb);

int cnt = 0;

bool is_find;

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

if(cnt > 6) break;

is_find = false;

for(int j = 0; sa[j]; j++) {

if(sb[i] == sa[j]) {

solve(sb[i]);

is_find = true;

}

if(!is_find) cnt++;

}

printf("Round %d\n", id);

bool is_win = true;

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

if(sa[i] != '*') {

is_win = false;

break;

}

if(is_win) puts("You win.");

else {

if(cnt > 6) puts("You lose.");

else puts("You chickened out.");

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int maxn = 106;

char com[maxn], ply[maxn];
bool win, lose;
int chance, comleave;

void guess (char ch)
{
	int bad = 1, len = strlen (com), i;
    for (i = 0; i < len; i++)
	{
		if (com[i] == ch)
		{
            comleave--;
            com[i] = ' ';
            bad = 0;
		}
	}

	if (bad)
		chance--;

	if (!chance)
		lose = true;

	if (!comleave)
		win = true;

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

    while (cin >> id >> com >> ply && id != -1)
	{
        win = lose = false;
        chance = 7;
        comleave = strlen (com);

	    int i, len = strlen (ply);
	    for (i = 0; i < len; i++)
		{
			guess (ply[i]);

			if (win || lose)
				break;
		}

	    printf ("Round %d\n", id);

	    if (win)
			printf ("You win.\n");

		else if (lose)
			printf ("You lose.\n");

		else
			printf ("You chickened out.\n");
	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 106;

char com[maxn], ply[maxn];

bool win, lose;

int chance, comleave;

void guess (char ch)

{

int bad = 1, len = strlen (com), i;

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

{

if (com[i] == ch)

{

comleave--;

com[i] = ' ';

bad = 0;

}

if (bad)

chance--;

if (!chance)

lose = true;

if (!comleave)

win = true;

}

int main()

{

int id;

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

while (cin >> id >> com >> ply && id != -1)

{

win = lose = false;

chance = 7;

comleave = strlen (com);

int i, len = strlen (ply);

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

{

guess (ply[i]);

if (win || lose)

break;

}

printf ("Round %d\n", id);

if (win)

printf ("You win.\n");

else if (lose)

printf ("You lose.\n");

else

printf ("You chickened out.\n");

}

return 0;

}

uva11809

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

03 12月 2017

Floating-point numbers are represented differently in computers than integers. That is why a 32-bit floating-point number can represent values in the magnitude of 1038 while a 32-bit integer can only represent values as high as 2^32.

Although there are variations in the ways floating-point numbers are stored in Computers, in this problem we will assume that floating-point numbers are stored in the following way:

Floating-point numbers have two parts mantissa and exponent. M-bits are allotted for mantissa and E bits are allotted for exponent. There is also one bit that denotes the sign of number (If this bit is 0 then the number is positive and if it is 1 then the number is negative) and another bit that denotes the sign of exponent (If this bit is 0 then exponent is positive otherwise negative). The value of mantissa and exponent together make the value of the floating-point number. If the value of mantissa is m then it maintains the constraints 1 2 ≤ m < 1. The left most digit of mantissa must always be 1 to maintain the constraint 1 2 ≤ m < 1. So this bit is not stored as it is always 1. So the bits in mantissa actually denote the digits at the right side of decimal point of a binary number (Excluding the digit just to the right of decimal point)

In the figure above we can see a floating-point number where M = 8 and E = 6. The largest value this floating-point number can represent is (in binary) 0.1111111112 ×2 1111112 . The decimal equivalent to this number is: 0.998046875 × 2 63 = 920535763834529382410. Given the maximum possible value represented by a certain floating point type, you will have to find how many bits are allotted for mantissa (M) and how many bits are allotted for exponent (E) in that certain type.

Input

The input file contains around 300 line of input. Each line contains a floating-point number F that denotes the maximum value that can be represented by a certain floating-point type. The floating point number is expressed in decimal exponent format. So a number AeB actually denotes the value A×10B. A line containing ‘0e0’ terminates input. The value of A will satisfy the constraint 0 < A < 10 and will have exactly 15 digits after the decimal point.

Output

For each line of input produce one line of output. This line contains the value of M and E. You can assume that each of the inputs (except the last one) has a possible and unique solution. You can also assume that inputs will be such that the value of M and E will follow the constraints: 9 ≥ M ≥ 0 and 30 ≥ E ≥ 1. Also there is no need to assume that (M + E + 2) will be a multiple of 8.

Sample Input

5.699141892149156e76

9.205357638345294e18

0e0

Sample Output

题目类型：简单数学

算法分析：由于尾数和阶数的组合数较小(只有300组)，所以考虑打表求解。使用m[i]=1-(1/2)^(i+1)表示位数为i时的尾数值，e[j]=2^j-1表示位数为j时的阶数值，v[i][j]=m[i]*2^e[j]表示尾数为m[i]，阶数为e[j]的浮点数值。由于v[i][j]比较大，一个技巧是对其取10为底的对数，最后每次读入输入后对其取对数在v[i][j]中查找(i, j)，注意由于存在对数运算(会丢失精度)，所以两数比较时的EPS要取的小一些

/**************************************************
filename       :s.cpp
author         :maksyuki
created time   :2017/12/3 17:52:29
last modified  :2017/12/3 18:19:58
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-5;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

double m[66], v[66][66], va;
int e[66], vb;
char s[66];

void pre() {
    double tmpa = 0.5;
    for(int i = 0; i <= 9; i++, tmpa /= 2.0)
        m[i] = 1.0 - tmpa;

    
    for(int i = 1, tmpb = 2; i <= 30; i++, tmpb *= 2)
        e[i] = tmpb - 1;

    for(int i = 0; i <= 9; i++)
        for(int j = 1; j <= 30; j++)
            v[i][j] = log10(m[i]) + e[j] * log10(2.0);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    pre();
    
    while(scanf(" %s", s) != EOF) {
        if(s[0] == '0' && s[2] == '0') break;

        for(int i = 0; s[i]; i++) 
            if(s[i] == 'e') {
                s[i] = ' ';
                break;
            }

        sscanf(s, " %lf %d", &va, &vb);
        double tmp = log10(va) + vb;
        
        //printf("%.15lf\n", tmp);
        //printf("%.15lf\n", v[0][26]);

        bool is_find = false;
        int m1 = -1, e1 = -1;
        for(int i = 0; i <= 9 && !is_find; i++)
            for(int j = 1; j <= 30 && !is_find; j++)
                if(fabs(tmp - v[i][j]) < EPS) {
                    is_find = true;
                    m1 = i, e1 = j;
                    break;
                }
        
        printf("%d %d\n", m1, e1);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

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

filename :s.cpp

author :maksyuki

created time :2017/12/3 17:52:29

last modified :2017/12/3 18:19:58

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

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

double m[66], v[66][66], va;

int e[66], vb;

char s[66];

void pre() {

double tmpa = 0.5;

for(int i = 0; i <= 9; i++, tmpa /= 2.0)

m[i] = 1.0 - tmpa;

for(int i = 1, tmpb = 2; i <= 30; i++, tmpb *= 2)

e[i] = tmpb - 1;

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

for(int j = 1; j <= 30; j++)

v[i][j] = log10(m[i]) + e[j] * log10(2.0);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

pre();

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

if(s[0] == '0' && s[2] == '0') break;

for(int i = 0; s[i]; i++)

if(s[i] == 'e') {

s[i] = ' ';

break;

}

sscanf(s, " %lf %d", &va, &vb);

double tmp = log10(va) + vb;

//printf("%.15lf\n", tmp);

//printf("%.15lf\n", v[0][26]);

bool is_find = false;

int m1 = -1, e1 = -1;

for(int i = 0; i <= 9 && !is_find; i++)

for(int j = 1; j <= 30 && !is_find; j++)

if(fabs(tmp - v[i][j]) < EPS) {

is_find = true;

m1 = i, e1 = j;

break;

}

printf("%d %d\n", m1, e1);

}

return 0;

}

1 2 下一页最后一页

超客的水墨烟雨

uva101

uva10474

uva509

uva1591

uva12108

uva815

uva508

uva1590

uva253

uva220

uva201

uva1589

uva512

uva133

uva489

uva11809

分类目录

标签云

书签

近期评论

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