We would like to place n rooks, 1 ≤ n ≤ 5000, on a n×n board subject to the following restrictions
The input consists of several test cases. The first line of each of them contains one integer number, n, the side of the board. n lines follow giving the rectangles where the rooks can be placed as described above. The i-th line among them givesxli, yli, xri, and yri. The input file is terminated with the integer `0’ on a line by itself.
Your task is to find such a placing of rooks that the above conditions are satisfied and then outputn lines each giving the position of a rook in order in which their rectangles appeared in the input. If there are multiple solutions, any one will do. Output IMPOSSIBLE if there is no such placing of the rooks.
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
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 first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.
This is an example of one of her creations:
D / \ / \ B E / \ \ / \ \ A C G / / F
To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree).
For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).
Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.
However, doing the reconstruction by hand, soon turned out to be tedious.
So now she asks you to write a program that does the job for her!
The input file will contain one or more test cases. Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)
Input is terminated by end of file.
For each test case, recover Valentine’s binary tree and print one line containing the tree’s postorder traversal (left subtree, right subtree, root).
#include <bits/stdc++.h> using namespace std; int x[] = { -2, -1, -2, -1, 1, 2, 1, 2}; int y[] = { -1, -2, 1, 2, -2, -1, 2, 1}; int d[15][15], sx, sy, ex, ey; pair<int, int> q[105], t;
int bfs() { int cx, cy, r, c, front = 0, rear = 0; memset(d, -1, sizeof(d)); d[sx][sy] = 0; q[rear++] = make_pair(sx, sy); while(front < rear) { t = q[front++]; cx = t.first, cy = t.second; if(cx == ex && cy == ey) return d[cx][cy]; for(int i = 0; i < 8; ++i) { r = cx + x[i], c = cy + y[i]; if(r < 0 || r > 7 || c < 0 || c > 7 || d[r][c] >= 0) continue; d[r][c] = d[cx][cy] + 1; q[rear++] = make_pair(r, c); } } }
int main() { char a[5], b[5]; while(~scanf("%s%s", a, b)) { sx = a[0] - 'a', sy = a[1] - '1'; ex = b[0] - 'a', ey = b[1] - '1'; printf("To get from %s to %s takes %d knight moves.\n", a, b, bfs()); } return0; }
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the “difficult” part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input Specification
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output Specification
For each test case, print one line saying “To get from xx to yy takes n knight moves.”.
Sample Input
e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.
You are given a string consisting of parentheses () and []. A string of this type is said to becorrect: (a) if it is the empty string (b) if A and B are correct, AB is correct, (c) if A is correct, (A ) and [A ] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
The file contains a positive integer n and a sequence of n strings of parentheses () and [] , one string a line.
int main() { int a, b, i; while(~scanf("%d %d", &n, &m), n) { memset(g, 0, sizeof(g)); memset(v, 0, sizeof(v)); while(m--) { scanf("%d%d", &a, &b); g[a][b] = 1; }
t = 0; for(i = 1; i <= n; ++i) if(!v[i]) dfs(i); for(i = 1; i < n; ++i) printf("%d ", tpo[i]); printf("%d\n", tpo[n]); } return0; }
John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.
Input
The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 <= n <= 100 andm. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0will finish the input.
memset(p, 0, sizeof(p)); memset(var, 0, sizeof(var)); while(!qr.empty()) { int cur = qr.front(); qr.pop_front(); run(cur); } if(cas) puts(""); } return0; }
Programs executed concurrently on a uniprocessor system appear to be executed at the same time, but in reality the single CPU alternates between the programs, executing some number of instructions from each program before switching to the next. You are to simulate the concurrent execution of up to ten programs on such a system and determine the output that they will produce.
The program that is currently being executed is said to be running, while all programs awaiting execution are said to be ready. A program consists of a sequence of no more than 25 statements, one per line, followed by an end statement. The statements available are listed below.
Each statement requires an integral number of time units to execute. The running program is permitted to continue executing instructions for a period of time called its quantum. When a program�s time quantum expires, another ready program will be selected to run. Any instruction currently being executed when the time quantum expires will be allowed to complete.
Programs are queued first-in-first-out for execution in a ready queue. The initial order of the ready queue corresponds to the original order of the programs in the input file. This order can change, however, as a result of the execution of lock and unlock statements.
The lock and unlock statements are used whenever a program wishes to claim mutually exclusive access to the variables it is manipulating. These statements always occur in pairs, bracketing one or more other statements. A lock will always precede an unlock, and these statements will never be nested. Once a program successfully executes a lock statement, no other program may successfully execute a lock statement until the locking program runs and executes the corresponding unlockstatement. Should a running program attempt to execute a lock while one is already in effect, this program will be placed at the end of the blocked queue. Programs blocked in this fashion lose any of their current time quantum remaining. When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue. The first statement this program will execute when it runs will be the lock statement that previously failed. Note that it is up to the programs involved to enforce the mutual exclusion protocol through correct usage of lock andunlock statements. (A renegade program with no lock/unlock pair could alter any variables it wished, despite the proper use of lock/unlock by the other programs.)
Input
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 first line of the input file consists of seven integers separated by spaces. These integers specify (in order): the number of programs which follow, the unit execution times for each of the five statements (in the order given above), and the number of time units comprising the time quantum. The remainder of the input consists of the programs, which are correctly formed from statements according to the rules described above.
All program statements begin in the first column of a line. Blanks appearing in a statement should be ignored. Associated with each program is an identification number based upon its location in the input data (the first program has ID = 1, the second has ID = 2, etc.).
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Your output will contain of the output generated by the print statements as they occur during the simulation. When a print statement is executed, your program should display the program ID, a colon, a space, and the value of the selected variable. Output from separate print statements should appear on separate lines.
A sample input and correct output are shown below.
Sample Input
1 3 1 1 1 1 1 1 a = 4 print a lock b = 9 print b unlock print b end a = 3 print a lock b = 8 print b unlock print b end b = 5 a = 17 print a print b lock b = 21 print b unlock print b end
In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.
Each dictionary is formatting as follows:
{key:value,key:value,…,key:value}
Each key is a string of lower-case letters, and each value is a non-negative integer without leading zeros or prefix `+’. (i.e. -4, 03 and +77 are illegal). Each key will appear at most once, but keys can appear in any order.
The first line contains the number of test cases T ( T1000 ). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.
WARNING: there are no restrictions on the lengths of each key and value in the dictionary. That means keys could be really long and values could be really large.
For each test case, print the changes, formatted as follows:
If the two dictionaries are identical, print `No changes’ (without quotes) instead.
The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along a vertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on the right is not left-right symmetric as it is impossible to find such a vertical line.
Write a program that determines whether a figure, drawn with dots, is left-right symmetric or not. The dots are all distinct.
The input consists of T test cases. The number of test cases T is given in the first line of the input file. The first line of each test case contains an integer N , where N ( 1N1, 000) is the number of dots in a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Both x-coordinates and y-coordinates are integers between -10,000 and 10,000, both inclusive.
Print exactly one line for each test case. The line should contain YES' if the figure is left-right symmetric. and NO’, otherwise.
The following shows sample input and output for three test cases.
We would like to place n rooks, 1 ≤ n ≤ 5000, on a n×n board subject to the following restrictions
A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
1000 ). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.
N