staticBigInteger two = BigInteger.valueOf(2), one = BigInteger.ONE, zero = BigInteger.ZERO;
staticBigIntegergcd(BigInteger a, BigInteger b) { while (!(a.mod(b).equals(zero))) { BigInteger t = a.mod(b); a = b; b = t; } return b; }
staticvoidbprint(BigInteger x) { if (x.equals(zero)) return; bprint(x.divide(two)); if (x.mod(two).equals(one)) System.out.print(1); else System.out.print(0); }
public staticvoidmain(String[] args) { Scannerin = newScanner(System.in); int T = in.nextInt(); String a, b; for (int t = 1; t <= T; t++) { a = in.next(); b = in.next(); int la = a.length(), lb = b.length();
BigInteger m = zero, n = zero; for (int i = 0; i < la; ++i) { m = m.multiply(two); if (a.charAt(i) == '1') m = m.add(one); }
for (int i = 0; i < lb; ++i) { n = n.multiply(two); if (b.charAt(i) == '1') n = n.add(one); } System.out.printf("Case #%d: ", t); bprint(gcd(m, n)); System.out.println(); } in.close(); } }
Divided Land
Problem Description
It’s time to fight the local despots and redistribute the land. There is a rectangular piece of land granted from the government, whose length and width are both in binary form. As the mayor, you must segment the land into multiple squares of equal size for the villagers. What are required is there must be no any waste and each single segmented square land has as large area as possible. The width of the segmented square land is also binary. Input
The first line of the input is T (1 ≤ T ≤ 100), which stands for the number of test cases you need to solve. Each case contains two binary number represents the length L and the width W of given land. (0 < L, W ≤ 21000) Output
For each test case, print a line “Case /#t: ”(without quotes, t means the index of the test case) at the beginning. Then one number means the largest width of land that can be divided from input data. And it will be show in binary. Do not have any useless number or space. Sample Input
int main() { int cas, w; scanf("%d", &cas); while(cas--) { printf(solve(w) ? "YES\n" : "NO\n"); if(cas) printf("\n"); } return0; }
Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies.
The figure illustrates a simple mobile. It is just a wire, suspended by a string, with an object on each side. It can also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the lever principle we know that to balance a simple mobile the product of the weight of the objects by their distance to the fulcrum must be equal. That is Wl×Dl = Wr×Drwhere Dl is the left distance, Dr is the right distance, Wl is the left weight and Wr is the right weight.
In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure. In this case it is not so straightforward to check if the mobile is balanced so we need you to write a program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or not.
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input is composed of several lines, each containing 4 integers separated by a single space. The 4 integers represent the distances of each object to the fulcrum and their weights, in the format: Wl Dl Wr Dr
If Wl or Wr is zero then there is a sub-mobile hanging from that end and the following lines define the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of all its objects, disregarding the weight of the wires and strings. If both Wl and Wrare zero then the following lines define two sub-mobiles: first the left then the right one.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Write YES' if the mobile is in equilibrium, write NO’ otherwise.
1 0 2 0 4 0 3 0 1 1 1 1 1 2 4 4 2 1 6 3 2
YES
Before being an ubiquous communications gadget, a mobile was just a structure made of strings and wires suspending colourfull things. This kind of mobile is usually found hanging over cradles of small babies.
The figure illustrates a simple mobile. It is just a wire, suspended by a string, with an object on each side. It can also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the lever principle we know that to balance a simple mobile the product of the weight of the objects by their distance to the fulcrum must be equal. That is Wl×Dl = Wr×Drwhere Dl is the left distance, Dr is the right distance, Wl is the left weight and Wr is the right weight.
In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure. In this case it is not so straightforward to check if the mobile is balanced so we need you to write a program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or not.
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input is composed of several lines, each containing 4 integers separated by a single space. The 4 integers represent the distances of each object to the fulcrum and their weights, in the format: Wl Dl Wr Dr
If Wl or Wr is zero then there is a sub-mobile hanging from that end and the following lines define the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of all its objects, disregarding the weight of the wires and strings. If both Wl and Wrare zero then the following lines define two sub-mobiles: first the left then the right one.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Write YES' if the mobile is in equilibrium, write NO’ otherwise.
#include<cstdio> #include<cstring> using namespace std; int le, ri; const int M = 205; int a[M];
voidbuild(int p) { int t; scanf("%d", &t); if(t == -1) return; else { a[p] += t; build(p - 1); build(p + 1); le = le < p ? le : p; ri = ri > p ? ri : p; } }
int main() { int cas = 0; le = M, ri = 0; build(M / 2);
while(le <= ri) { printf("Case %d:\n", ++cas); for(int i = le; i < ri; ++i) printf("%d ", a[i]); printf("%d\n\n", a[ri]);
memset(a, 0, sizeof(a)); le = M, ri = 0; build(M / 2); } return0; }
Each year, fall in the North Central region is accompanied by the brilliant colors of the leaves on the trees, followed quickly by the falling leaves accumulating under the trees. If the same thing happened to binary trees, how large would the piles of leaves become?
We assume each node in a binary tree “drops” a number of leaves equal to the integer value stored in that node. We also assume that these leaves drop vertically to the ground (thankfully, there’s no wind to blow them around). Finally, we assume that the nodes are positioned horizontally in such a manner that the left and right children of a node are exactly one unit to the left and one unit to the right, respectively, of their parent. Consider the following tree:
The nodes containing 5 and 6 have the same horizontal position (with different vertical positions, of course). The node containing 7 is one unit to the left of those containing 5 and 6, and the node containing 3 is one unit to their right. When the “leaves” drop from these nodes, three piles are created: the leftmost one contains 7 leaves (from the leftmost node), the next contains 11 (from the nodes containing 5 and 6), and the rightmost pile contains 3. (While it is true that only leaf nodes in a tree would logically have leaves, we ignore that in this problem.)
The input contains multiple test cases, each describing a single tree. A tree is specified by giving the value in the root node, followed by the description of the left subtree, and then the description of the right subtree. If a subtree is empty, the value -1 is supplied. Thus the tree shown above is specified as 5 7 -1 6 -1 -1 3 -1 -1 . Each actual tree node contains a positive, non-zero value. The last test case is followed by a single -1 (which would otherwise represent an empty tree).
For each test case, display the case number (they are numbered sequentially, starting with 1) on a line by itself. On the next line display the number of “leaves” in each pile, from left to right, with a single space separating each value. This display must start in column 1, and will not exceed the width of an 80-character line. Follow the output for each case by a blank line. This format is illustrated in the examples below.
You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.
The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.
For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.
You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.
The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.
For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.
Trees are fundamental in many branches of computer science. Current state-of-the art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics.
This problem involves building and traversing binary trees.
The Problem
Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes.
In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k+1.
For example, a level order traversal of the tree
is: 5, 4, 8, 11, 13, 4, 7, 2, 1.
In this problem a binary tree is specified by a sequence of pairs (n,s) where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of L‘s and R‘s where L indicates a left branch and R indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once.
The Input
The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs (n,s) as described above separated by whitespace. The last entry in each tree is (). No whitespace appears between left and right parentheses.
All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file.
The Output
For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete’’ should be printed.
#include<cstdio> #include<cstring> using namespace std; const int N=100005; char s[N]; int next[N]; int main() { int last,cur; while(~scanf("%s",s+1)) { next[0]=last=cur=0; int length=strlen(s+1); for(int i=1;i<=length;++i) { if(s[i]=='[') cur=0; elseif(s[i]==']') cur=last; else { next[i]=next[cur]; next[cur]=i; if(cur==last) last=i; cur=i; } } for(int i=next[0];i;i=next[i]) printf("%c",s[i]); printf("\n"); } return0; }
Broken Keyboard
You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally).
You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).
In Chinese, we can call it Beiju. Your task is to find the Beiju text.
Input
There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[‘ and ‘]’. ‘[‘ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.
Output
For each case, print the Beiju text on the screen.
#include<cstdio> #include<cctype> #include<cstring> using namespace std; const int N = 1000; int st[N], row[N], col[N], r[N], c[N];
int main() { int n, ans, top; scanf("%d", &n); char na[3], s[N]; for(int i = 1; i <= n; ++i) { scanf("%s", na); int j = na[0] - 'A'; scanf("%d%d", &row[j], &col[j]); }
while(~scanf("%s", &s)) { int i; for(i = 0 ; i < 26; ++i) c[i] = col[i], r[i] = row[i]; ans = top = 0;
Suppose you have to evaluate an expression like A/*B/*C/*D/*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.
For example, let A be a 50/*10 matrix, B a 10/*20 matrix and C a 20/*5 matrix. There are two different strategies to compute A/*B/*C, namely (A/*B)/C and A/(B/*C).
The first one takes 15000 elementary multiplications, but the second one only 3500.
Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.
Input Specification
Input consists of two parts: a list of matrices and a list of expressions.
The first line of the input file contains one integer n ( ), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.
The second part of the input file strictly adheres to the following syntax (given in EBNF):
For each expression found in the second part of the input file, print one line containing the word “error” if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.
Sample Input
9 A 50 10 B 10 20 C 20 5 D 30 35 E 35 15 F 15 5 G 5 10 H 10 20 I 20 25 A B C (AA) (AB) (AC) (A(BC)) ((AB)C) (((((DE)F)G)H)I) (D(E(F(G(HI))))) ((D(EF))((GH)I))
#include<cstdio> #include<cstring> using namespace std; const int N = 2000; int b[N], c[N]; int main() { int l, cur, top; while(scanf("%d", &l), l) { while(scanf("%d", &b[1]), b[1]) { for(int i = 2; i <= l; ++i) scanf("%d", &b[i]); cur = 1, top = 0; for(int i = 1; i <= l; ++i) { if(i == b[cur]) cur++; else c[++top] = i; while(top && b[cur] == c[top]) { ++cur; --top; } } printf("%s\n", top ? "No" : "Yes"); } printf("\n"); } return0; }
There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.
The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has coaches numbered in increasing order . The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be . Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.
The input file consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of The last line of the block contains just 0.
The last block consists of just one line containing 0.
The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains No . In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last ``null’’ block of the input file.
#include<cstdio> #include<cstring> using namespace std; const int maxs = 50 * 50 * 50 * 50 * 4 + 10; unsigned short cnt[maxs]; int main() { int a1, a2, a3, a4, a5, sum,ans=0; scanf ("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5); for (int x1 = -50; x1 <= 50; ++x1) { if (x1 == 0) ++x1; for (int x2 = -50; x2 <= 50; ++x2) { if (x2 == 0) ++x2; sum = (a1 * x1 * x1 * x1 + a2 * x2 * x2 * x2) * (-1); if (sum < 0) ++cnt[sum + maxs]; else ++cnt[sum]; } }
for (int x3 = -50; x3 <= 50; ++x3) { if (x3 == 0) ++x3; for (int x4 = -50; x4 <= 50; ++x4) { if (x4 == 0) ++x4; for (int x5 = -50; x5 <= 50; ++x5) { if (x5 == 0) ++x5; sum = (a3 * x3 * x3 * x3 + a4 * x4 * x4 * x4 + a5 * x5 * x5 * x5) ; if (sum < 0) sum += maxs; ans += cnt[sum]; } } } printf ("%d\n", ans); return0; }
Eqs
Description Consider equations having the following form: a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 The coefficients are given integers from the interval [-50,50]. It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}. Determine how many solutions satisfy the given equation.
Input
The only line of input contains the 5 coefficients a1, a2, a3, a4, a5, separated by blanks.
Output
The output will contain on the first line the number of the solutions for the given equation.
#include<iostream> #include<cstdio> #include<cstring> #include<hash_map> using namespace std; int first[50*50*50+10]; int ecnt,w[10005],v[10005],nex[10005];
#include<cstdio> #include<cstring> using namespace std; const int N = 100010; int s[N], vis[N];
int main() { int n, c, i, j; while (~scanf ("%d%d", &c, &n), c) { memset (vis, 0, sizeof (vis)); vis[0] = 1; for (i = 1; i <= n; ++i) { scanf ("%d", &s[i]); s[i] = (s[i] + s[i - 1]) % c; }
for (i = 1; i <= n; ++i) { if (vis[s[i]]) break; else vis[s[i]] = i+1; }
Description Every year there is the same problem at Halloween: Each neighbour is only willing to give a certain total number of sweets on that day, no matter how many children call on him, so it may happen that a child will get nothing if it is too late. To avoid conflicts, the children have decided they will put all sweets together and then divide them evenly among themselves. From last year’s experience of Halloween they know how many sweets they get from each neighbour. Since they care more about justice than about the number of sweets they get, they want to select a subset of the neighbours to visit, so that in sharing every child receives the same number of sweets. They will not be satisfied if they have any sweets left which cannot be divided.
Your job is to help the children and present a solution.
Input
The input contains several test cases. The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000), the number of children and the number of neighbours, respectively. The next line contains nspace separated integers *a1 , … , *a**n** (1 ≤ ai ≤ 100000), where ai** represents the number of sweets the children get if they visit neighbour i.
The last test case is followed by two zeros.
Output
For each test case output one line with the indices of the neighbours the children should select (here, index i corresponds to neighbour i who gives a total number of ai sweets). If there is no solution where each child gets at least one sweet print “no sweets” instead. Note that if there are several solutions where each child gets at least one sweet, you may print any of them.
), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.
coaches numbered in increasing order 
. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be 
. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.