题意 输出所有输入单词中可以由另两个单词的组成的词

STL set的应用 枚举每个单词的所有可能拆分情况 看拆开的两个单词是否都存在 都存在的就可以输出了

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

#include <bits/stdc++.h>
using namespace std;
string a, b;
set<string> s;
set<string>::iterator i;

int main()
{
    int l;
    while(cin >> a) s.insert(a);
    for(i = s.begin(); i != s.end(); ++i)
    {
        l = i->length();
        for(int j = 1; j < l - 1; ++j)
        {
            a = i->substr(0, j);
            b = i->substr(j);
            if(s.count(a) && s.count(b))
            {
                cout << (*i) << endl;
                break;
            }
        }
    }
    return 0;
}

Compound Words

You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.

Input

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.

Output

Your output should contain all the compound words, one per line, in alphabetical order.

Sample Input

a alien born less lien never nevertheless new newborn the zebra

Sample Output

alien newborn

题意 按要求对齐代码

字符串流的应用

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

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 200;
string s[N][M], line;
int cw[M], cn[N];

int main()
{
    int r = 0, c = 0;
    while(getline(cin, line))
    {
        stringstream ss(line);
        while(ss >> s[r][c])
        {
            if(s[r][c].length() > cw[c])
                cw[c] = s[r][c].length();
            ++c;
        }
        cn[r++] = c;
        c = 0;
    }

    for(int i = 0; i < r; ++i)
    {
        for(int j = 0; j < cn[i] - 1; ++j)
            cout << left << setw(cw[j] + 1) << s[i][j];
        cout << s[i][cn[i] - 1] << endl;
    }
    return 0;
}

You are working in a team that writes Incredibly Customizable Programming Codewriter (ICPC) which is basically a text editor with bells and whistles. You are working on a module that takes a piece of code containing some definitions or other tabular information and aligns each column on a fixed vertical position, while keeping the resulting code as short as possible, making sure that only whitespaces that are absolutely required stay in the code. So, that the first words on each line are printed at position p1 = 1; the second words on each line are printed at the minimal possible position p2, such that all first words end at or before position p2 - 2; the third words on each line are printed at the minimal possible position p3, such that all second words end at or before position p3 - 2, etc.

For the purpose of this problem, the code consists of multiple lines. Each line consists of one or more words separated by spaces. Each word can contain uppercase and lowercase Latin letters, all ASCII punctuation marks, separators, and other non-whitespace ASCII characters (ASCII codes 33 to 126 inclusive). Whitespace consists of space characters (ASCII code 32).

The input file contains one or more lines of the code up to the end of file. All lines (including the last one) are terminated by a standard end-of-line sequence in the file. Each line contains at least one word, each word is 1 to 80 characters long (inclusive). Words are separated by one or more spaces. Lines of the code can have both leading and trailing spaces. Each line in the input file is at most 180 characters long. There are at most 1000 lines in the input file.

Write to the output file the reformatted, aligned code that consists of the same number of lines, with the same words in the same order, without trailing and leading spaces, separated by one or more spaces such that i-th word on each line starts at the same position pi.

Note for the Sample:

The `‘ character in the example below denotes a space character in the actual files (ASCII code 32).

start: integer; // begins here stop: integer; // ends here s: string; c: char; // temp

start: integer; // begins here stop: integer; // ends here s: string; c: char; // temp

题意 质因数只可能有2,3,5的数称为丑数 输出第1500个丑数

STL优队列应用 1是丑数 丑数的2,3,5倍都是丑数 用优先队列模拟就行了

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
32
33
34
35
36

#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

//priority_queue<ll, vector<ll>, greater<ll> > q;
struct cmp{
    bool operator () (ll a, ll b)    { return a > b; }
};
priority_queue<ll, vector<ll>, cmp> q;


set<ll> cnt;
int ugly[3] = {2, 3, 5};
int main()
{
    ll a, b;
    q.push(1);
    cnt.insert(1);
    for(int i = 1;; ++i)
    {
        a = q.top();
        q.pop();
        if(i == 1500) break;
        for(int j = 0; j < 3; ++j)
        {
            b = a * ugly[j];
            if(!cnt.count(b))
                cnt.insert(b), q.push(b);
        }
    }
    printf("The 1500'th ugly number is %lld.\n", a);
    return 0;
}

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500’th ugly number.

Input and Output

There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.

Sample output

The 1500’th ugly number is .

题意 模拟团队队列的入队和出队

STL应用 用一个队列维护团队编号 再用一个队列数组维护个体

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
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
const int N = 1000005;
int team[N];

int main()
{
    int cas = 0, n, t, a;
    char cmd[20];
    while(~scanf("%d", &t), t)
    {

        printf("Scenario #%d\n", ++cas);
        for(int i = 0; i < t; ++i)
        {
            scanf("%d", &n);
            while(n--)
                scanf("%d", &a), team[a] = i;
        }

        queue<int> q, qt[1005];
        while(scanf("%s", cmd), cmd[0] != 'S')
        {
            if(cmd[0] == 'E')
            {
                scanf("%d", &a);
                t = team[a];
                if(qt[t].empty()) q.push(t);
                qt[t].push(a);
            }
            else
            {
                t = q.front();
                printf("%d\n", qt[t].front()), qt[t].pop();
                if(qt[t].empty()) q.pop();
            }
        }
        puts("");
    }
    return 0;
}

Queues and Priority Queues are data structures which are known to most computer scientists. TheTeam Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example.

In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.

Your task is to write a program that simulates such a team queue.

The input file will contain one or more test cases. Each test case begins with the number of teams t ( ). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0 - 999999. A team may consist of up to 1000 elements.

Finally, a list of commands follows. There are three different kinds of commands:

The input will be terminated by a value of 0 for t.

Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the implementation of the team queue should be efficient: both enqueing and dequeuing of an element should only take constant time.

For each test case, first print a line saying `` Scenario /# k “, where k is the number of the test case. Then, for each DEQUEUE command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one.

2 3 101 102 103 3 201 202 203 ENQUEUE 101 ENQUEUE 201 ENQUEUE 102 ENQUEUE 202 ENQUEUE 103 ENQUEUE 203 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 2 5 259001 259002 259003 259004 259005 6 260001 260002 260003 260004 260005 260006 ENQUEUE 259001 ENQUEUE 260001 ENQUEUE 259002 ENQUEUE 259003 ENQUEUE 259004 ENQUEUE 259005 DEQUEUE DEQUEUE ENQUEUE 260002 ENQUEUE 260003 DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 0

Scenario /#1 101 102 103 201 202 203 Scenario /#2 259001 259002 259003 259004 259005 260001

题意 给你一个黑方被将军的象棋残局 判断红方是否已经把黑方将死

模拟题 注意细节就行了 看黑方的将是否四个方向都不能走

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 12;

char brd[N][N];
int dx[] = { -1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int hx[] = { -2, -1, -2, -1, 1, 2, 1, 2};  //马将军
int hy[] = { -1, -2, 1, 2, -2, -1, 2, 1};
int tx[] = { -1, -1, -1, -1, 1, 1, 1, 1};  //马蹩脚
int ty[] = { -1, -1, 1, 1, -1, -1, 1, 1};
int cr[2], cc[2];  //记录炮的坐标

int check(int r, int c)
{
    int i, j, k, tr, tc, cnt;
    if(r < 1 || r > 3 || c < 4 || c > 6) return 1;

    for (j = c - 1; j > 0; --j)   //行被车
    {
        if(brd[r][j])
            if(brd[r][j] == 'R') return 1;
            else break;
    }
    for (j = c + 1; j <= 9; ++j)
    {
        if(brd[r][j])
            if(brd[r][j] == 'R') return 1;
            else break;
    }

    for (i = r - 1; i > 0; --i)  //列被车
    {
        if(brd[i][c])
            if(brd[i][c] == 'R') return 1;
            else break;
    }
    for (i = r + 1; i <= 10; ++i) //列被车或将
    {
        if(brd[i][c])
            if(brd[i][c] == 'R' || brd[i][c] == 'G') return 1;
            else break;
    }

    for(int k = 0; k < 2; ++k)    //被炮将军
    {
        if(cr[k] == r)   //行有炮
        {
            for(j = c - 1, cnt = 0; j > cc[k]; --j) if(brd[r][j]) ++cnt;
            if(cnt == 1) return 1;
            for(j = c + 1, cnt = 0; j < cc[k]; ++j) if(brd[r][j]) ++cnt;
            if(cnt == 1) return 1;
        }
        if(cc[k] == c)   //列有炮
        {
            for(i = r - 1, cnt = 0; i > cr[k]; --i) if(brd[i][c]) ++cnt;
            if(cnt == 1) return 1;
            for(i = r + 1, cnt = 0; i < cr[k]; ++i) if(brd[i][c]) ++cnt;
            if(cnt == 1) return 1;
        }
    }

    for(int k = 0; k < 8; ++k)   //被马将军
    {
        tr = r + hx[k], tc = c + hy[k];
        if(tr < 1 || tr > 10 || tc < 1 || tc > 9) continue;
        if(brd[tr][tc] == 'H' && (!brd[r + tx[k]][c + ty[k]]))
            return 1;
    }

    return 0;
}

int main()
{
    char s[5];
    int n, r, c, x, y;
    while(scanf("%d%d%d", &n, &r, &c), n || r || c)
    {
        memset(brd, 0, sizeof(brd));
        cr[0] = cc[0] = cr[1] = cc[1] = 0;

        while(n--)
        {
            scanf("%s%d%d", s, &x, &y);
            if(s[0] == 'C')
            {
                if(cr[0]) cr[1] = x, cc[1] = y;
                else cr[0] = x, cc[0] = y;
            }
            brd[x][y] = s[0];
        }

        int cnt = 0;
        for(int i = 0; i < 4; ++i)
            cnt += check(r + dx[i], c + dy[i]);
        if(cnt < 4) puts("NO");
        else puts("YES");
    }
    return 0;
}

Xiangqi

Problem Description

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’.
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 NO

题意 求两点之间有多少不同颜色的路径

范围比较小 可以直接floyd

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
32
33
34
35
36

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105;
int d[N][N][N], ans;

int main()
{
    int a, b, c, n, m, q;
    while(~scanf("%d%d", &n, &m))
    {
        memset(d, 0, sizeof(d));
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            d[c][a][b] = d[c][b][a] = 1;
        }

        for(c = 1; c <= m; ++c)
        for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(!d[c][i][j]) d[c][i][j] = d[c][j][i] = (d[c][i][k] && d[c][k][j]);

        scanf("%d", &q);
        while(q--)
        {
            ans = 0;
            scanf("%d%d", &a, &b);
            for(int c = 1; c <= m; ++c)
                if(d[c][a][b]) ++ans;
            printf("%d\n", ans);
        }
    }
    return 0;
}

B. Mr. Kitayuta’s Colorful Graph
Mr. Kitayuta has just bought an undirected graph consisting of n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color c**i, connecting vertex a**i and b**i.

Mr. Kitayuta wants you to process the following q queries.

In the i-th query, he gives you two integers — u**i and v**i.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex u**i and vertex v**i directly or indirectly.

Input

The first line of the input contains space-separated two integers — n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100), denoting the number of the vertices and the number of the edges, respectively.

The next m lines contain space-separated three integers — a**i, b**i (1 ≤ a**i < b**i ≤ n) and c**i (1 ≤ c**i ≤ m). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if i ≠ j, (a**i, b**i, c**i) ≠ (a**j, b**j, c**j).

The next line contains a integer — q (1 ≤ q ≤ 100), denoting the number of the queries.

Then follows q lines, containing space-separated two integers — u**i and v**i (1 ≤ u**i, v**i ≤ n). It is guaranteed that u**i ≠ v**i.
Output

For each query, print the answer in a separate line.

Sample test(s)

input 4 5 1 2 1 1 2 2 2 3 1 2 3 3 2 4 3 3 1 2 3 4 1 4

output 2 1 0
input 5 7 1 5 1 2 5 1 3 5 1 4 5 1 1 2 2 2 3 2 3 4 2 5 1 5 5 1 2 5 1 5 1 4

output 1 1 1 1 2

题意 在一个字符串中插入一个字母使其变成一个回文串 可以的话输出这个回文串 否则NA

大水题 插入情况最多就26/*11种 可以直接暴力

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
32
33
34
35
36

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 20;
char s[N], p[N];
int l;
bool ispal()
{
    for(int i = 0; i < (l + 1) / 2; ++i)
        if(p[i] != p[l - i]) return false;
    return true;
}

int main()
{
    int i, j, k;
    scanf("%s", s);
    l = strlen(s);
    for(char c = 'a'; c <= 'z'; ++c)
    {
        for(k = 0; k <= l; ++k)
        {
            i = j = -1;
            while(i < k - 1) p[++j] = s[++i];
            p[++j] = c;
            while(i < l - 1) p[++j] = s[++i];
            if(ispal())
            {
                printf("%s\n", p);
                return 0;
            }
        }
    }
    printf("NA\n");
    return 0;
}

A. Mr. Kitayuta’s Gift

Mr. Kitayuta has kindly given you a string s consisting of lowercase English letters. You are asked to insert exactly one lowercase English letter into s to make it a palindrome. A palindrome is a string that reads the same forward and backward. For example, “ noon “, “ testset “ and “ a “ are all palindromes, while “ test “ and “ kitayuta “ are not.

You can choose any lowercase English letter, and insert it to any position of s, possibly to the beginning or the end of s. You have to insert a letter even if the given string is already a palindrome.

If it is possible to insert one lowercase English letter into s so that the resulting string will be a palindrome, print the string after the insertion. Otherwise, print “NA” (without quotes, case-sensitive). In case there is more than one palindrome that can be obtained, you are allowed to print any of them.
Input

The only line of the input contains a string s (1 ≤ |s| ≤ 10). Each character in s is a lowercase English letter.

Output

If it is possible to turn s into a palindrome by inserting one lowercase English letter, print the resulting string in a single line. Otherwise, print “NA” (without quotes, case-sensitive). In case there is more than one solution, any of them will be accepted.
Sample test(s)

input revive

output reviver
input ee

output eye
input kitayuta

output NA

大水题 模拟在草稿纸上算除法的过程→_→

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

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 3005;
int a[N], v[N];

int main()
{
    int n, m, cnt;
    while(~scanf("%d%d", &n, &m))
    {
        cnt = 0;
        memset(v, 0, sizeof(v));
        printf("%d/%d = %d.", n, m, n / m);
        n = n % m;
        while(!v[n])
        {
            a[++cnt] = (n * 10) / m;
            v[n] = cnt;
            n = n * 10 % m;
        }
        for(int i = 1; i <= cnt && i < 51; ++i)
        {
            if(i == v[n]) printf("(");
            printf("%d", a[i]);
            if(i == 50) printf("...");
        }
        printf(")\n   %d = number of digits in repeating cycle\n\n", cnt - v[n] + 1);
    }
    return 0;
}

The decimal expansion of the fraction 1/33 is , where the is used to indicate that the cycle 03 repeats indefinitely with no intervening digits. In fact, the decimal expansion of every rational number (fraction) has a repeating cycle as opposed to decimal expansions of irrational numbers, which have no such repeating cycles.

Examples of decimal expansions of rational numbers and their repeating cycles are shown below. Here, we use parentheses to enclose the repeating cycle rather than place a bar over the cycle.

Write a program that reads numerators and denominators of fractions and determines their repeating cycles.

For the purposes of this problem, define a repeating cycle of a fraction to be the first minimal length string of digits to the right of the decimal that repeats indefinitely with no intervening digits. Thus for example, the repeating cycle of the fraction 1/250 is 0, which begins at position 4 (as opposed to 0 which begins at positions 1 or 2 and as opposed to 00 which begins at positions 1 or 4).

Input

Each line of the input file consists of an integer numerator, which is nonnegative, followed by an integer denominator, which is positive. None of the input integers exceeds 3000. End-of-file indicates the end of input.

Output

For each line of input, print the fraction, its decimal expansion through the first occurrence of the cycle to the right of the decimal or 50 decimal places (whichever comes first), and the length of the entire repeating cycle.

In writing the decimal expansion, enclose the repeating cycle in parentheses when possible. If the entire repeating cycle does not occur within the first 50 places, place a left parenthesis where the cycle begins - it will begin within the first 50 places - and place ``…)” after the 50th digit.

Print a blank line after every test case.

Sample Input

76 25 5 43 1 397

Sample Output

76/25 = 3.04(0) 1 = number of digits in repeating cycle 5/43 = 0.(116279069767441860465) 21 = number of digits in repeating cycle 1/397 = 0.(00251889168765743073047858942065491183879093198992…) 99 = number of digits in repeating cycle

大水题一发 弄清长方体的几个面的关系就行了

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
32
33

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 6;

struct rec{ int l, w;} r[N];
bool cmp(rec a, rec b)
{
    return a.w < b.w || (a.w == b.w && a.l < b.l);
}

int main()
{
    int a, b, ok;
    while(~scanf("%d%d", &r[0].w, &r[0].l))
    {
        ok = 1;
        if(r[0].w > r[0].l) swap(r[0].w, r[0].l);
        for(int i = 1; i < 6; ++i)
        {
            scanf("%d%d", &r[i].w, &r[i].l);
            if(r[i].w > r[i].l) swap(r[i].w, r[i].l);
        }

        sort(r, r + N, cmp);
        for(int i = 0; i < N; i += 2)
            if(r[i].w != r[i + 1].w || r[i].l != r[i + 1].l) ok = 0;
        if(r[0].w != r[2].w || r[0].l != r[4].w || r[2].l != r[4].l) ok = 0;

        puts(ok ? "POSSIBLE" : "IMPOSSIBLE");
    }
    return 0;
}

Ivan works at a factory that produces heavy machinery. He has a simple job – he knocks up wooden boxes of different sizes to pack machinery for delivery to the customers. Each box is a rectangular parallelepiped. Ivan uses six rectangular wooden pallets to make a box. Each pallet is used for one side of the box.

Joe delivers pallets for Ivan. Joe is not very smart and often makes mistakes – he brings Ivan pallets that do not fit together to make a box. But Joe does not trust Ivan. It always takes a lot of time to explain Joe that he has made a mistake. Fortunately, Joe adores everything related to computers and sincerely believes that computers never make mistakes. Ivan has decided to use this for his own advantage. Ivan asks you to write a program that given sizes of six rectangular pallets tells whether it is possible to make a box out of them.

Input file contains several test cases. Each of them consists of six lines. Each line describes one pallet and contains two integer numbers w and h ( 1w, h10 000 ) – width and height of the pallet in millimeters respectively.

For each test case, print one output line. Write a single word POSSIBLE ' to the output file if it is possible to make a box using six given pallets for its sides. Write a single word IMPOSSIBLE ‘ if it is not possible to do so.

1345 2584 2584 683 2584 1345 683 1345 683 1345 2584 683 1234 4567 1234 4567 4567 4321 4322 4567 4321 1234 4321 1234

POSSIBLE IMPOSSIBLE

八数码问题 紫书上的简单搜索 渣渣好久才弄懂

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include<cstdio>
#include<cstring>
using namespace std;
const int M = 1000003;
int x[4] = { -1, 1, 0, 0}, y[4] = {0, 0, -1, 1};
int dis[M], h[M], s[M][9], e[9];

int aton(int a[])
{
    int t = 0;
    for(int i = 0; i < 9; ++i)
        t = t * 10 + a[i];
    return t;
}

int search_hash(int a[])
{
    int t = aton(a), p = t % M;
    while(h[p])
    {
        if(h[p] == t) return p;
        ++p;
        if(p >= M) p = 0;
    }
    return p;
}

int bfs()
{
    memset(h, 0, sizeof(h));
    int fro = 1, rear = 2, r, c, k = 0, p;
    int t[9], tmp, cur, nr, nc, nk;

    while(fro < rear)
    {
        memcpy(t, s[fro], sizeof(t));
        cur = search_hash(t);
        if(memcmp(t, e, sizeof(t)) == 0) return dis[cur];
        for(k = 0; t[k];) ++k;
        r = k / 3, c = k % 3;
        for(int i = 0; i < 4; ++i)
        {
            memcpy(t, s[fro], sizeof(t));
            nr = r + x[i], nc = c + y[i], nk = nr * 3 + nc;
            if(nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            tmp = t[nk];
            t[nk] = 0;
            t[k] = tmp;
            p = search_hash(t);
            if(h[p] == 0)
            {
                h[p] = aton(t);
                dis[p] = dis[cur] + 1;
                memcpy(s[rear], t, sizeof(t));
                ++rear;
            }
        }
        ++fro;
    }
    return -1;
}

int main()
{
    while(~scanf("%d", &s[1][0]))
    {
        memset(dis, 0, sizeof(dis));
        for(int i = 1; i < 9; ++i)
            scanf("%d", &s[1][i]);
        for(int i = 0; i < 9; ++i)
            scanf("%d", &e[i]);
        h[aton(s[1]) % M] = aton(s[1]);
        int ans = bfs();
        if(ans != -1)
            printf("%d\n", ans);
        else  printf("No solution\n");
    }
    return 0;
}
/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
2 3 4 1 5 0 7 6 8
1 2 3 4 5 6 7 8 0
*/