You have recently been appointed as the administrator for a wired network of devices. Unfortunately, your predecessor used very poor quality lines to connect the devices. The board of executives is currently deciding if they want to fund an upgrade to a wireless network, or simply replace the existing wires with ones of better quality. As expected, this decision is being weighed down with bureaucratic nonsense; it looks like it will take some time before anything is approved.

Meanwhile, you still have to deal with the problem at hand. You have access to an antiquated version of Newton Network Monitor which is a software package that, once installed on a machine, will monitor all lines connected to that machine and immediately alert the user when a line has failed. This should help reduce your response time to any failures.

Your task is to install the software on some machines so each line is being monitored by at least one of its endpoint devices. For various technical reasons, the time it takes to install the software varies from device to device so you want to minimize the total amount of time spent installing the software. You cannot install on more than one machine at a time (since you only have one copy of the software) meaning the total time spent installing the software is exactly the sum of the installation times on each machine.

Input Format

Each input case begins with two numbers n,m with 1 ≤ n ≤ 1,000 and 0 ≤ m ≤ 25,000. Following this are m pairs of distinct integers between 0 and n-1 which describe a wire connecting the two devices. The time spent installing the software on machine numbered i is 2i. The input is terminated with n = m = 0; this should not be processed.
Output Format

For each input case, there is to be one line of output containing a sequence of n bits with no spaces. The i’th bit is 1 if the software is installed on machine i, and 0 if not.

Sample Input

1
2
3
4
5
6

3 2
0 2
1 2
3 1
1 2
0 0

Sample Output

1
2

110
010

Solution

題目描述：

給定一個 N 個點的城市和邊，每一條邊上至少有一個點安裝服務，而在編號 i 的地方設置服務器成本為 $2^{i}$，求最少花費。

題目解法：

明顯地，會發現對於編號最大的節點來說，周遭的點數全設置也不會比該點設置來得高，那還不如將周圍都設置服務。藉此，從編號大的開始檢查，如果還沒有設置服務，將其鄰居全都設置服務！

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 <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
vector<int> g[1024];
int main() {
    int n, m, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n + m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int used[1024] = {};
        for(int i = n - 1; i >= 0; i--) {
            if(used[i])	continue;
            for(int j = 0; j < g[i].size(); j++)
                used[g[i][j]] = 1;
        }
        for(int i = 0; i < n; i++)
            printf("%d", used[i]);
        puts("");
    }
    return 0;
}

We are at a funfair, where an array of trampolines, named ‘’The Grasshopper Labyrinth’’, catches our attention. As the figure below shows, all of them are labelled with non-negative integers:

\epsfbox{p11705a.eps}

People are inside, jumping from one trampoline to another, trying to reach the trampoline in the northwest corner, where the exit to the attraction is located. If you reach the exit fast enough, you may win a prize. However, in order to be eligible for the prize, you must abide by the following rule: after leaping from a trampoline labelled with z, you need to get to another one z trampolines away, in the same row or column.

Therefore, your problem is to find the shortest path from any trampoline to the way out, measured by the number of leaps needed. Since the length of the jump from any trampoline is given, it is sufficient to label each trampoline with the direction of the best jump from it.

\epsfbox{p11705b.eps}

For a given starting position, a path is considered shorter than another if it requires a smaller number of jumps; in case of a tie, the path whose first step gets you northmost in the array is to be preferred; and in case of a tie, the one getting you westmost.

Instead of these symbols, we are using the plain text ones: the appropriate cardinal point (‘N’, ‘S’, ‘E’ or ‘W’) for the arrows, ‘X’ for the trampolines without possible escape, and the asterisk ‘*’ for the special trampoline at the upper left position, which represents the exit.

Input

Several cases are given in a single test file. The first line in each test case contains a pair of integers between 1 and 50, separated by a single space; the first is the number of rows and the second the number of columns in the matrix. Then, the entries in the matrix follow, line by line, each element being a non-negative integer, again separated by single whitespace characters. A 0 x 0 matrix will denote the end of the test cases, and hence should not be analyzed.

Output

The expected output of each data case is a character matrix. Each element is one of the allowed charset, N'',S’’, E'',W’’, X'' or*’’, as described above. The output for each case is followed by a blank line.

Sample Input

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

3 4
0 2 2 5
3 1 1 2
2 2 2 1
1 20
0 3 3 3 2 5 10 5 3 4 5 4 4 4 6 4 10 3 5 1
5 6
0 7 2 4 4 4
3 1 3 2 3 1
2 1 4 3 4 3
4 4 2 3 3 3
5 4 4 3 4 5
0 0

Sample Output

1
2
3
4
5
6
7
8
9
10
11

*SWX
EENW
NENW
*EEWWWXWWWWWWWWWXWWW
*XWSWX
ESSWSW
NWXWWX
EEEWNW
XXNNNX

Solution

題目描述：

每一個位置的彈簧上會標記一個數字 w，表示可以跳躍至上下左右其中一個方向的 w 距離所在。
求每一個位置下一步的方向，來獲得最短路徑 (跳躍次數) 到最左上角。

題目解法：

題目忘了講到字典順序，如果有相同的情況，則選擇跳躍越左上角越好。

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

#include <stdio.h> 
#include <queue>
#include <algorithm>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const char ds[] = {'S', 'E', 'N', 'W'};
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, g[64][64];
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                scanf("%d", &g[i][j]);
                
        char ret[64][64] = {};
        int visited[64][64] = {}, x, y, tx, ty, d;
        int vx[64][64], vy[64][64];
        queue<int> X, Y;
        X.push(0), Y.push(0);
        while(!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            for(int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i], d = 1;
                while(tx < n && ty < m && tx >= 0 && ty >= 0) {
                    if(g[tx][ty] == d) {
                        if(visited[tx][ty] == 0) {
                            visited[tx][ty] = visited[x][y] + 1;
                            ret[tx][ty] = ds[i];
                            vx[tx][ty] = x, vy[tx][ty] = y;
                            X.push(tx), Y.push(ty);
                        } else if(visited[tx][ty] == visited[x][y] + 1 
                        && make_pair(x, y) < make_pair(vx[tx][ty], vy[tx][ty])) {
                            ret[tx][ty] = ds[i];
                            vx[tx][ty] = x, vy[tx][ty] = y;
                        }
                    }
                    tx += dx[i], ty += dy[i], d++;
                }
            }
        }
        for(int i = 0; i < n; i++, puts("")) {
            for(int j = 0; j < m; j++) {
                if(i == 0 && j == 0)
                    putchar('*');
                else if(visited[i][j] == 0)
                    putchar('X');
                else
                    putchar(ret[i][j]);
            }
        }
        puts("");
    }
    return 0;
}

After writing a solver for the “moveable maze” game last week, you have grown tired of it. After all, you already know the optimal solution. To entertain yourself, you find another puzzle game called “Pipes”, and play that for a while. On one puzzle, you have not been able to find a solution by hand, and you think that there is no solution. You decide to write a program to tell you whether this is the case.

The game is played on a grid with R rows and C columns. Each square of the grid contains a black dot in the centre and black lines in the direction of some, none, or all of its north, east, south, and west neighbouring squares, with the following restriction: if two opposite directions both have lines, then at least one of the other two directions has a line as well. In other words, it is forbidden for a square to consist of a straight line.

The objective of the game is to rotate each square, as many times as you like, such that for each square, if it has a line going in a compass direction (that is, north, east, south, or west), then it has a neighbour in that compass direction and that neighbour has a line going in the opposite compass direction. In other words, each edge in the grid should either have a line on both sides or neither side.

Your task is to determine whether a given grid has a solution.

Input Specification

The input consists of several test cases.

The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R,C <= 12.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

• If the string is the single character x, then the square does not contain a line to any of its neighbours.
• Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

Sample Input

1
2
3
4
5
6
7
8

3 3
NW NW x
NES NESW W
E W x
2 2
ES x
x N
0 0

Output Specification

For each test case, output SOLVABLE if there is a solution to the puzzle, and UNSOLVABLE otherwise.
Output for Sample Input

1
2

SOLVABLE
UNSOLVABLE

Solution

題目描述：

一個類似水管通路的遊戲，每一格都會有四個方向的缺口，請將每一個缺口與相鄰的格子缺口對齊。

題目解法：

當初以為是要從某一個邊流向到另一個邊，但是題目並沒有說明這些，其實就假想每一個格子都會有四個方向的標記，翻轉每一個格子，標記和標記之間要對到。(有標記的邊一定要與另一個有標記的邊相鄰)

因此，類似於關燈遊戲的窮舉方式，從左上依序窮舉到右下，同時檢查上一列的條件是否符合。

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
102
103
104
105
106
107
108

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int g[16][16][4], n, m;
int kind[16][16], solvable;
static const int dx[] = {-1, 0, 1, 0}; // N, E, S, W
static const int dy[] = {0, 1, 0, -1};
void rotate(int r, int c) {
    int t = g[r][c][0];
    for(int i = 1; i < 4; i++)
        g[r][c][i-1] = g[r][c][i];
    g[r][c][3] = t;
}
int check(int r, int c, int ign) {
    for(int i = 0; i < 4; i++) {
        if(i == ign)	continue;
        if(g[r][c][i]) {
            int tx = r + dx[i], ty = c + dy[i];
            if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                return 0;
            if(!g[tx][ty][(i+2)%4])
                return 0;
        }
    }
    return 1;
}
void dfs(int r, int c) {
    if(solvable)
        return;
    if(c == m) {
        if(check(r, c-1, 2))
            dfs(r + 1, 0);
        return ;
    }
    if(r == n) {
        int f = 1;
        for(int i = 0; i < m; i++)
            f &= check(r-1, i, -1);
//		if(f)
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < m; j++) {
//				printf("[%d, %d] ", i, j);
//				for(int k = 0; k < 4; k++)
//					printf(" %d", g[i][j][k]);
//				puts("");
//			}
//		}
        solvable |= f;
        return;
    }
    
    if(kind[r][c] == 0) {
        if(check(r-1, c, -1)) {
            if(c && !check(r, c-1, 2))
                return;
            dfs(r, c+1);
        }
    } else {
        for(int i = 0; i < kind[r][c]; i++, rotate(r, c)) {
            if(check(r-1, c, -1)) {
                if(c && !check(r, c-1, 2))
                    continue;
                dfs(r, c+1);
            }
        }
    }
}
int main() {
    char s[128], mapped[128] = {};
    mapped['N'] = 0;
    mapped['E'] = 1;
    mapped['S'] = 2;
    mapped['W'] = 3;
    while(scanf("%d %d", &n, &m) == 2 && n + m) {
        memset(g, 0, sizeof(g));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                scanf("%s", s);
                if(s[0] != 'x') {
                    for(int k = 0; s[k]; k++)
                        g[i][j][mapped[s[k]]] = 1;
                }
                if(s[0] == 'x')
                    kind[i][j] = 0;
                else {
                    int len = strlen(s);
                    if(len == 4)
                        kind[i][j] = 0;
                    else if(len == 1 || len == 3)
                        kind[i][j] = 4;
                    else {
                        if(g[i][j][0] == g[i][j][2])
                            kind[i][j] = 2;
                        else
                            kind[i][j] = 4;
                    }
                }
            }
        }
        solvable = 0;
        dfs(0, 0);
        puts(solvable ? "SOLVABLE" : "UNSOLVABLE");
    }
    return 0;
}

Problem

In ancient times, communication was not as swift as it is today. When a kingdom was at war, it could take months to muster all the armed forces. But by using fire-lit beacons at strategic locations, it was still possible to quickly send emergency signals.

When the first beacon is lit, all other beacons within sight from it are also lit. All beacons within sight of these are then lit, and so on until all beacons are lit - assuming of course that all beacons are within sight of each other, directly or indirectly. If they are not, the dire news must be carried by riders between some beacons.

Given the location of all beacons in the kingdom as well as the location and size of all mountain peaks, write a program that determines how many messages must be sent by riders in order for all beacons to be lit when an enemy threatens the country.

For simplicity, we model the country in the following way: a beacon is represented as a point in the xy-plane and a mountain peak is represented as a circle. Two beacons are considered to be within sight of each other if no mountain peak blocks the straight line between the two beacons.

The input will be constructed so that the straight line between any pair of beacons will not touch the circumference of a mountain peak, unless it passes through the interior of another mountain peak. Mountain peaks will not overlap or touch, nor will any beacon be on a mountain peak or on its circumference.

Input

The first line of the input file contains an integer N (N<25) which denotes the total number of test cases. The description of each test case is given below:

The first line of input for each test case contains two integers n (1 ≤ n ≤ 1000) and m (0 ≤ m ≤ 1000) the number of beacons and the number of mountain peaks, respectively. Then follow n lines specifying the locations of the beacons. The location of each beacon is given as a pair of integers x and y (0 ≤ x, y ≤ 10000). Then follow m lines describing the mountain peaks. Each mountain peak is given as a pair of integers x and y x(0 ≤ x, y ≤ 10000) specifying the location of the peak and a radius r (1 ≤ r ≤ 5000).

Output

For each test case the output should be a line containing a single integer: the number of messages that must be carried by riders for all beacons to be lit.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2
6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1

Sample Output

1
2

2
1

Solution

題目描述：

每個山峰將會由一個點為圓心和半徑構成，而從編號 1 將會發送狼煙，這個狼煙要傳遞到每一個其他點，但有可能會被山峰擋住 (當作圓柱也行)，因此必須採用人工的方式將訊息傳遞到另一個點進行施放，當每一個點獲得訊息後，也會點燃狼煙傳給其他點。

求最少的人工傳遞次數。

題目解法：

找到這題的 graph，接著找有多少個 component 即可，但是對於建造 graph 的成本上，不能使用 O(n n m) 任抓兩個點並且檢查是否有圓柱遮蔽。

窮舉對於每一個點，將其當作圓心，得到其他點的極角排序，接著對於每一個圓柱找到遮蔽的極角區間，二分搜索區間後，直接針對該區間的點進行圓柱遮蔽判斷。如此一來建圖的效率就能快很多。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
Pt D[1024], E[1024];
double Er[1024];
#define maxL (1048576>>5)+1
#define GET(x) (g[(x)>>5]>>((x)&31)&1)
#define SET(x) (g[(x)>>5] |= 1<<((x)&31))
int g[maxL];
void buildGraph(int n, int m) {
    memset(g, 0, sizeof(g));// all link
    sort(D, D+n); // let (i, j) i < j for polar angle in [-pi/2, pi/2]
    for(int i = 0; i < n; i++) {
        vector< pair<double, int> > A;
        for(int j = i+1; j < n; j++)
            A.push_back(make_pair(atan2(D[j].y - D[i].y, D[j].x - D[i].x), j));
        sort(A.begin(), A.end());
        for(int j = 0; j < m; j++) { // test obstacle
            double mm = atan2(E[j].y - D[i].y, E[j].x - D[i].x);
            double theta = asin(Er[j] / dist(E[j], D[i])), L = mm - theta, R = mm + theta;
            int st = lower_bound(A.begin(), A.end(), make_pair(L, -1)) - A.begin();
            for(int k = st; k < A.size() && A[k].first <= R; k++) {
                if(dot(D[i] - D[A[k].second], E[j] - D[A[k].second]) > 0)
                    SET(i * n + A[k].second), SET(A[k].second * n + i);
            }
        }
    }
}
int visited[1024];
void dfs(int u, int n) {
    visited[u] = 1;
    for(int i = 0; i < n; i++) {
        if(!GET(u * n + i) && !visited[i]) {
            dfs(i, n);
        }
    }
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++) 
            scanf("%lf %lf", &D[i].x, &D[i].y);
        for(int i = 0; i < m; i++)
            scanf("%lf %lf %lf", &E[i].x, &E[i].y, &Er[i]);
        buildGraph(n, m);
        int ret = 0;
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) // compute how many component
            if(visited[i] == 0)
                dfs(i, n), ret++;
        printf("%d\n", ret - 1);
    }
    return 0;
}
/*
2
6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1
*/

Problem

Gray Inc. is a software fabricant specialized in management of Gray codes. An n-binary code, for n $\geq$ 1, is a sequence of words w0, w1,… that includes every possible binary word of n bits. An n-Gray code is an n-binary code such that between any two consecutive words there is only one bit that changes, i.e., they differ at exactly one position. As you might be aware by now, there are many n-Gray codes.

Gray Inc. produces its own particular kind of Gray code in the following way (name Gn the produced n-Gray code, n $\geq$ 1):

The notation defining Gn should be understood as follows:

=    {% math %}\displaystyle \langle{% endmath %}00, 01, 11, 10{% math %}\displaystyle \rangle{% endmath %}

and

G3 = (0G2) (1G2R)
= (0$\displaystyle \langle$00, 01, 11, 10$\displaystyle \rangle$) (1$\displaystyle \langle$00, 01, 11, 10$\displaystyle \rangle^_{}$)
= (0$\displaystyle \langle$00, 01, 11, 10$\displaystyle \rangle$) (1$\displaystyle \langle$10, 11, 01, 00$\displaystyle \rangle$)
= $\displaystyle \langle$000, 001, 011, 010$\displaystyle \rangle$$\displaystyle \langle$110, 111, 101, 100$\displaystyle \rangle$
= $\displaystyle \langle$000, 001, 011, 010, 110, 111, 101, 100$\displaystyle \rangle$

Observe that not only Gn is an n-Gray code, but also a circular Gray code as the first word in the sequence may be regarded as the successor of the last one in the sequence.

Gray Inc. wants your help to solve the following problem: given a binary word w in Gn and a natural number m, they want to produce the binary word in the sequence Gn that is m words ahead w in the listing (of course, considering the circular ordering described above). Can you help them?

Input

The problem input consists of several cases, each one defined by a line with an integer m ( 0 < m $\leq$ 1000), and a binary n-word w ( 1 $\leq$ n $\leq$ 100), separated by one blank.

The end of the input is given by a line with m = 0 and w = 0.

Output

For each input case, your solution should output the n-binary word that is m words ahead of w in the listing of Gn.

Sample Input

1
2
3
4
5
6
7

1 0
3 0
1 1
1 11
6 011
123 010101010
0 0

Sample Output

1
2
3
4
5
6

1
1
0
10
000
111100100

Solution

題目描述：

根據格雷碼的產生方式，找到某個格雷碼的下 m (m < 1000) 個格雷碼為何。

題目解法：

由於給定的格雷碼長度可能太長，因此如果要用數學解的話必須搭配大數處理，然而 m 就相對於小，因此直接使用原本的格雷碼窮舉方式，針對給定的格雷碼進行還原操作，還原結束後，開始計數直到指定的格雷碼。

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

#include <stdio.h> 
#include <string.h>
//#define DEBUG
int gray(int n, int k) { // find k-th gray code
    if(n == 0)  return 0;
    if(k >= (1<<(n-1)))
        return (1<<(n-1)) | gray(n-1, (1<<(n))-k-1);
    else
        return gray(n-1, k);
}
int path[128];
void grayNext(int idx, int n, char w[], int& k, int &f) {
    if(f == 2)	return;
    if(idx == n) {
        if(f == 0) {
            f = 1;
        } else {
            k--;
            if(k == 0) {
                for(int i = 0; i < n; i++)
                    printf("%d", path[i]);
                puts("");
                f = 2;
            }
        }
#ifdef DEBUG
        for(int i = 0; i < n; i++)
            printf("%d", path[i]);
        puts("");
#endif
        return ;
    }
    if(f == 0) {
        if(w[idx] == path[idx] + '0') {
            grayNext(idx+1, n, w, k, f);
            path[idx] = !path[idx];
            grayNext(idx+1, n, w, k, f);
        } else {
            for(int i = idx; i < n; i++)
                path[i] = 0;
            path[idx] = w[idx] - '0';path[idx+1] = 1;
            grayNext(idx+1, n, w, k, f);
        }
    } else {
        grayNext(idx+1, n, w, k, f);
        path[idx] = !path[idx];
        grayNext(idx+1, n, w, k, f);
    }
    
}
int main() {
    int n, m, f;
    char w[1024];
    while(scanf("%d %s", &n, w) == 2 && n) {
        f = 0;
        memset(path, 0, sizeof(path));
        m = strlen(w);
//		printf("find next %d\n", n);
        grayNext(0, m, w, n, f);
        while(n) {
            memset(path, 0, sizeof(path));
            grayNext(0, m, w, n, f);
        }
    }
    return 0;
}

Problem

The university canteen does not want any student to leave the canteen hungry. Therefore, as long as a student is hungry, he can get another portion of food for free. The canteen uses a fixed food portion size, because it would take too much time to first ask a student how much food he wanted. It can happen that a student doesn’t finish his last portion of food and the remainder has to be thrown away.

To minimize costs, the manager of the canteen wants to determine a food portion size S such that the amount of food that is wasted is small, but also the number of times the students have to fetch another portion of food is not too big. Note that these two goals can be conflicting:

• By choosing a very small food portion size, one does not waste food, but simultaneously the number of times the students have to fetch food is big.
• By choosing a large food portion size, one can make sure each student has to fetch only one portion, but at the same time it may happen that a large quantity of food is wasted.

The manager of the canteen has collected data about how many units of food each student eats. The problem to be solved can now be formulated mathematically as follows: Let x be the amount of food that is wasted, and y the number of times the students go to fetch food. Then, the goal is to minimize a × x + b × y, where a, b are weights that represent the relative importance of the two opposing goals. Note that x and y depend on the food portion size S and the quantities of food each student eats. We impose the additional constraint that no student should have to go more than 3 times to fetch food.

Input Specification

The input file contains several test cases. Each test case starts with a line containing an integer n, (1 ≤ n ≤ 1000), the number of students eating in the canteen. The next line contains the values a and b (1 ≤ a, b ≤ 10). The third line of each test case consists of n integers y1, …, yn (1 ≤ yi ≤ 100), where yi is the amount of food student i eats. Input is terminated by n=0.
Output Specification

For each test case print one line containing the costs resulting from an optimal choice of the food portion size. Print each value as a reduced fraction. If the result is an integer, do not print the denominator 1. See the sample output for details.

Sample Input

1
2
3
4
5
6
7
8
9
10

5
1 1
3 7 1 9 12
3
10 1
11 13 17
2
2 3
6 3
0

Sample Output

1
2
3

35 / 2
154 / 3
9

Solution

題目描述：

學生餐廳為了不讓學生餓肚子，以及方便他們為每一個學生製作餐點，每一份餐點的量都會相同，然而一份餐點對於某些學生來說太少，因此必須多跑幾次餐廳才能吃飽，已知每位學生不會跑大於 3 次餐廳，而每位學生只會吃自己所需要的份量，剩餘的份量就是浪費。

請最小化 $ax + by$，其中 a, b 為給定的常數，x 為所有學生所製造的廚餘，y 為所有學生跑餐廳次數的總和。

題目解法：

由於可能跑 1, 2, 3 次，通分得到分母為 6，保證最小化一定通過某一個人的其中一種情況，窮舉每一個人跑餐廳的次數後，並且在合法的情況下 (所有人皆不大於 3 次。)，計算 $ax + by$ 的結果。

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

#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int n, a, b;
    int v[1024];
    while(scanf("%d", &n) == 1 && n) {
        scanf("%d %d", &a, &b);
        
        int mx = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &v[i]);
            v[i] *= 6; // v[i]/3, v[i]/2, v[i]/1
            mx = max(mx, v[i]);
        }
        
        int minCost = 0x3f3f3f3f;
        for(int i = 0; i < n; i++)  {
            for(int j = 1; j <= 3; j++) {
                int S = v[i]/j;
                int x = 0, y = 0;
                
                if(S * 3 < mx)	continue;
                
                for(int k = 0; k < n; k++) {
                    x += (S * (v[k]/S + (v[k]%S != 0)) - v[k]);
                    y += v[k]/S + (v[k]%S != 0);
                }
                if(a * x + 6 * b * y < minCost)
                    minCost = a * x + 6 * b * y;
            }
        }
        if(minCost%6 == 0)
            printf("%d\n", minCost /6);
        else {
            int div = 6, g = __gcd(minCost, div);
            div /= g, minCost /= g;
            printf("%d / %d\n", minCost, div);
        }
    }
    return 0;
}

Problem

The Elias gamma code is a simple code which can be used to encode a sequence of positive integers. We will use a modified code which is also able to encode zeros. To encode an integer n, do the following:

Let k be the number of bits of n
Write k-1 zeros followed by a 1
Write n in binary

Examples

Number     Binary     Number of bits     Prefix     Code
0     0     1     1     10
1     1     1     1     11
2     10     2     01     0110
3     11     2     01     0111
4     100     3     001     001100
5     101     3     001     001101
6     110     3     001     001110
7     111     3     001     001111
8     1000     4     0001     00011000

A sequence of integers is encoded by writing the codes of the individual integers of the sequence in the same order as the integers appear in the sequence. The prefix of k additional bits before the binary representation of each integer is needed to be able to decode the encoded integers. So when reading the encoding of a sequence of integers, if we read k-1 zeros followed by a one, it means that there are k bits following which are the binary representation of the next encoded integer.

If we want to shorten the length of the encoding of a sequence of integers, there may be still some room for improvement; we will consider the following two optimizations:

• If there is a prefix which indicates that k bits are following, but there is no integer in the sequence with k bits, we can use this prefix to indicate that k+1 bits are following. If there already was a prefix which indicates that k+1 bits are following, this prefix is not needed anymore, and it can be used to indicate that k+2 bits are following, and so on.

• We can add a leading zero to the binary representation of all integers in the sequence with k bits, which then become integers with k+1 bits, and then the first optimization can be used. This optimization seems especially useful if there are few integers with k bits, but many integers with more than k bits.

When we are minimizing the length of the encoding of a sequence of integers, we only care about how many integers in the sequence have a certain number of bits. Let ci denote the number of integers in a sequence with i bits.

Let us look at the following example: c1 = 2, c2 = 4, c3 = 0, c4 = 1 (which, for example, could correspond to a sequence 2, 1, 3, 8, 0, 2, 3). With the original elias gamma coding, the encoding of the sequence would have length 2 × (1 + 1) + 4 × (2 + 2) + 0 × (3 + 3) + 1 × (4 + 4) = 28. By using optimization 1 we can save 1 bit by using prefix 001 for the integer with 4 bits. Then, we could use optimization 2 and add leading zeros to the integers with 1 bit, making them use 2 bits. Then, we use optimization 1 and use prefix 1 for the integers with 2 bits, prefix 01 for the integer with 4 bits, and we get the new length of 6 × (1 + 2) + 1 × (2 + 4) = 24.

Both optimizations can possibly be used several times. Note that for the second optimization, it is not easy to decide when and how to use it. The goal is to combine these two optimizations in the best possible way, that means we want to find an encoding of a given sequence of integers that has minimum length among all encodings using elias gamma coding with any combination of these two optimizations.

Input Specification

The input file contains several test cases. Each test case starts with a line containing an integer n, (1 ≤ n ≤ 128). The next line contains the values c1, …, cn (0 ≤ ci ≤ 10000). Input is terminated by n=0.
Output Specification

For each test case print one line with the minimum length of an encoding of the given input sequence.

Sample Input

1
2
3
4
5
6
7

4
2 4 0 1
5
9 4 2 4 3
11
44 56 96 26 73 80 77 50 33 16 78
0

Sample Output

1
2
3

24
99
5494

Solution

題目描述：

對於一個編碼而言，假使全部存放數字，採用固定長度的方式儲存，就類似全部使用 32 bit 形式，但這樣會浪費相當多的首位 0，因此題目給定多一個欄位表示接下來會有多少 bits，這樣方式有可能會增加編碼長度，因此會有以下優化。

• 將一個原本使用 k bits 表示的數字，使用多於 k bits 表示，也就是多補給個 0。
• 對於欄位表示，將使用映射的方式進行，由於前一條規則，將會有無用的欄位格式，因此可以將比較短的表示法給更多 bits 的數字使用。

題目解法：

題目相當冗長，其實就相當於將 3 bit 數字弄成 4 bit，並且讓 3 bits 和 4 bits 共用同一種欄位表示法 (001 之類的，原本 4 bit 必須使用 0001，現在反而能用更少。)。

使用 dp[i][j] 表示前 i bits 表示法使用最大 j bits 欄位的最小成本。

1
2

dp[j][k] = min(dp[j][k], dp[i-1][k-1] + sum * (k + j));
// sum 表示 [i, j] 之間的 bits 數字總量，k + j 表示單一數字的表示長度。

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

#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
int main() {
    int n, A[256];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int dp[256][256];
        memset(dp, 63, sizeof(dp));
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++) {
            int sum = 0;
            for(int j = i; j <= n; j++) {
                sum += A[j];
                for(int k = 1; k <= n; k++) {
                    dp[j][k] = min(dp[j][k], dp[i-1][k-1] + sum * (k + j));
                }
            }
        }
        int ret = 0x3f3f3f3f;
        for(int i = 0; i <= n; i++)
            ret = min(ret, dp[n][i]);
        printf("%d\n", ret);
    }
    return 0;
}

Problem

Wile E. Coyote is back. He is back in the business. The business of capturing the road runner. Being the most loyal customer to the Acme Corporation, they are hoping to do some great business with him. Although, Acme makes literally every kinds of devices, all of them has a similarity, that has been kept secret for ages. All of their products use a secret element “element X” (this is kept so secret that, only you and the Acme people know about this). The decision makers of the Acme Corp. has already estimated the maximum amount of element X that can be used into manufacture every month.

For month i, the per unit manufacturing cost of “element X” is mi, and at most ni units can be produced. Moreover, the selling price for “element X” for that month is pi. One more thing is that, element X older than Ei months can not be used. But good thing is that, they can store any amount of element X in their inventory (it’s the Acme Corp, they can make anything :) ). Now, Acme Corporation wants to know how much element X should be produced and sold, to make the highest amount of profit.

Input

l First line contains T, the number of test cases.

l For each test case

u First line contains two integers M and I, the number of months to consider and the cost of storing per unit of element X per month in the inventory.

u Each of the next M lines describe the parameters for each month

· The ith line contains 5 integers, mi, ni, pi, si, Ei, where mi is the per unit manufacturing cost for month i, ni is the maximum amount that can be manufactured in this month, pi is the selling price for that month(per unit), si is the maximum amount that can be sold that month, and Ei is the maximum time,element X manufactured on month i, can be stored in the inventory. For example, if for month 1, E1 = 3, the elements produced in month 1 can be sold in months 1, 2, 3 and 4. But it can not be sold in month 5.

Output

For each test case, output the case number and the maximum amount of profit, Acme Corporation can make. Note that, you have to think of only M months. If any amount of element X is stored in the inventory after this period, are completely ignored. For formatting, see the sample input and output.

Sample Input

1
2
3
4

1
2 2
2 10 3 20 2
10 100 7 5 2

Output for Sample Input

1

Case 1: 20

Solution

題目描述：

這個工廠，每個月會生產商品，在每個月中，每一個商品會有其生產成本、該月最大生產量、該月最大銷售量、產品的保存期限。

然而沒有銷售的的商品，將會放置於倉庫，每個月的保管成本為 I。求最大獲益金額為何。

題目解法：

將銷售金額與負號，最小費用流即最大獲益。

source - product - sell - sink，將每一個月的訊息拆成兩個節點，生產的數量和銷售的情況，並且根據保存期限，將該月的生產數量拉至可預期的銷售時間，並且同時扣除保管成本。

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

 
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>
using namespace std;
struct Node {
    int x, y;
    long long cap, cost;// x->y, v
    int next;
} edge[262144];
int e, head[512], prev[512], record[512], inq[512];
long long dis[512];
void addEdge(int x, int y, long long cap, long long cost) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
long long mincost(int s, int t) {
    long long mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        int oo = dis[0];
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while(!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    prev[y] = x, record[y] = i;
                    if(inq[y] == 0) {
                        inq[y] = 1;
                        if(Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if(dis[t] > 0)	break;
        flow = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int testcase, cases = 0;
    int M, I;
    int pm[128], pn[128], pp[128], ps[128], pe[128];
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d %d", &M, &I);
    	e = 0;
        memset(head, -1, sizeof(head));
        
        int source = 2 * M + 2, sink = source + 1;
        for(int i = 1; i <= M; i++)
        	scanf("%d %d %d %d %d", pm+i, pn+i, pp+i, ps+i, pe+i);
#define INF 0x3f3f3f3f
        for(int i = 1; i <= M; i++) {
        	addEdge(source, 2*i, pn[i], pm[i]);
        	for(int j = i; j <= min(i + pe[i], M); j++)
        		addEdge(2*i, 2*j+1, INF, (j - i) * I);
        	addEdge(2*i+1, sink, ps[i], -pp[i]);
        }
        
        printf("Case %d: %lld\n", ++cases, -mincost(source, sink));
    }
    return 0;
}

You are given a 3D grid, which have dimensions N, M and P. Each of the M x N x P cells has a light. Initially all lights are off. You will have K turns. In each of the K turns,

• You will select a cell A randomly from the grid

• You will select a cell B randomly from the grid

• Toggle the states of all the bulbs bounded by cell A and cell B, ie make all the ON lights OFF and make all the OFF lights ON which are bounded by A and B. To be more clear, consider cell A is (x1, y1, z1) and cell B is (x2, y2, z2). Then you have to toggle all the bulbs in grid cell (x, y, z) where min(x1,x2)<=x<=max(x1,x2) , min(y1,y2)<=y<=max(y1,y2) and min(z1, z2)<=z<=max(z1, z2).

How many bulbs are expected to be ON after K turns?

Note:

• A and B can be the same cell.

Input

First line of the input is an integer T(T<101) which denotes the number of test cases. Each of the next T lines represents one test case by 4 integers N, M, P (0 < M, N, P < 101) and K (0<=K<=10000) separated by spaces.

Output

Output one line for each test cases giving the expected number of ON lights. Up to 1E-6 error in your output will be acceptable. Print the case number followed by the output. Look at the sample output for exact format.

Sample Input

1
2
3

2
2 3 4 1
2 3 4 2

Output for Sample Input

1
2

Case 1: 6.3750000000
Case 2: 9.0976562500

Solution

題目描述：

在 N x M x P 的三維空間中，任抓 2 個格子所構成的長方體，將長方體內部的所有格子點進行反轉標記 (一開始全是 OFF)，抓取 K 次得到的 ON 標記格子數期望值為何？

題目解法：

每一個軸的情況可以分開考慮，考慮對於座標 (x, y, z) 被選到的機率 p，則 sigma(p * 1) = 所求的期望值。

1
2

p = dp[N][x] * dp[M][y] * dp[P][z],
dp[i][j] 表示在區間 [1, i] 中任挑區間包含 j 的機率為何。

得到 p 之後，計算在 K 次中，得到奇數 ON 的機率為何，這裡藉由矩陣乘法來完成。

1
2
3
4

[1 - p, p]
[p, 1 - p] = M
         [0  ON]    [final ON  p]
M ^ K *  [1 OFF]  = [final OFF p]

藉由快速取冪次來完成。

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

#include <stdio.h> 
#include <string.h>
struct Matrix {
    double v[2][2];
    int row, col; // row x col
    Matrix(int n, int m, double a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < x.col; j++)
                for(int k = 0; k < col; k++)
                    ret.v[i][j] += v[i][k] * x.v[k][j];
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int N, M, P, K;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d %d", &N, &M, &P, &K);
        double pN[128], pM[128], pP[128];
        for(int i = 1; i <= N; i++)
            pN[i] = (i * (N-i+1) * 2 - 1) / (double)(N * N);			
        for(int i = 1; i <= M; i++)
            pM[i] = (i * (M-i+1) * 2 - 1) / (double)(M * M);
        for(int i = 1; i <= P; i++)
            pP[i] = (i * (P-i+1) * 2 - 1) / (double)(P * P);
        double ret = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                for(int k = 1; k <= P; k++) {
                    double p = pN[i] * pM[j] * pP[k];
                    Matrix mm(2, 2);
                    mm.v[0][0] = mm.v[1][1] = 1 - p;
                    mm.v[0][1] = mm.v[1][0] = p;
                    Matrix mmk = mm ^ K;
                    ret += mmk.v[0][1];
                }
            }
        }
        printf("Case %d: %.10lf\n", ++cases, ret);
    }
    return 0;
}

Problem

My appartment has n computers. My friend’s appartment also has n computers. In each appartment, some pairs of computers are connected to each other with AcidNet cables (ignoring the routers). Each connection has a certain bandwidth (in bytes per second). My friend always brags about the speed of his computer network. He always shows me his n-by-n table that lists the bandwidths between each pair of computers. My network is slower, and I want to rebuild it. So I want to know how I should connect my computers in order to have the same n-by-n bandwidth table.

Since I don’t want to buy too many AcidNet cables, you’ll need to find a solution with the minimum number of connections. You may use AcidNet cables of any integer bandwidth - they all have the same price at my local Imaginary Hardware Store.
Problem, in short

Given a graph, you can compute the all-pairs maximum flow table, right? Now do the opposite: given an n-by-n symmetric table, find a graph with fewest edges that has the given table of all-pairs maximum flows.

Input

The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 200), followed by n lines with n integers each, giving the table T.

T[u][u] will always be 0.
T[u][v] will always be positive and equal to T[v][u].
T[i][j] ≤ 10000

T[u][v] is the largest possible speed (in bytes per second) for sending information from computer u to computer v, assuming there is no other traffic on the network.

Output

For each test case, output one line containing “Case #x:” followed by m - the number of cables I have to buy. The next m lines will each contain 3 integers u, v and w meaning that I need to connect computer u to computer v using an AcidNet cable of bandwidth w. Computers are numbered starting at 0.

If there is no solution, print Impossible.

Sample Input

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

4
2
0 10
10 0
3
0 1 1
1 0 2
1 2 0
1
0
4
0 2 2 1
2 0 2 2
2 2 0 2
1 2 2 0

Output for Sample Input

1
2
3
4
5
6
7

Case #1: 1
0 1 10
Case #2: 2
0 1 1
1 2 2
Case #3: 0
Case #4: Impossible

Solution

題目描述：

朋友給一個他的端點之間的頻寬關係，這些頻寬關係是對稱的，現在要用最少條的邊做出跟朋友一樣的網路頻寬關係，請問是否有可能，如果可能的話，請輸出需要擺設的邊。

題目解法：

假設有 n 個節點，要用最少條構成，相當於給定一個 n - 1 條邊的 tree，對於一個 tree 而言，彼此之間的流量關係符合不等式

也就是說，如果存在更好的流量方式，則會在關係圖中表示出來。在判斷是否可能即檢查所有情況是否符合不等式。最後根據這條不等式，相當於最小生成樹中 s - t 集合中的關係。

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

#include <stdio.h> 
#include <algorithm>
using namespace std;
struct E {
    int x, y, v;
    E(int a = 0, int b = 0, int c = 0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v > a.v;
    }
};
E D[65536];
int p[256], rank[256];
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)	return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int main() {
    int testcase, cases = 0, n, g[256][256];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        printf("Case #%d: ", ++cases);
        int eflag = 0;
        for(int i = 0; i < n; i++)
            for(int j = i+1; j < n; j++)
                for(int k = j+1; k < n; k++)
                    if(min(g[i][j], g[j][k]) > g[i][k] ||
                        min(g[i][k], g[j][k]) > g[i][j] ||
                        min(g[i][j], g[i][k]) > g[j][k])
                        eflag = 1, i = j = k = n;
        if(eflag)  {
            puts("Impossible");
            continue;
        }
        printf("%d\n", n - 1);
        int m = 0;
        for(int i = 0; i < n; i++)
            p[i] = i, rank[i] = 1;
        for(int i = 0; i < n; i++)
            for(int j = i+1; j < n; j++)
                D[m++] = E(i, j, g[i][j]);
        sort(D, D+m);
        for(int i = 0; i < m; i++) {
            if(joint(D[i].x, D[i].y)) {
                printf("%d %d %d\n", D[i].x, D[i].y, D[i].v);
            }
        }
    }
    return 0;
}