博文
练手题(2008-04-27 20:33:00)
摘要：
Don't ask woman about her age
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Mrs Little likes digits most of all. Every year she tries to make the best number of the year. She tryes to become more and more intelligent and every year studies a new digit. And the number she makes is written in numeric system which base equals to her age. To make her life more beautiful she writes only numbers that are divisible by her age minus one. Mrs Little wants to hold her age in secret.
You are given a number consisting of digits 0, …, 9 and latin letters A, …, Z, where A equals 10, B equals 11 etc. Your task is to find the minimal number k satisfying the following condition: the given number, written in k-based system is divisible by k−1.
Input
Input consists of one string containing no more than 106 digits or uppercase latin letters.
Output
Output file should conta......
Orders(^_^)(2007-10-23 22:58:00)
摘要：Orders
Time Limit: 1000MS
Memory Limit: 10000K
Description
The stores manager has sorted all kinds of goods in an alphabetical order of their labels. All the kinds having labels starting with the same letter are stored in the same warehouse (i.e. in the same building) labelled with this letter. During the day the stores manager receives and books the orders of goods which are to be delivered from the store. Each order requires only one kind of goods. The stores manager processes the requests in the order of their booking.
You know in advance all the orders which will have to be processed by the stores manager today, but you do not know their booking order. Compute all possible ways of the visits of warehouses for the stores manager to settle all the demands piece after piece during the day.
Input
Input contains a single line with all labels of the requested goods (in random order). Each kind of goods is represented by the starting letter of its la......
子序列<ACM>(2007-10-03 15:46:00)
摘要：
Subsequence
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
Input
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3
说明： 从&n......
缩写匹配(2007-09-06 12:54:00)
摘要：
Campus Buildings
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Most campuses have a lot of named buildings, and as the names tend to be rather long, the class schedules have abbreviations. At USC, it seems that the abbreviations have become used so widely that most people don't even remember the full name of the building. SAL, PHE, OHE. To a newcomer, this can be quite confusing. So perhaps, we ought to write a little program that finds out which building could be meant by abbreviations.
Here's how we'll do it: you will be given a list of building names, and a building abbreviation, such as SAL or FRSSC. The abbreviation matches the building name if all of its letters appear, in this order, in the building name (no letter can be matched twice). So, for instance, SAL matches "SALvatori", or "Student Aerospace Laboratory", or "univerSity of southern cALifornia". It does not match "angeles", as the letters are ......
累加回文(2007-09-06 11:35:00)
摘要：
Eventual Palindromes
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Consider the decimal number 193. Reverse its digits and add the result to the starting number. The answer is 193 + 391 = 584. Repeat the process, 584 + 485 = 1,069. Continue the process until a palindrome is formed (a number that is the same when read in the forward or reverse directions). In this example, the palindrome is 233332, formed after eight applications of the “reverse and add” rule. All numbers are thought to yield palindromes eventually, although there is no proof of this, and, for some numbers, no palindrome has ever been found. Your task is to determine, for each input number, how many applications of the “reverse and add” rule are necessary to form a palindrome, and to find the palindrome.
Assume that no input number will be larger than 10,000. You can also assume that no palindrome will be larger than 4,668,731,596,684,224,866......
求和最大的子矩阵(2007-09-06 10:40:00)
摘要：
Maximal Sub-rectangle
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2is in the lower-left-hand corner:
9 2
-4 1
-1 8
and has the sum of 15.
Input
The input consists of an array of N × N integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by N2 integers separated by white-space (newlines and spaces). These N2 integers m......
走马(2007-09-06 09:52:00)
摘要：
Playing Chess
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 18, Accepted users: 18
Problem 10763 : No special judgement
Problem description
yiyi and birdman like to play chess.They sometimes play chess in QQ game. They discovered that the game cost a lot of time. They have lots of things to do, for instance doing homework, programming.So they come up with a good game, this game is played on the chessboard too, Is a 4 × 3 Lattice. However, only a pawn - horse. The horse on the chessboard of arbitrary position ,The pawn returns to the original location of a number of different routes ,(if a position has been arrived then should not go again and the horse takes ‘日’ route), They have to give a total number of different routes and the faster is the winner. Because they are very good at programming , Through programming they can easily give the answer. This new game is not a challenge to them ,But it maybe a challenge to......
求 n 个子序列的最大和(2007-09-05 22:08:00)
摘要：
Find the max
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Yiyiyi4321 is trying to solve the problem 10113 in acm.hnu.cn, and he found that in order to solve this problem he must learn to solve the problem below :
Give you a sequence of integers, find K subsequences of the sequence and make their sum Maximized.For example, given a sequence 3, 4, -7, 3, 5, -2, 3, find 2 subsequences from the sequence, you could take 3,4 | 3,5,-2,3, their sum is 16. find 3 subsequences from the sequence, we can take 3,4 | 3,5 | 3 ,whose sum is 18.
Input
There are two integers, separated by single spaces, in the first line : number of integers n (1 <= n <= 1000), number of subsequences K(0 <= K <= n).The consecutive n lines are the integers.
Output
Your program should write one integer, the max sum of the K subsequence.
Sample Input
7 2
3
4
-7
3
5
-2
3
Sam......
求 n 个数的最小公倍数(2007-09-05 18:58:00)
摘要：
Least Common Multiple
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. If there is no such positive integer, e.g., if a = 0 or b = 0, then lcm(a, b) is defined to be zero.
For example, the least common multiple of the numbers 4 and 6 is 12.
Input
The input contains several cases. Each case has one line containing a non-negative integer N (N<=100), then followed N non-negative integers in the range of 0 and 2147483647. A ZERO terminates the input, which should not be processed.
Output
For each test case, output the least common multiple of the N integers in seperate lines. It is guaranteed that the lcm would not exceed 231 - 1.
Sample Input
2
12 18
5
3......
上台阶(2007-09-04 22:38:00)
摘要：上阶梯★★★
上阶梯，你可以一个一个阶梯上，也可以两个两个地来，也可以一个和二个间隔着上，甚至可以一次k个
阶梯
问题是，上一个阶梯数为n，每步能上1至k个阶的话，你有多少种方法走完它？
如 n = 5 , k = 2，可以
1,1,1,1,1
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
2,2,1
2,1,2
1,2,2
共8种
输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：
5 2
5 3
输出：
8
13
解题报告：不记得什么时候写的程序了，当时写了个简单思路“斐波那弃序列变种” ，现在自己看了十几分钟才弄明白。因此写个详细的报告，以备不时之需：我们先看下 k=2 的情况，设 f(n) 表示走完台阶数为 n 的方法如果n = 1， 显然 f(1) = 1如果n = 2，台阶: 1 1 我们的走法是 f(1) 1, 2, 即若最后一步走一步则走法是 f(1) , 还有两个台阶 一步走完又是一种方法，所以 f(2) = f(1)+1 = 2;如果n = 3，同 2 我们有 f(3)=f(2)+f(1),即最后一步走一个台阶就是 f(2), 另外最后一步走两个台阶 则为 f(1), 因为k=2,最后一步不能超过 2，因此 3 2 的走法就是 f(3) = f(2)+f(1)。一般的 n = m 我们有 f(m) = f(m-1)+f(m-2) (m>=3) 即 k=2 时为正中的斐波那弃序列。
通常的 n k ,我们防上面的方法: 有 f(m) = f(m-1)+f(m-2)+ ... + f(m-k)
证明：显然 f(1) = 1 如果 k>=2 则 f(2) = 2, 如果 k>=3 , 则 f(3) = f(2)+f(1)+1 表示最后一步分别走 1，2，3个台阶。 我们按最后一步的走法即可得上面的公式：
f(m) = f(m-1)+f(m-2)+ ... + f(m-k) (m>k)
// 下面是实现代码 f(n) 的值记录在 数组 a 中了
#include <stdi......