Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Return of the Aztecs

Problem I:	Can't be too GREEDY
Time Limit: 5 seconds Memory Limit: 32 MB

---

Greed is all right, by the way I think greed is healthy. You can be greedy and still feel good about yourself. -- Ivan F. Boesky
Greedy coloring LOOSES	Greedy coloring WINS

Okay, don't get confused. Greed is good and greed is bad -- we all know that pretty well. There are problems that can be solved quite easily with greedy approach, and there are problems where it fails.

Your mission, should you choose to accept it, is to show how bad a greedy approach can turn out to be. Given a number of colors, you'd have to show that a greedy approach can be as bad as to need all the colors given to color a tree.

Some useful information:

Any tree with more than one node can be properly colored using two colors only.

Proper Coloring: A coloring of a graph is proper if no two adjacent vertices receive the same color.

Greedy approach for graph coloring: Given a permutation (ordering) of the vertices, color each vertex using the least available proper color. Example: Let A be a vertex that is connected to B, C and D. B is connected to C and D. Given the permutation CDBA, you'd assign color 1 to C, 1 to D, 2 to B and 3 to A. Thus the greedy approach needs 3 colors (which is also optimal in this case) to color this graph.

Degree of a Vertex: The number of vertices connected to this vertex.

Input

There can be multiple test cases. For each test case you'd be given an integer K on a line. 1< K< 16, the number of colors the greedy approach would at least need to color the tree.

Output

For each input case you are to print the tree, followed by an ordering of the vertices that the greedy approach would follow. In the first line, print the number of vertices N and the number of edges M in one line. In the next M lines, print M edges. An edge is represented by two integers separated by a space. In the last line for the test case, print an ordering of the vertices such that the greedy approach would need at least K colors to color the tree properly. The vertex numbers are to be separated by spaces. Any valid solution will be accepted. However, you must strictly adhere to the following constraints.

Constraints:

• Maximum degree for any vertex is K-1
• There can be at most 2^(K-1) vertices
• Vertices are to be numbered 1..N

Sample Input

2
4

Sample Output

2 1
1 2
1 2
8 7
1 2
2 3
2 5
4 3
1 6
8 1
6 7
8 4 7 5 3 6 2 1

Note: The image with the problem statement corresponds to the second sample output. A level order traversal on the tree would have allowed the greedy algorithm to use optimal coloring.

---

Problem setter: Monirul Hasan (Tomal), CSE Dept, Southeast University, Bangladesh

"Academic activities comes first and then comes the extra curricular activities like participating in programming contests, this message should be clear to all" -- some wise men would say to the contestants. But a contestant should be wise enough to safely ignore this message and would be ready to pay whatever prices are to be paid for ignoring the message. The wise contestant would say, "It is the contests that made me learn what I know, the academic activities have left little contribution there."

題目描述：

// 前面在描述如何使用 greedy 策略得到的最少著色數方式
// 每次著新的點時，先看附近有圖哪些顏色，盡可能挑一個使用且不重複的顏色
// 真的不行再增加一個顏色。

由於這種策略上，跟你選擇的圖色順序有關，如果順序好就容易得到最少著色數。
現在要求，隨便給定一棵樹和你所選擇的著色順序，根據 greedy 策略，
恰好得到 K 的著色數。

其中這棵樹的點數最多為 2^(K-1)，每個點的 degree 最多為 K-1。

題目解法：

遞迴結構

對於一個需要 K 種顏色的樹來說，根節點肯定接有 K-1 不同顏色的子節點，

而這些子節點又恰好由 K-1 種顏色的著色子樹。

// 稍微用數學歸納法計算點數，不超過 2^(K-1) 個節點

#include <stdio.h>
#include <vector>
using namespace std;
int node;
vector<int> C[20];
int dfs(int color) {
    int x = ++ node;
    C[color].push_back(x);
    for(int i = 1; i < color; i++)
        printf("%d %d\n", x, dfs(i));
    return x;
}
int main() {
    int K, i, j;
    while(scanf("%d", &K) == 1) {
        int n = 1<<(K-1);
        printf("%d %d\n", n, n-1);
        node = 0;
        dfs(K);
        for(i = 1, j = 0; i <= K; i++)
            for(; !C[i].empty(); C[i].pop_back())
                printf(j++ ? " %d" : "%d", C[i].back());
        puts("");
    }
    return 0;
}