# Fork() Makes Trouble

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by jinho.

 Sorter: Uncategorized Unknown 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;
}

```