杰拉斯的博客

Tian Ji -- The Horse Racing

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9786 Accepted Submission(s): 2718

Description

Here is a famous story in Chinese history.

"That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others."

"Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser."

"Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian."

"Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match."

"It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king's regular, and his super beat the king's plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?"

Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian's horses on one side, and the king's horses on the other. Whenever one of Tian's horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching...

However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses --- a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.

In this problem, you are asked to write a program to solve this special case of matching problem.

(阅读全文…)

注释

Time Limit:1000MS Memory Limit:32768K

Description

给出一个C++源程序代码。请将其中的注释去掉。

Sample Input

//======================

// simplest program

//======================
#include<iostream>
using namespace std;
//----------------------
int main(){
cout<<”hello world!\n”;
}//---------------------

Sample Output

#include<iostream>
using namespace std;
int main(){
cout<<”hello world!\n”;
}

(阅读全文…)

Moving Tables

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9950 Accepted Submission(s): 3389

Description

The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.

The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.

For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.

(阅读全文…)

Lily's puzzle

Time Limit:1000MS Memory Limit:32768K

Description

最近lily的好朋友Kingly在农场里干活，农场里种了很多树，Kingly的任务就是：给定树的位置，然后到农场里清点树的棵数，由于他比较死板，只会一棵棵去数，所以他的工资比别人少。而lily就提醒他用计算机，因为这是计算速度最快的东东！同时lily又想到了一个问题：如果给定一个区域的尺寸，怎么样才能数出这个范围内的树最多？
举个例子，在下图中，农场是一个宽为10长为8的矩形。

每个（*） 代表一棵树。 如果给定区域的一边为4另一边为3的，那么显然是左上方的小矩形区域中的树最多，是5棵。 你的任务就是解决上述的问题！

(阅读全文…)

今年暑假不AC

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13173 Accepted Submission(s): 6807

Description

“今年暑假不AC？”

“是的。”

“那你干什么呢？”

“看世界杯呀，笨蛋！”

“@#$%^&*%...”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

(阅读全文…)