{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"A Strange Tree (S-tree) over the variable set Xn\u003d{ x1;x2;:::;xn } is a binary tree representing a Boolean function f:f0;1gn!f0;1g. Each path of the S-tree begins at the root node and consists of n+ 1 nodes. Each of the S-tree’s nodes has adepth, which is the amount of nodes between itself and the root (so the root has depth 0). The nodes with depth less than n are called non-terminal nodes. All non-terminal nodes have two children: the right child and the left child. Each non-terminal node is marked with some variable xi from the variable set Xn. All non-terminal nodes with the same depth are marked with the same variable, and non-terminal nodes with different depth are marked with different variables. So, there is a unique variable xi1 corresponding to the root, a unique variable xi2 corresponding to the nodes with depth 1, and so on. The sequence of the variables xi1,xi2,:::,xin is called the variable ordering. The nodes having depth n are called terminal nodes. They have no children and are marked with either 0 or 1. Note that the variable ordering and the distribution of 0’s and 1’s on terminal nodes are sufficient to completely describe an S-tree.\n\nAs stated earlier, each S-tree represents a Boolean functionf. If you have an S-tree and values for the variables x1,x2,:::,xn, then it is quite simple to find out what f(x1;x2;:::;xn) is: start with the root. Now repeat the following: if the node you are at is labelled with a variable xi, then depending on whether the value of the variable is 1 or 0, you go its right or left child, respectively. Once you reach a terminal node, its label gives the value of the function.\n\nFigure 1: S-trees for the function x1^(x2_x3)\n\nOn the picture, two S-trees representing the same Boolean function,f(x1;x2;x3) \u003dx1^(x2_x3),are shown. For the left tree, the variable ordering is x1;x2;x3, and for the right tree it is x3;x1;x2.The values of the variables x1,x2,:::,xn, are given as aVariable Values Assignment(VVA)\n\n(x1\u003db1;x2\u003db2;:::;xn\u003dbn)\n\nwith b1;b2;:::;bn\u003d {0;1}. For instance, (x1\u003d 1,x2\u003d 1,x3\u003d 0) would be a valid VVA for n\u003d 3,resulting for the sample function above in the value f(1;1;0) \u003d 1^(1_0) \u003d 1. The corresponding paths are shown bold in the picture.Your task is to write a program which takes an S-tree and some VVAs and computesf(x1;x2;:::;xn)as described above.\n\nInput\n\nThe input file contains the description of several S-trees with associated VVAs which you have to process. Each description begins with a line containing a single integer n,1\u003c\u003dn\u003c\u003d7, the depth of the S-tree. This is followed by a line describing the variable ordering of the S-tree. The format of that line is xi1xi2:::xin. (There will be exactly n different space-separated strings). So, for n\u003d 3 and the variable ordering x3,x1,x2, this line would look as follows:x3 x1 x2\n\nIn the next line the distribution of 0’s and1’s over the terminal nodes is given. There will be exactly 2n characters (each of which can be ‘0’ or ‘1’), followed by the new-line character. The characters are given in the order in which they appear in the S-tree, the first character corresponds to the leftmost terminal node of the S-tree, the last one to its rightmost terminal node.The next line contains a single integer m, the number of VVAs, followed by m lines describing them. Each of the m lines contains exactly n characters (each of which can be ‘0’ or ‘1’), followedby a new-line character. Regardless of the variable ordering of the S-tree, the first character always describes the value of x1, the second character describes the value of x2, and so on. So, the line 110 corresponds to the VVA (x1\u003d 1,x2\u003d 1,x3\u003d 0).The input is terminated by a test case starting with n\u003d 0. This test case should not be processed.\n\nOutput\n\nFor each S-tree, output the line ‘S-Tree #j:’, wherejis the number of the S-tree. Then print a line that contains the value of f(x1;x2;:::;xn)for each of the given m VVAs, where f is the functiondefined by the S-tree.Output a blank line after each test case.\n\nSample Input\n\n3\nx1 x2 x3\n00000111\n4\n000\n010\n111\n110\n3\nx3 x1 x2\n00010011\n4\n000\n010\n111\n110\n0\n\nSample Output\n\nS-Tree #1:\n0011\nS-Tree #2:\n0011\n\n"}},{"title":"","value":{"format":"PLAIN","content":"变量集Xn\u003d{ x1;x2;::;xn }上的奇树(S-tree)是表示布尔函数f:f0;1gn!f0;1g的二元树。S树的每条路径从根节点开始,由n+1个节点组成。S树的每个节点都有深度,深度是指自身与根节点之间的节点数量(所以根节点的深度为0)。深度小于n的节点称为非终端节点。所有非终端节点都有两个子节点:右子节点和左子节点。每个非终端节点都用变量集Xn中的某个变量xi来标记。所有深度相同的非终端节点都用同一个变量标记,深度不同的非终端节点用不同的变量标记。所以,有一个唯一的变量xi1对应根,有一个唯一的变量xi2对应深度为1的节点,以此类推。变量xi1,xi2,::,xin的序列称为变量排序。具有深度n的节点称为终端节点。它们没有子节点,用0或1标记。请注意,变量排序和终端节点上0和1的分布足以完全描述一棵S树。\n\n如前所述,每个S树代表一个布尔函数f。如果你有一个S树和变量x1,x2,::,xn的值,那么要找出f(x1;x2;::;xn)是什么很简单:从根开始。现在重复以下步骤:如果你所在的节点上标有一个变量xi,那么根据变量的值是1还是0,你分别走它的右边或左边子节点。一旦你到达一个终端节点,它的标签就会给出函数的值。\n\n图1:函数x1^(x2_x3)的S树。\n\n如图所示,是表示同一个布尔函数f(x1;x2;x3)\u003dx1^(x2_x3)的两棵S树,左边树的变量排序是x1;x2;x3,右边树的变量排序是x3;x1;x2。左边树的变量排序为x1;x2;x3,右边树的变量排序为x3;x1;x2.变量x1,x2,::,xn的值为变量值分配(VVA)。\n\n(x1\u003db1;x2\u003db2;:::;xn\u003dbn)\n\n与b1;b2;::;bn\u003d {0;1}。例如,(x1\u003d 1,x2\u003d 1,x3\u003d 0)将是一个有效的VVA,对于n\u003d 3,导致上面的示例函数的值f(1;1;0)\u003d 1^(1_0) \u003d 1。你的任务是写一个程序,将一个S树和一些VVAs,并计算f(x1;x2;::;xn),如上所述。\n\n输入内容\n\n输入文件包含了几个S树的描述,以及相关的VVA,你必须处理这些S树。每个描述都以一行开始,包含一个整数n,1\u003c\u003dn\u003c\u003d7,即S树的深度。之后是一行描述S树的变量排序的行。该行的格式是xi1xi2::xin。(正好会有n个不同的空间分隔的字符串)。所以,对于n\u003d3,变量排序为x3,x1,x2,这一行的格式如下:x3 x1 x2。\n\n在下一行中,给出了0和1在终端节点上的分布。恰好有2n个字符(每个字符可以是\u00270\u0027或\u00271\u0027),然后是新行字符。这些字符是按照它们在S树中出现的顺序给出的,第一个字符对应于S树最左边的终端节点,最后一个字符对应于它最右边的终端节点.下一行包含一个单整数m,即VVA的数量,然后是描述它们的m行。每一行都包含n个字符(每个字符可以是\u00270\u0027或\u00271\u0027),然后是一个新行字符。无论S树的变量排序如何,第一个字符总是描述x1的值,第二个字符描述x2的值,以此类推。因此,第110行对应于VVA(x1\u003d 1,x2\u003d 1,x3\u003d 0).输入以n\u003d 0开始的测试用例结束,这个测试用例不应该被处理。\n\n輸出\n\n对于每一个S树,输出一行 \"S树#j:\",其中j是S树的编号。然后打印一行包含给定的m个VVA的f(x1;x2;::;xn)的值,其中f是由S树定义的函数。\n\n输入示例\n\n3\nx1 x2 x3\n00000111\n4\n000\n010\n111\n110\n3\nx3 x1 x2\n00010011\n4\n000\n010\n111\n110\n0\n\n采样输出\n\nS-Tree #1:\n0011\nS-Tree #2:\n0011\n\n"}}]}