# Fork() Makes Trouble

### From Progteam

Sorter: | Uncategorized |
---|---|

Source: | Unknown |

Link: | http://acm.pku.edu.cn/JudgeOnline/problem?id=1680 |

**Fork() Makes Trouble** is problem number 1680 on the Peking University ACM
site. This is a binary tree creation/traversal problem solved using good old DFS.

## Solution

// If you put this into PKU, remember to first get rid of all comments, otherwise you will // get a compile error. #include <stdio.h> #include <math.h> //For convenience sake #define exp(x, y) (int)(pow((double)x, (double)y)) //Global variable int P; // Both functions fill the array "tree" with DFS ordering of the binary tree // The binary tree is really a recreation of the process tree that comes to be when // father processes fork off child processes. The left node is the child process // while the right node is the father process waiting for the child node to do it's thing. // Therefore in "create_bt_loop_dfs" we just pass the root_val to the right node, while passing // an increment of the global variable P to the left node. // // In "create_bt_dfs" we're just making an array with the DFS ordering of the binary tree. void create_bt_loop_dfs(int *tree, int *depth_tree, int root, int root_val, int depth, int N) { depth_tree[root] = N - depth; if (depth > 0) { tree[root] = root_val; int bts; bts = exp(2, depth-1) - 1; //Left nodes: P is incremented according to the number of nodes traversed create_bt_loop_dfs(tree, depth_tree, root+1, ++P, depth-1, N); //Right nodes: P should not change create_bt_loop_dfs(tree, depth_tree, root+bts+1, root_val, depth-1, N); } } void create_bt_dfs(int *tree, int root, int root_val, int depth) { if (depth > 0) { tree[root] = ++P; int bts; bts = exp(2, depth-1) - 1; create_bt_dfs(tree, root+1, P, depth-1); create_bt_dfs(tree, root+bts+1, P, depth-1); } } int main() { int t, n, i; scanf("%d", &t); for(t; t > 0; t--) { scanf("%d\t%d\n", &n, &i); // bts = "binary tree size" int bts; // bts = (2^n) - 1 bts = exp(2, n) - 1; // These 2 arrays hold the information needed to print out the odd lines that starts // with "Loop..." and the other one holds the depth of each node int loop_tree[bts]; int depth_tree[bts]; // Starting value of P as instructed by the problem P = 1000; // Recreating the binary tree in an array form create_bt_loop_dfs(loop_tree, depth_tree, 0, P, n, n); //holds the information to print out even lines that start with "Process ID=..." int dfs_tree[bts]; // Again starting value of P as instructed by the problem P = 1000; create_bt_dfs(dfs_tree, 0, P, n); // Annoying hacks to determine whether they want me to print the odd or even lines --i; if ((i%2)==0) printf("Loop %d: Process ID=%d\n", depth_tree[i/2], loop_tree[i/2]); else printf("Process ID=%d, A=%d\n", dfs_tree[(i/2)], ((depth_tree[(i/2)])+1)*7); } return 0; }