杰拉斯的博客

写在前面

虽然不是什么文艺青年，但对着过去的事物总会有一种说不清道不明的感觉，听着《三个人的时光》这首抒情的音乐，决定也跟着文艺一把。

曾经，我也是一个什么都不懂的菜鸟，第一次与网络亲密接触的时候，我就在想：“我们一直以来上的都是别人网站，我能不能自己制作一个呢？”于是稀里糊涂的就开始学起了网页……

这么多年走过，也算是小有所成，捣鼓过不少作品，只是想即便放出来也只是贻笑于大方之家罢了，于是这些在我手里诞生的作品们便在硬盘里尘封了多年，直到最近，突然觉得让他们只能在自己的硬盘里待着也实在没什么意义，要是有一天硬盘坏了那就再也找不出来了，于是收拾心情把这些旧事物整理出来，或许有一天我真正成熟，乃至老去，我可以指着这些东西对别人说，你看，这些幼稚的作品，却是我一步一步走过来的痕迹。。

朝花夕拾，为时未晚。。

(阅读全文…)

Douglas Crockford是Javascript权威，Json格式就是他的发明。

(阅读全文…)

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.

(阅读全文…)