博文
Picking Coins(2008-04-28 12:31:00)
摘要：
Picking Coins
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
A pack of coins have been divided into piles, each pile has some number Ni (1 <= Ni <= 25) of coins. All the piles have been placed in an area of R rows(1 <= R <= 100) and C columns (1 <= C <= 100).Given a starting location, you have to make your way out of the area and gather as many coins as you can. From the position (r,c) you can only move to (r-1,c+1), (r, c+1), or (r+1,c+1) and endup your way at any edge of the area. If there exist more than one path that can gather the maximum number of coins, make your path the shortest.
Input
There will be only one testcase in the input file, the first line contains Two space-separated integers, respectively R and C, then followed R lines, Each line contains C space-separated integers in the obvious order, the last few lines each contains two integer which indicate the starting loca......
Zipper(字符串处理）(2007-10-08 13:47:00)
摘要：
Zipper
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Problem description
Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree":
String A: cat
String B: tree
String C: catrtee
Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".
Input
The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The......
Oulipo (模式匹配)(2007-10-08 07:46:00)
摘要：
Oulipo
Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB
Problem description
The French author Georges Perec (1938-1982) once wrote a book, La disparition, without the letter ‘e’. He was a member of Oulipo group. A quote from the book:
Tout avait l’air normal, mais tout s’affirmait faux. Tout avait l’air normal, d’abord, puis surgissait l’inhumain, l’affolant.Ⅱaurait voulu savoir ou s, articulait l’association qui l’unissait au roman: sur son tapis, assailant atout instant son imagination, l’intution d’un tabou, la vision d’un mal obscure, d’sun quoi vacant, d’un non-dit: la vision, l’avision d’un oubli commandant tout,ou s’abolissait la raison: tout avait l’air normal mais …
Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given ”word” as possible. Our task is to provide the jury with a program that coun......
Digital Friends(2007-10-05 22:10:00)
摘要：Digital Friends
Description
Two positive integers are called friends if they consist of the same decimal digits. So 123 and 32331313323213 are friends, but 123 and 22121221 are not.
Two positive integers (that are not friends) are called almost friends if a single neighbour exchange in one of them results in a pair of friends. A neighbour exchanges two neighbouring digits a and b into a-1 and b+1, or into a+1 and b-1, provided that these new digits are still in the range 0...9, and that no leading zero is generated. So 123 and 2223042 are almost friends(let 04->13), and 137 and 470 are neither friends nor almost friends(note that 13 -> 04 is not allowd).
The problem is to determine if two given integers are friends or almost friends.
Input
The frist line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
One line with two integer x and y, separated by a single space, with 0 < x, y < 10......
序列<ACM>(2007-10-03 13:38:00)
摘要：///// 好一段时间没做ACM题了,AC一道题都难了,看来以后还得经常练手...... , 贴一道简单的题
Sequence
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:65536KB
Problem description
Giving a collection S of points on two dimension plane. (S = {(x0,y0), (x1,y1), ... }) We define a point is greater than another point when all its coordinate on two axis are both greater than or equel to another one. Namely, p is greater than q when xp ≥ xq and yp ≥ yq. A sequence is a list points < p1, p2, ... > satisfy that i < j => pi is greater than pj. You can use the elements in S to construct sequences, how many sequences needed to cover a S at least?
Input
The input consists of several test cases. Each test case start with a line containing a number n(0 < n ≤ 1000000), the number of points in S. Then n lines follows, each line containing two number, xi, yi(0 ≤ xi, yi ≤ 100000), the position of point i. The input end with EOF.
Output
Yo......
排队买票(2007-09-05 18:38:00)
摘要：
Buy tickets
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
There are N people who want to buy some tickets, and there are M places to serve them. These people are numbered from 1 to N , and person i will be served in Ti minites. If N > M, some people will have to wait. Now we want to rearrange the sequence of these people so that the sum of the waiting time of all the people will be minimized, and your task is to calculate the minimum waiting time.
Input
The first line is two integers N(1 <= N <= 1000) and M(1 <= M <= 100), which is the number of the people and the number of places to serve them. The following n lines is the time which the N people need to be served.
Output
Only one integer, the minimum waiting time.
Sample Input
5 3
3
4
2
8
4
Sample Output
5
//// 第一行输入 n m ,n 表示需要买票的总人数，m 表示提供服务的窗口数目，接下来的 n 行每行一个整数表示第 i （1<=i<=n) 个......
判断线段与矩形是否相交(2007-09-05 18:05:00)
摘要：
Intersection
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
You are to write a program that has to decide whether a given line segment intersects a given rectangle.
An example:
line: start point: (4,9)
end point: (11,2)
rectangle: left-top: (1,5)
right-bottom: (7,1)
Figure 1: Line segment does not intersect rectangle
The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.
Input
The input consists of n test cases. The first line of the input file contains the number n. Each following line contains one test case of the format:
xstart ystart xend yend xleft ytop xright ybottom
where (xstart, ystart) is the start and (xend, yend) ......
Wooden Sticks (STL use)(2007-09-03 19:13:00)
摘要：
Wooden Sticks
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are......
Marbles in Three Baskets（广搜）(2007-09-03 01:26:00)
摘要：
Marbles in Three Baskets
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 15, Accepted users: 13
Problem description
Each of three baskets contains a certain number of marbles. You may move from one basket into another basket as many marbles as are already there, thus doubling the quantity in the basket that received the marbles. You must find a sequence of moves that will yield the same number of marbles in the three baskets. Moreover, you must achieve the goal in the smallest possible number of moves. Your program must also recognize the case in which there is no such sequence of moves.
Input
Each line of the input file will contain data for one instance of the problem: three positive integers, with one blank space separating adjacent integers. The three integers represent the initial numbers of marbles in the three baskets. The sum of the three integers will be at most 60.
Output......
Permutation Recovery(2007-09-02 21:04:00)
摘要：
Permutation Recovery
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Professor Permula gave a number of permutations of the n integers 1, 2, ..., n to her students. For each integer i (1 <= i <= n), she asks the students to write down the number of integers greater than i that appears before i in the given permutation. This number is denoted ai. For example, if n = 8 and the permutation is 2,7,3,5,4,1,8,6, then a1 = 5 because there are 5 numbers (2, 7, 3, 5, 4) greater than 1 appearing before it. Similarly, a4 = 2 because there are 2 numbers (7, 5) greater than 4 appearing before it.
John, one of the students in the class, is studying for the final exams now. He found out that he has lost the assignment questions. He only has the answers (the ai's) but not the original permutation. Can you help him determine the original permutation, so he can review how to obtain the answers?
Input
The input......