Description Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:
Certainly, we would like to minimize the number of all possible operations. Illustration
A G T A A G T /* A G G C | | | | | | | A G T /* C /* T G A C G C
Deletion: /* in the bottom line Insertion: /* in the top line Change: when the letters at the top and bottom are distinct
This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like
A G T A A G T A G G C | | | | | | | A G T C T G /* A C G C
and 4 moves would be required (3 changes and 1 deletion).
In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≥ m.
Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.
Write a program that would minimize the number of possible operations to transform any string x into a string y.
Input
The input consists of the strings x and y prefixed by their respective lengths, which are within 1000.
Output
An integer representing the minimum number of possible operations to transform any string x into a string y.
Description Linda is a teacher in ACM kindergarten. She is in charge of n kids. Because the dinning hall is a little bit far away from the classroom, those n kids have to walk in line to the dinning hall every day. When they are walking in line, if and only if two kids can see each other, they will talk to each other. Two kids can see each other if and only if all kids between them are shorter then both of them, or there are no kids between them. Kids do not only look forward, they may look back and talk to kids behind them. Linda don’t want them to talk too much (for it’s not safe), but she also don’t want them to be too quiet(for it’s boring), so Linda decides that she must form a line in which there are exactly m pairs of kids who can see each other. Linda wants to know, in how many different ways can she form such a line. Can you help her? Note: All kids are different in height.
Input
Input consists of multiple test cases. Each test case is one line containing two integers. The first integer is n, and the second one is m. (0 < n <= 80, 0 <= m <= 10000). Input ends by a line containing two zeros.
Output
For each test case, output one line containing the reminder of the number of ways divided by 9937.
Description Any positive integer v can be written as p1a1/p2a2/…/*pnan where pi is a prime number and ai ≥ 0. For example: 24 = 23/*31. Pick any two prime numbers p1 and p2 where p1 = p2. Imagine a two dimensional plane where the powers of p1 are plotted on the x-axis and the powers of p2 on the y-axis. Now any number that can be written as p1a1/*p2a2 can be plotted on this plane at location (x, y) = (a1, a2). The figure on the right shows few examples where p1 = 3 and p2 = 2. This idea can be extended for any N-Dimensional space where each of the N axes is assigned a unique prime number. Each N-Dimensional space has a unique set of primes. We call such set the Space Identification Set or S for short. |S| (the ordinal of S) is N. Any number that can be expressed as a multiplication of pi ∈ S (each raised to a power (ai ≥ 0) can be plotted in this |S|-Dimensional space. The figure at the bottom illustrates this idea for N = 3 and S = {2, 3, 7}. Needless to say, any number that can be plotted on space A can also be plotted on space B as long as SA SB. We define the distance between any two points in a given N-Dimensional space to be the sum of units traveled to get from one point to the other while following the grid lines (i.e. movement is always parallel to one of the axes.) For example, in the figure below, the distance between 168 and 882 is 4. Given two positive integers, write a program that determines the minimum ordinal of a space where both numbers can be plotted in. The program also determines the distance between these two integers in that space.
Input
Your program will be tested on one or more test cases. Each test case is specified on a line with two positive integers (0 < A,B < 1, 000, 000) where A /* B > 1. The last line is made of two zeros.
Output
For each test case, print the following line: k. X:D Where k is the test case number (starting at one,) X is the minimum ordinal needed in a space that both A and B can be plotted in. D is the distance between these two points.
#include<cstdio> #include<cmath> #include<cstring> using namespace std; typedef long long ll; const int N = 1000001; int p[N], ans[N], vis[N], a, b; voidinitPrime() { int num = 0, m = sqrt (N + 0.5); for (int i = 2; i <= m; ++i) if (vis[i] == 0) for (int j = i * i; j <= N; j += i) vis[j] = 1; for (int i = 2; i <= N; ++i) if (vis[i] == 0) p[++num] = i; }
int main() { initPrime(); int cas=0; while (scanf ("%d%d", &a, &b),a) { int cnt = 0, ans = 0, ca, cb; for (int i = 1; a > 1 || b > 1; ++i) if (a % p[i] == 0 || b % p[i] == 0) { ++cnt, ca = cb = 0; while (a % p[i] == 0) a /= p[i], ++ca; while (b % p[i] == 0) b /= p[i], ++cb; ans += (ca > cb ? ca - cb : cb - ca); } printf ("%d. %d:%d\n", ++cas,cnt, ans); } return0; }
Description The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated. As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers. A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC. Given a set of DNA base sequences, determine the longest series of bases that occurs in all of the sequences.
Input
Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each dataset consists of the following components:
Output
For each dataset in the input, output the longest base subsequence common to all of the given base sequences. If the longest common subsequence is less than three bases in length, display the string “no significant commonalities” instead. If multiple subsequences of the same longest length exist, output only the subsequence that comes first in alphabetical order.
A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf nodes of FBT. To determine a ball’s moving direction a flag is set up in every non-terminal node with two values, either false or true. Initially, all of the flags are false. When visiting a non-terminal node if the flag’s current value at this node isfalse, then the ball will first switch this flag’s value, i.e., from the false to the true, and then follow the left subtree of this node to keep moving down. Otherwise, it will also switch this flag’s value, i.e., from the true to the false, but will follow the right subtree of this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at 1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered from left to right.
For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1, 2, 3, …, 15. Since all of the flags are initially set to be false, the first ball being dropped will switch flag’s values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being dropped will switch flag’s values at node 1, node 3, and node 6, and stop at position 12. Obviously, the third ball being dropped will switch flag’s values at node 1, node 2, and node 5 before it stops at position 10.
Fig. 1: An example of FBT with the maximum depth 4 and sequential node numbers.
Now consider a number of test cases where two values will be given for each test. The first value is D, the maximum depth of FBT, and the second one is I, the I**th ball being dropped. You may assume the value of I will not exceed the total number of leaf nodes for the given FBT.
Please write a program to determine the stop position P for each test case.
For each test cases the range of two parameters D and I is as below:
Contains l +2 lines. Line 1 I the number of test cases Line 2 test case /#1, two decimal numbers that are separatedby one blank … Line k+1 test case /#k Line l+1 test case /#l Line l+2 -1 a constant -1 representing the end of the input file
Contains l lines. Line 1 the stop position P for the test case /#1 … Line k the stop position P for the test case /#k … Line l the stop position P for the test case /#l
#include<cstdio> int main() { int cas, ans, d, i; while (scanf ("%d", &cas), cas + 1) { while (cas--) { ans = 1; scanf ("%d%d", &d, &i); while (--d) { if (i % 2) ans = ans * 2, i = (i + 1) / 2; else ans = ans * 2 + 1, i = i / 2; } printf ("%d\n", ans); } } return0; }
int main() { int cas = 0, op, x, y, t; while (scanf ("%d%d", &n, &m) != EOF) { for (int i = 1; i <= n; ++i) ri[i] = i + 1, le[i] = i - 1; ri[n] = 0, le[0] = n, ri[0] = 1; int flag = 0; //判断是否翻转 while (m--) { scanf ("%d", &op); if (op == 4) flag = !flag; else { scanf ("%d%d", &x, &y); if (flag && op != 3) op = 3 - op; //翻转后移动操作就相反了 if (ri[y] == x && op == 3) //方便后面判断交换是否相邻 t = x, x = y, y = t; if ( (op == 1 && le[y] == x) || (op == 2 && ri[y] == x)) continue;
if (op == 1) //x移到y右边 link (le[x], ri[x]), link (le[y], x), link (x, y); elseif (op == 2) //x移到y左边 link (le[x], ri[x]), link (x, ri[y]), link (y, x); elseif (y == ri[x]) //op==3&&x,y相邻 link (le[x], y), link (x, ri[y]), link (y, x); else//不相邻 { int ry = ri[y], ly = le[y]; link (le[x], y), link (y, ri[x]), link (ly, x), link (x, ry); } } }
t = 0; ll ans = 0; for (int i = 1; i <= n; ++i) { t = ri[t]; if (i % 2) ans += t; } if (n % 2 == 0 && flag) //n为偶数且翻转过 故求的恰为偶数位的和 ans = (ll) n / 2 * (1 + n) - ans; printf ("Case %d: %lld\n", ++cas, ans); } return0; }
Boxes in a Line
You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands: • 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y ) • 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y ) • 3 X Y : swap box X and Y • 4: reverse the whole line. Commands are guaranteed to be valid, i.e. X will be not equal to Y . For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2
Input
There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.
Output
For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000). Output
For each test case, you should output two lines. The first line is “Case /#:”, /# means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases. Sample Input
#include<cstdio> #include<cstring> using namespace std; const int N = 100005; int main() { int a, cas, ans, l, le, ri, n, d[N]; scanf ("%d", &cas); for (int k = 1; k <= cas; ++k) { memset (d, 0x8f, sizeof (d)); ans = d[0]; scanf ("%d", &n); for (int i = 1; i <= n; ++i) { scanf ("%d", &a); if (d[i - 1] + a < a) d[i] = a, l = i; else d[i] = d[i - 1] + a; if (d[i] > ans) ans = d[i], le = l, ri = i; } if (k > 1) printf ("\n"); printf ("Case %d:\n%d %d %d\n", k, ans, le, ri); } return0; }
Description This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of 4n+1 numbers. Here, we do only a bit of that.
An H-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,… are the H-numbers. For this problem we pretend that these are the only numbers. The H-numbers are closed under multiplication.
As with regular integers, we partition the H-numbers into units, H-primes, and H-composites. 1 is the only unit. An H-number h is H-prime if it is not the unit, and is the product of two H-numbers in only one way: 1 × h. The rest of the numbers are H-composite.
For examples, the first few H-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.
Your task is to count the number of H-semi-primes. An H-semi-prime is an H-number which is the product of exactly two H-primes. The two H-primes may be equal or different. In the example above, all five numbers are H-semi-primes. 125 = 5 × 5 × 5 is not an H-semi-prime, because it’s the product of three H-primes.
Input
Each line of input contains an H-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.
Output
For each inputted H-number h, print a line stating h and the number of H-semi-primes between 1 and h inclusive, separated by one space in the format shown in the sample.
Sample Input
21 85 789 0
Sample Output
21 0 85 5 789 62
Semi-prime H-numbers
Description This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of 4n+1 numbers. Here, we do only a bit of that.
An H-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,… are the H-numbers. For this problem we pretend that these are the only numbers. The H-numbers are closed under multiplication.
As with regular integers, we partition the H-numbers into units, H-primes, and H-composites. 1 is the only unit. An H-number h is H-prime if it is not the unit, and is the product of two H-numbers in only one way: 1 × h. The rest of the numbers are H-composite.
For examples, the first few H-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.
Your task is to count the number of H-semi-primes. An H-semi-prime is an H-number which is the product of exactly two H-primes. The two H-primes may be equal or different. In the example above, all five numbers are H-semi-primes. 125 = 5 × 5 × 5 is not an H-semi-prime, because it’s the product of three H-primes.
Input
Each line of input contains an H-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.
Output
For each inputted H-number h, print a line stating h and the number of H-semi-primes between 1 and h inclusive, separated by one space in the format shown in the sample.
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<cstring> using namespace std; const int N = 100005; char s[N], c; int cur, last, l; struct Node{ char c; int next;} lis[N]; int main() { while (~scanf ("%s", s + 1)) { l = strlen (s + 1); lis[0].next = last = cur = 0; for (int i = 1; i <= l; ++i) { c = s[i]; if (c == '[') cur = 0; elseif (c == ']') cur = last; else { lis[i].c = c; lis[i].next = lis[cur].next; lis[cur].next = i; if (cur == last) last = i; cur = i; } } for (int i = lis[0].next; i != 0; i = lis[i].next) printf ("%c", lis[i].c); printf ("\n"); } return0; }
Bob wants to put a new bargaining table in his office. To do so he measured the office room thoroughly and drew its plan: Bob’s office room is a rectangular room n × m meters. Each square meter of the room is either occupied by some furniture, or free. A bargaining table is rectangular, and should be placed so, that its sides are parallel to the office walls. Bob doesn’t want to change or rearrange anything, that’s why all the squares that will be occupied by the table should be initially free. Bob wants the new table to sit as many people as possible, thus its perimeter should be maximal. Help Bob find out the maximum possible perimeter of a bargaining table for his office. Input
The first line contains 2 space-separated numbers n and m (1 ≤ n, m ≤ 25) — the office room dimensions. Then there follow n lines with m characters 0 or 1 each. 0 stands for a free square meter of the office room. 1 stands for an occupied square meter. It’s guaranteed that at least one square meter in the room is free.
Output
Output one number — the maximum possible perimeter of a bargaining table for Bob’s office room. Sample test(s)
This idea can be extended for any N-Dimensional space where each of the N axes is assigned a unique prime number. Each N-Dimensional space has a unique set of primes.
SB.
