.:: Bots United ::. - Programming quiz

Here is a small programming quiz.... Sorry but my English is poor. I don't know those "professional" words.

Of course, If you can give me the answers of these problems that's great. But that's not wanted to because these problems are not very easy.....

PROBLEM 1: NEURAL NETWORKS

BACKGROUND

Artifical Neural Network (NN) is a new and developing trainable computing system. It's widely used in many fields. Lan-Lan, who has just taught herself some basics on NN, brought forward a simplified model. She hopes you can help her checking the practicability of her model with programming.

PROBLEM DESCRIPTION

In Lan-Lan's model, NN is a directed graph. The nodes in the graph is called 'neuron'. There's at most one edge between two nodes. Here is a sample of a neuron:

x1--------> T-----I----T ------>Y1
x2--------> | C(i) |U(i)|
x3--------> L_____I___| ------>Y2

Figure 1. neuron (No. i)

x1 - x3 are input channels for information. y1, y2 are output channels. C(i) stands for the current state of the neuron. U(i) is the threshold value, which can be treated as a internal parameter of the neuron.

The neurons are arranged in a certain order and make up of the entire NN. In Lan Lan's model, the neurons in the NN are divided into several layers, which is called 'input layer', 'output layer', and several 'middle layer's. Each layer only passes information to the next layer and receives information from the previous layer. Here is a simple 3-layer NN:

[Edited: Those '*' s are nothing. change them to spaces.]
[Is this a bug of this forum? it just don't let me type more than 1 space.]

****I--->(3)---I
*(1)-I********I-->(6)
****I--->(4)---I
*(2)-I********I-->(7)
****I--->(5)---I

Figure 2. A simple NN

Lan-Lan supposes, C(i) agrees to formula:

****----I
C(i) = \ W(j, i) * C(j) - U(i)
****/
****----I
[ (j, i) belongs to E ]

W(j, i) (may be negative) stands for the weight of the edge which connects neuron No. j and No. i. When C(i)>0, this neuron is in the condition of being excited. Otherwise it's in thhe condition of being calm. When a neuron is in the condition of being excited, it will pass a signal to other neurons in the next second. The strength of this signal is C(i).

Like this, after the neurons in the input layer are activated, the entire NN is running thanks to information transmiting. Now, give an NN and the conditions of the neurons in the input layer C(i), your program should output the conditions of the neurons in the output layer.

INPUT FORMAT

The first line of the input file are 2 integers n (1 <= n <= 20) and p. Next n lines, 2 integers per line, the (i + 1)th line is the initial condition of neuron No.i and its threshold value. The conditions of the neurons in the layers other than the input layer must be zero. Next p lines, each line has 2 integers i, j and 1 integer W(i,j), which stand for the weight of the edge which connects neuron i and j is W(i,j).

OUTPUT FORMAT

Output file contains several lines, each line has 2 integers, stands for one number of a neuron, and its final condition. 2 integers are separated by a space. ONLY OUTPUT THE CONDITIONS OF neuronS WHOSE FINAL CONDITION IS NON-ZERO, AND IN A ASCENDING ORDER!

INPUT SAMPLE

5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1

OUTPUT SAMPLE

3 1
4 1
5 1

----------------------------------------------------------------------------------

PROBLEM 2: DETECTIVE

PROBLEM DESCRIPTION

Ming-Ming is entranced with detective storybook "Holmes" and logic games. He gathered some classmates to play logic games. The rules of the game are, one of his classmates pretends to be the criminal (of course, Ming-Ming doesn't know who is it), Ming-Ming's task is to find out this criminal. Then, Ming-Ming asks each of his classmates, each of them may say:

I am guilty.
I am not guilty.
**** is guilty.
**** is not guilty.
Today is ****. (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday)

Other words are supposed to be ignored.
What Ming-Ming knows is, there are always N persons are lying. Other persons always tell truth.
Now, Ming-Ming wants you to help him find out who is the criminal. Please keep in mind, THERE IS ONLY ONE CRIMINAL!!!

INPUT FORMAT

Input file is made up of several lines. The first line has 3 integers M(1 <= M <= 20), N(1 <= N <= M), and P(1 <= P <= 100). M is the number of Ming-Ming's classmates who take part in the game, N is the number of persons who are always lying, P is the number of testimonys. Next M lines, each line is a name of one of Ming-Ming's classmate (in capital letters, without spaces). Next P lines are testimonys. The beginning of each line here is a name, followed by a colon and a space, then is the testimony. The length of the lines here won't exceed 250 characters.

OUTPUT FORMAT

Output the name of the criminal. If there are not only one criminals, output "Cannot determine". If there are no possible criminals, output "Impossible".

INPUT SAMPLE

3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??

OUTPUT SAMPLE

MIKE

-----------------------------------------------------------------------------------
PROBLEM 3. BINARY TREE

PROBLEM DESCRIPTION

The in-order traversal of a binary tree with n nodes is (1,2,3,.....n). Where the number 1,2,3,.....n are the number of the nodes. Each node has a mark (positive integer). Let the mark of Node No. j be d(j), the tree and its each subtree has a mark, the mark of any subtree (including tree itself) is:

d(subtree's left subtree) * d(subtree's right subtree) + d(subtree's root)

If one of the subtrees is empty, let its mark to be 1. The mark of a leaf is its own mark. Do not consider its empty subtree.

Now you are wanted to find out a binary tree whose mark is the greatest.

INPUT FORMAT

1st line: a integer n(n<30). The number of nodes.
2nd line: n integers separated by spaces. Mark of each nodes (<100).

OUTPUT FORMAT

1st line: a integer, the greatest mark of the tree.
2nd line: n integers separated by spaces. The pre-order traversal of this tree.

INPUT SAMPLE

5
5 7 1 2 10

OUTPUT SAMPLE

145
3 1 2 4 5