Fork() Makes Trouble

From Progteam

Revision as of 22:40, 15 March 2009 by Jinho (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by jinho.



Fork() Makes Trouble
Problem Number 1680
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;
}

Personal tools